Links: Modular Arithmetic

Euler’s Theorem

Euler’s Theorem is a more general case of Fermat’s Little Theorem using Euler’s Totient Function. Theorem

In the case of being prime and it simplifies to Fermat’s Little Theorem.

Proof By considering the elements of (The Reduced Residue System ), and multiplying them together. . Hence

Since the products only contain coprime to the whole product will share no prime factors to and so the whole product is coprime to and therefore can be cancelled. Therefore as required.