Links: Modular Arithmetic

Fermat’s Little Theorem

Theorem Let be prime and , then

Proof: Using the Reduced Residue System , . Multiplying all the elements together yields . This gives . Since , you get .

Proof: By Induction Base case: Induction forwards Assume , then by assumption.

Induction backwards Assume , then . For is odd. so we get which by our assumption . For , we get which by our our assumption .

Therefore we get the fact that . If has an inverse you get .