Question

Using fermat's little theorem, find the least positive residue of $2^{1000000}$ modulo 17.

Answer 1

Fermat's little theorem states that

`a^p`≡a mod p

If we divide both sides by a, then

`a^(p-1)`≡1 mod p
=>

`a^(17-1)`≡1 mod 17

`a^(16)`≡1 mod 17

Rewrite

`a^(1000000)` mod 17 as

`=(a^(16))^(62500)` mod 17
and apply Fermat's little theorem

`=(1)^(62500)` mod 17
=>

`=(1)` mod 17

So we conclude that

`a^(1000000)`≡1 mod 17