TheoremProved

Euler's theorem (totient)

Statement

If $\gcd(a,n)=1$ , then $a^{\varphi(n)}\equiv 1 \pmod{n}$ , where $\varphi(n)$ (Euler's totient function) counts the integers in $\{1,\dots,n\}$ coprime to $n$ .

Why is it true?

This generalizes Fermat's little theorem from prime moduli to arbitrary moduli: the same permutation argument works on the $\varphi(n)$ residues invertible mod $n$ , instead of on all of $1,\dots,p-1$ .

Proof sketch

Let $R=\{r_1,\dots,r_{\varphi(n)}\}$ be the residues mod $n$ coprime to $n$ . Multiplication by $a$ permutes $R$ , since $\gcd(a,n)=1$ . Multiplying all elements of $R$ before and after this permutation gives $a^{\varphi(n)}\prod r_i \equiv \prod r_i \pmod n$ ; cancelling $\prod r_i$ (invertible mod $n$ ) yields $a^{\varphi(n)}\equiv1\pmod n$ .

Stated by

Leonhard Euler

Proved by

proved 1763Leonhard Euler

Topics that use this theorem

Congruences and modular arithmetic Fermat's little theorem and Euler's theorem

Related theorems

Fermat's little theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Leonhard Euler (1763). Theoremata arithmetica nova methodo demonstrata
G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers · DOI:10.1093/oso/9780199219858.001.0001