3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Joel Cohen Nov 12 '12 at 1:00
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ how do you know $2^{9} = -1 \pmod {19}$ $\endgroup$ – Drew Nov 12 '12 at 3:28
  • $\begingroup$ 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$$ $\endgroup$ – DonAntonio Nov 12 '12 at 3:29
  • $\begingroup$ Since $2^{9}=2^{5}\cdot2^{4}=-3\cdot-6=18=-1$ never mind it in mod19 not 18 $\endgroup$ – Drew Nov 12 '12 at 3:42
  • $\begingroup$ Careful: $\,18=-1\pmod{19}\,$ , not $\,1\,$ ! $\endgroup$ – DonAntonio Nov 12 '12 at 3:43
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Drew Nov 12 '12 at 5:43
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.