Compute the remainder of $2^{2^{17}} + 1$. 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$ 
 A: 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} ...$$
A: 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
A: $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$.
