# Order of 2 modulo p, where p is a prime divisor of the Fermat number $F_n=2^{2^n}+1$

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}$$.
• 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? – Anna Naden Aug 29 at 1:51
• @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. – John Omielan Aug 29 at 2:37