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

591 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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