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$

  • 0
    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...2012-11-12

3 Answers 3