# Help with finding the remainder of $2^{2^n}$ when divided by 13

I have this problem from an algebra course:

Find the remainder of $2^{2^n}$ when divided by 13, $\forall n \in \Bbb N$

It's in a section of Fermat's little theorem and Chinese Remainder Theorem exercises but I don't understand how to solve it.

There's something I'm missing, any hints please? Thanks!

• Find $2^n$ mod 12. – Aravind Jun 8 '16 at 17:53
• @Aravind Haha, it was so simple. Then I should find $2^{12q+r}$ mod 13, right ? Thanks – jrs Jun 8 '16 at 18:02
• Since $13$ is prime, and in conjunction with Fermat's Little Theorem: $2^{12}\equiv1\pmod{13}$. Therefore: $2^{12k+m} \equiv 2^{12k}\cdot2^m \equiv (2^{12})^k\cdot2^m \equiv 1^k\cdot2^m \equiv 1\cdot2^m \equiv 2^m\pmod{13}$. Therefore: $2^a\equiv2^{a\bmod{12}}\pmod{13}$. Therefore: $2^{2^n}\equiv2^{{2^n}\bmod{12}}\pmod{13}$. – barak manos Jun 8 '16 at 18:12

The sequence given by $a_n=2^{2^n}$ fulfills $$a_{n+1} = a_n^2$$ hence the sequence $\!\!\pmod{13}$ becomes periodic very soon: $$\begin{array}{|c|c|c|c|}\hline n & 0 & 1 & 2 & 3 & 4 & 5 & \ldots\\ \hline a_n \pmod{13} & 2 & 4 & \color{red}{3} & \color{blue}{9} & \color{red}{3} & \color{blue}{9} & \ldots\\ \hline\end{array}$$