Fermat's little theorem states that
[tex]a^p[/tex]≡a mod p
If we divide both sides by a, then
[tex]a^{p-1}[/tex]≡1 mod p
=>
[tex]a^{17-1}[/tex]≡1 mod 17
[tex]a^{16}[/tex]≡1 mod 17
Rewrite
[tex]a^{1000000}[/tex] mod 17 as
[tex]=(a^{16})^{62500}[/tex] mod 17
and apply Fermat's little theorem
[tex]=(1)^{62500}[/tex] mod 17
=>
[tex]=(1)[/tex] mod 17
So we conclude that
[tex]a^{1000000}[/tex]≡1 mod 17
