Euler's theorem (modular arithmetic)

maths

Statement

Euler’s theorem

For integers $n,a \in \mathbb{Z}$ such that gcd(n,a) = 1. Then

$$a^{\phi(n)} = 1 \ (mod \ n)$$

where $\phi(n)$ is Euler’s totient function.

Proof

Theory

This generalises Fermat’s little theorem.