# Problem about Fermat numbers and order of an element

Let Fn = 22n + 1 be the nth Fermat number and suppose that p|Fn, where p is a prime (possibly Fn itself). Show that $2^{2^{n+1}} \equiv 1 (mod p)$ so that $ord_p(2)|2^{n+1}$. Use this to show that $ord_p(2) = 2^{n+1}$.

So far i have shown that $2^{2^{n+1}} \equiv 1 (mod p)$ so that $ord_p(2)|2^{n+1}$. But what I'm having trouble showing now is that 2n+1 is the smallest possible number k such that $2^k \equiv 1 (mod p)$. I know that the order of 2 must be some power of 2 so I have tried to use a contradiction argument assuming that there exists a 2k such that $2^{2^k} \equiv 1 (mod p)$. then i have $2^{2^{n+1}} \equiv 2^{2^k} (mod p)$ so $2^{2^{n+1}-2^k} \equiv 1 (mod p)$. but i can't seem to find a contradiction.

can someone give me some hints to continue? thanks.

$2^{2^{n+1}-2^k} = 2^{\left(2^k + 2^{k+1} + 2^{k+2} + ... + 2^n\right)} = 2^{2^k} \cdot 2^{2^{k+1}} \cdot 2^{2^{k+2}} \cdot ~...~ \cdot 2^{2^n}$, but $2^{2^k}$ was 1 modulo p... See if you can unwind the whole thing to get $2^{2^{k+1}} \equiv 1 \pmod p$, at which point you can find your contradiction.

Be careful, however (you probably know this already), with arguments that cancel something on both sides of a congruency. $10 \equiv 6 \pmod 4$, but $5 \not\equiv 3 \pmod 4$. What you cancel out in your case are expressions congruent to 1 mod p, which, since they are 1 multiplying something, can be removed.

i think i know how to continue the problem. thanks for your reply!

Oops... I used a neat trick to conclude something stupid. Sorry, it was Sunday. :)

Successive squares of $2^{2^k}$ will also be congruent to 1, which contradicts the initial statement that $2^{2^n} \equiv -1 \pmod p$ (since p has to be odd to divide Fn).

ah yes that is what i have concluded as well. your first post still helped me to come to fact though!