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