The order of 2 modulo p is the minimal solution of $2^t\equiv 1 \pmod{p}$

Euler's theorem guarantees that the congruence has a solution. The challenge is to demonstrate that $k=2^{n+1}$ is the minimal solution where p is a prime divisor of the n-th Fermat number $F_n$

We know that all solutions are multiples of the minimal solution:

If $2^t\equiv 1 $ and $k\nmid t$ then $t=kq+r$ with $0\lt r \lt k$ and

$2^r 2^{kq} \equiv 1\equiv 2^{kq}$ with $gcd(p,2^{kq})=1$ so by the cancellation law,

$2^r \equiv 1$

but since k is minimal, this is a contradiction, so $k|t$

From here I don't know how to proceed.


Since $p \mid 2^{2^n}+1$, expressing this in congruence form and squaring both sides gives

$$2^{2^n} \equiv -1 \pmod{p} \implies 2^{2^{n+1}} \equiv 1 \pmod{p} \tag{1}\label{eq1A}$$

Thus, the multiplicative order of $2$ modulo $p$, which you're calling $k$, must divide $2^{n+1}$, so $k$ is a power of $2$, say $k = 2^j$. If any $j \lt n + 1$ gives $2^k \equiv 1 \pmod{p}$, then $k$ being any higher power of $2$ would also be congruent to $1$. However, that contradicts $2^{2^n} \equiv -1 \pmod{p}$. This means $j = n + 1,$ so the multiplicative order, i.e., minimal solution, of $2^k \equiv 1 \pmod{p}$ is $k = 2^{n+1}$.

| cite | improve this answer | |
  • $\begingroup$ I guess since k is a power of two, $2^{2^n}\equiv -1$ and $2^{2^n+1}\equiv 1$, $2^{2^n+1}$ is the smallest power of two and $2^n+1$ must be the smallest solution. Is that right? $\endgroup$ – Anna Naden Aug 29 at 1:51
  • $\begingroup$ @AnnaNaden Yes, that's correct, except the power is $2^{n+1}$, not $2^{n} + 1$ as you wrote, as the latter indicates just multiplying by $2$ instead of squaring (use 2^{n+1} in MathJax). If you have any $m$ where $2^m \equiv 1 \pmod{p}$, then the smallest $k$ where $2^k \equiv 1 \pmod{p}$ must be one where $k \mid m$, as you show yourself in your question. Since $2^{2^{n+1}} \equiv 1 \pmod{p}$, then $k \mid 2^{n+1}$, i.e., is a power of $2$. As I explained in my answer, $k$ can't be any smaller $2^{n+1}$ due to $2^{2^{n}} \equiv -1 \pmod{p}$, so $k = 2^{n + 1}$ is the smallest solution. $\endgroup$ – John Omielan Aug 29 at 2:37

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.