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

• In Fermat's theorem, the exponent is $p-1$ (we have $a^{p-1} \equiv 1 \mod p$), not any number $n$. For $p = 19$, it gives you $2^{18} \equiv 1 \mod 19$. Now, remember that the $\equiv$ sign behave like a $=$ sign in that you can take the exponent of both sides, add the same quantity on both sides, multiply both sides by the same number... – Joel Cohen Nov 12 '12 at 1:00

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

• how do you know $2^{9} = -1 \pmod {19}$ – Drew Nov 12 '12 at 3:28
• By inspection (the "check directly" part in my answer). Working all the time modulo $\,19\,$ we get: $$2^4=-3\,\,,\,2^5=-6\,\,,\,2^6=-12\,\,,\,2^7=-24=-5\,\,,\,2^8=-10\,\,,\,2^9=-20=-1$$ – DonAntonio Nov 12 '12 at 3:29
• Since $2^{9}=2^{5}\cdot2^{4}=-3\cdot-6=18=-1$ never mind it in mod19 not 18 – Drew Nov 12 '12 at 3:42
• Careful: $\,18=-1\pmod{19}\,$ , not $\,1\,$ ! – DonAntonio Nov 12 '12 at 3:43
• Thanks for the help. If you would check my work that would be helpful. All in $mod19$Now $2^{17}=18q+14$. So $2^{2^{17}}=2^{18q+14}=2^{18q}\cdot2^{14}$. Now $2^{18q} \equiv 1\pmod{19}$ by fermat's theorem. 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}$. – Drew Nov 12 '12 at 5:43

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

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

• I think your first line is wrong: $$2^{17}\neq 2^4\cdot2^4\cdot2$$ – DonAntonio Nov 12 '12 at 1:20
• Yes. thank you I will fix it – Amr Nov 12 '12 at 1:22
• @Amr how did you get $2^{2^{17}} \equiv 2^{14} \pmod {19}$ – Drew Nov 12 '12 at 4:11
• I used fermat's little theorem. – Amr Nov 12 '12 at 16:41