Compute the remainder of $2^{2^{17}} + 1$.

Question

This question comes from Fraleighs book A First Course in Abstract Algebra.
Compute the remainder of $2^{2^{17}} + 1$ divided by 19. [Hint: You will need to compute the remainder of $2^{17} \mod 18$.]

First off I do not even understand how the hint will helps me. The question comes from the section Fermat's and Euler's theorem's. By fermat's theorem they mean his little theorem: If $a\in \Bbb Z $ and p is prime and p not dividing a, then p divides $a^{p-1} -1$ , that is, $a^{p-1}\equiv 1\pmod p $.

I understand how to do $2^{n}\pmod {19} $. Since 19 does not divide 2, we may say $2^{n-1}\equiv 1\pmod {19} $. Since $2^{n}=2\cdot2^{n-1}\equiv 2\cdot1\pmod {19}$ so in general any $n\in \Bbb Z $ has remainder 2. What is really confusing me is the $+1$ in the statement $2^{2^{17}} + 1$

Answer 1

Checking directly, $\,2^9=-1\pmod {19}\,$ , so $\,2^{18}=1\pmod {19}\,$ . Now the hint must be clear:

$$2^4=-2\pmod {18}\Longrightarrow 2^{17}=(2^4)^4\cdot =(-2)^4\cdot 2=16\cdot 2=14\pmod {18} ...$$

Answer 2

Thanks for the help. If someone could check my work that would be helpful. Now $2^{17}=18q+14$.
So $$2^{2^{17}}=2^{18q+14}=2^{18q}\cdot2^{14}.$$ Now by fermat's little theorem, $$2^{18q} \equiv 1\pmod{19}.$$
Now $$2^{14}=2^{4}\cdot2^{4}\cdot2^{4}\cdot2^{2}=-3\cdot-3\cdot-3\cdot4=-27\cdot4=-8 \cdot 4=-32=-13=6.$$ So $$2^{2^{17}}\equiv 6 \pmod {19}.$$ Now $1\equiv 1 \pmod {19}$. So $$2^{2^{17}}=19m+6\; and \;1=19(0)+1$$ therefore $$2^{2^{17}}+1=19(m+0)+6+1$$ thus $$2^{2^{17}}+1 \equiv 7 \pmod {19}.$$ Q.E.D

Answer 3

$2^{17}\equiv(2^{4})^42\equiv(-2)^4(2)\equiv(-2)(2) \mod 18=14$

$\phi(19)=18$ Since $2^{2^{17}}\equiv2^{14} \mod 19$

(because $2^{17}\equiv14 \mod \phi(19))$

Therefore we end up evaluating $2^{14} \mod 19=6$

Thus $2^{2^{17}}+1\equiv2^{14}+1\equiv6+1\equiv7 \mod 19$ Hence the answer is $7$.