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?
 A: 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}$.
A: 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.
A: 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$
