# Math Help - fermat's little thm

1. ## fermat's little thm

compute the remainder when 2^(2^17) + 1 = 19

that + 1 is really throwing me off... I don't know how to deal with it.

2. Originally Posted by Coda202
compute the remainder when 2^(2^17) + 1 = 19

that + 1 is really throwing me off... I don't know how to deal with it.
I assume you want to find the remainder of $2^{2^{17}}+1$ modulo $19$.

By the division algorithm we can write $2^{17} = 18q + r$ where $0\leq r < 18$.
But then, $2^{2^{17}} = 2^{18q + r} = \left( 2^{18} \right)^q \cdot 2^r \equiv 2^r (\bmod 19)$.

To find the remainder $r$ we need to simplify $2^{17}$ modulo $18$.
First, $2^{\phi(9)} \equiv 1(\bmod 9) \implies 2^6\equiv 1(\bmod 9) \implies 4\cdot 2^{16} \equiv 1(\bmod 9)$.
Multiply both sides by seven to get, $2^{16}\equiv 7(\bmod 9) \implies 2^{17}\equiv 14(\bmod 18)$.

Therefore, $2^{2^{17}}\equiv 2^{14} (\bmod 19)$.

Now, $16\cdot 2^{14}\equiv 1(\bmod 19)$ by Fermat's little theorem.
Since $16\cdot 6\equiv 1(\bmod 19)$ we see that $2^{14} \equiv 6(\bmod 19)$.

But this is remainder of only $2^{2^{17}}$ if you want to find remainder of $2^{2^{17}}+1$ just add 1.