Let $p$ be a prime divisor of the Fermat number $F_{n} = 2^{2^{n}} + 1$.
Show that ord$_{p}2 = 2^{n + 1}$
The order of the element modulo some integer is the least positive integer such that it divides the "maximum" order.
Some attempt I made:
Assume that Fermat number is prime. By Fermat Theorem, we have:
$2^{2^{2^{n}}} \equiv 1 \bmod (2^{2^{n}} + 1)$
I want to show that ord$_{p}2 = 2^{n + 1}$ i.e. $2^{2^{n + 1}} \equiv 1 \bmod (2^{2^{n}} + 1)$. The question I have is: How do you know that $2^{n + 1}$ is a least positive integer such that we obtain 1 mod Fermat number? Can this be done by Modular Arithmetic, or is there a theorem that I need to use? Well, I found the orders of an element that divide the order $F_{n} – 1$, which are basically in the set $\{2^{k} | k \in \mathbb{N}\}$, but I don't know where to go from here.
Any comments or suggestions?
Best Answer
We are told that $p$ divides $2^{2^n}+1$. So $2^{2^n}+1\equiv 0\pmod{p}$. It follows that $2^{2^n}\equiv -1\pmod{p}$.
The square of $2^{2^n}$, which is $2^{2^{n+1}}$ (to square, a number, we double the exponents), is therefore congruent to $1$ modulo $p$.
Thus the order of $2$ divides $2^{n+1}$, so it is a power of $2$. Since $2^{2^n}\equiv -1\pmod{p}$, the order of $2$ must be greater than $2^n$. Thus it is $2^{n+1}$.