# For any Fermat number $F_n=2^{2^n}+1$ with $n>0$, establish that $F_n\equiv5\,\text{or}\,8\pmod9$

For any Fermat number $F_n=2^{2^n}+1$ with $n>0$, establish that $F_n\equiv5\,\text{or}\,8\pmod9$ according as $n$ is odd or even.

Since for any $n\ge3$,$2^{2^n}\equiv2^{2^{n-2}}\pmod9$, if $n=2k+3$ then $$2^{2^n}=2^{2^{2k+3}}\equiv2^{2^{2k+1}}=(2^{2^{2k}})^2\pmod9?$$ if $n=2k+4$ then $$2^{2^n}=2^{2^{2k+4}}\equiv2^{2^{2k+2}}=(2^{2^{2k}})^4\pmod9?$$ but I don't know how continue?

• Note that $2^{2^n} = \left(2^{2^{n-1}}\right)^2$. – Daniel Fischer Mar 11 '14 at 14:08

## 3 Answers

The proof is by induction on $n$. We have $F_1\equiv 5\pmod{9}$.

Note that $F_{n+1}-1=(F_n-1)^2$. This is because $2^{2^{n+1}}=(2^{2^n})^2$. Rewrite as $$F_{n+1}=(F_n-1)^2+1.$$ Now we do the induction step.

If $F_k\equiv 5\pmod{9}$, then $(F_k-1)^2\equiv 16\equiv 7\pmod{9}$, and therefore $F_{k+1}\equiv 8\pmod{9}$.

Similarly, if $F_k\equiv 8\pmod{9}$, then $(F_k-1)^2\equiv 4\pmod{5}$, and therefore $F_{k+1}\equiv 5\pmod{9}$.

• In $(F_k-1)^2 \equiv 25 \equiv$ the $25$ should be a $4^2=16$ or not? – Gottfried Helms Mar 11 '14 at 14:47
• Yes, thank you, fixed. – André Nicolas Mar 11 '14 at 16:18

Note that $2^6 \equiv 1 \pmod 9$.

Also $2^n \equiv 2,4 \pmod 6$ depending on the parity of $n$. If $n$ is odd then $2^n \equiv 2 \pmod 6$, otherwise $2^n \equiv 4 \pmod 6$. This means that $2^n = 6k + 2$ or $2^n = 6k + 4$. Now just substitute and use the first conclusion.

As ord$_92=6,$

$$\displaystyle2^{2^n}\equiv2^{2^n\pmod{\phi(9)}}\pmod 9$$

Now, $\displaystyle2^1\equiv2,2^2\equiv4,2^3\equiv2\pmod6$

So for $n(>0)$ odd, $\displaystyle2^n\equiv2\pmod6\implies2^{2^n}\equiv2^2\pmod9$

So for $n(>0)$ even, $\displaystyle2^n\equiv4\pmod6\implies2^{2^n}\equiv2^4\pmod9\equiv7$