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

  • 1
    $\begingroup$ 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$? $\endgroup$ – Greg Martin Jan 15 at 20:15
  • 1
    $\begingroup$ 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 $\endgroup$ – user635073 Jan 15 at 21:09
  • $\begingroup$ 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$.) $\endgroup$ – 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$.

  • 1
    $\begingroup$ This answer does not prove the assertion that the order modulo $B$ equals $4m$. $\endgroup$ – Greg Martin Jan 16 at 4:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Patrick Sole Jan 16 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.