Find Remainder When Divided by 19

[Deanmark]

Compute the remainder of 2^(2^17) + 1 when divided by 19. The book says to first compute 2^17 mod 18 but I don’t understand why we go to mod 18. Advice would be appreciated

 

[I like Serena]

Compute the remainder of 2^(2^17) + 1 when divided by 19. The book says to first compute 2^17 mod 18 but I don’t understand why we go to mod 18. Advice would be appreciated

Hi Deanmark,

That's because of the Little Theorem of Fermat:
$$a^{p-1} \bmod p = 1$$
where $p$ is prime and $a$ is any number except for a multiple of $p$.

So if we can write $2^{17}$ as some multiple of $18$ and a remainder, say $2^{17} = 18k + r$, then:
$$2^{(2^{17})} + 1 \bmod 19 = 2^{18k+r} + 1 \bmod 19 = (2^{18})^k\cdot 2^r + 1 \bmod 19 = 2^r + 1 \bmod 19$$

 

[Deanmark]

The parts of my wall that have yet to be punched thank you.