0
$\begingroup$

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!

$\endgroup$
3
  • 5
    $\begingroup$ Find $2^n$ mod 12. $\endgroup$
    – Aravind
    Jun 8, 2016 at 17:53
  • $\begingroup$ @Aravind Haha, it was so simple. Then I should find $2^{12q+r}$ mod 13, right ? Thanks $\endgroup$
    – jrs
    Jun 8, 2016 at 18:02
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – barak manos
    Jun 8, 2016 at 18:12

1 Answer 1

Reset to default
3
$\begingroup$

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}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .