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
