Find the smallest positive integer $\ell$ such that $3 \cdot \left(4^m + 1\right)$ divides $2^\ell-1$

Question

Find the smallest positive integer $\ell$ such that $3 \cdot \left(4^m + 1\right)$ divides $2^\ell-1$

Hint: The sought $\ell$ is the multiplicative order of $2$ in the ring of integer residues modulo $3\cdot(4^m+1)$.

I am having trouble understanding the hint, are there any "special" characteristics of a ring of integer that might help me?

The answer is supposed to be $4m$ , and I have already managed to show that $3 \cdot \left(4^m + 1\right)$ divides $2^{4m}-1$ , but I do not know how to prove that this is the smallest positive solution.

Link to the question

Answer 1

I may have done this a different way than from suggested in your hint OP.

Claim: $2^{2m}+1 =4^m+1$ does not divide $2^{\ell}-1$ for $\ell < 4m$.

Proof: $(2^{\ell-2m}-1)(2^{2m}+1) = 2^{\ell}+2^{\ell-2m}-2^{2m}-1 < 2^{\ell}-1$ if $\ell$ satisfies the inequality $\ell -2m < 2m$ or equivalently if $\ell$ satisfies the inequality $\ell < 4m$. On the other hand $2^{\ell-2m} (2^{2m}+1) > 2^{\ell}-1$. [Do you see how this implies that $2^{2m}+1$ indeed does not divide $2^{\ell}-1$? For some integer $a$, the integer $a(2^{2m}+1)$ is strictly less than $2^{\ell}-1$ yet the integer $(a+1)(2^{2m}+1)$ is strictly greater than $2^{\ell}-1$.]

So $\ell$ as in your problem must be at least $4m$.

However, $\ell=4m$ works; indeed

$$2^{4m}-1 = (2^{2m}-1)(2^{2m}+1) = (2^{2m}-1)(4^m+1).$$

So now it remains to show that $3|(2^{4m}-1)$. However, note that $3|(2^{2m}-1)$ for every integer $m$ [make sure you see why], so $\ell=4m$ indeed works; $3\times(2^{2m}+1)$ divides $(2^{4m}-1)$.

Answer 2

The ring of integers in the hint can be decomposed by the CRT into the product of $A=\Bbb{Z}_3$ by $B=\Bbb{Z}_{4^m+1}$. The order of 2 in each of these two rings is respectively 2 (because in $A$, $2^2=1$), and $4m$ (because in $B$, $2^{2m}=-1$) . Hence the order in the product is $\operatorname{LCM}(2,4m)=4m$.