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

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

  • 1
    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}$.2012-11-12
1

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

0

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

  • 0
    I used fermat's little theorem.2012-11-12