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

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.

• Thanks for the well-asked question! The divisibility you've already established shows that the order must at least divide $4m$. Is it possible for $3(4^m+1)$ to divide $2^\ell-1$ if $\ell\le 2m$? – Greg Martin Jan 15 at 20:15
• 3(4^m+1)>4^m=2^(2m) , so that mean that 3(4^m+1) can not divide 2^ℓ-1 if ℓ is smaller then 2m , but i still do know how to show that there is no other ℓ between 2m to 4m – user635073 Jan 15 at 21:09
• Do you know the following fact? If $a$ divides $2^\ell-1$, then the multiplicative order of $2$ in the ring of integer residues modulo $a$ divides $\ell$. (The point to emphasize here is that the order must not only be at most $\ell$ but must actually divide $\ell$.) – Greg Martin Jan 16 at 4:45

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)$$.

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$$.

• This answer does not prove the assertion that the order modulo $B$ equals $4m$. – Greg Martin Jan 16 at 4:46
• If we have in B, the equality x^s=-1that certainly shows the order of x divides 2s and cannot be s, nor a divisor of s. So it has to be 2s. – Patrick Sole Jan 16 at 13:38