Canonical: https://knowlpedia.com/algebra-groups/eulers-theorem/

# Euler's Theorem

If gcd(a,n)=1 then a^{φ(n)} ≡ 1 (mod n).

**Euler's theorem.** Let \(n\ge 1\) and \(a\in\mathbb Z\). If the [greatest common divisor](https://knowlpedia.com/algebra-rings/gcd/) of \(a\) and \(n\) is \(1\), then
\[
a^{\varphi(n)}\equiv 1\pmod n,
\]

where Euler's totient function is
\[
\varphi(n)=\bigl|\{k\in\{1,\dots,n\}:\gcd(k,n)=1\}\bigr|.
\]

Here \(x\equiv y\pmod n\) means that \(n\) divides \(x-y\).

## Remarks

This follows from [Lagrange's theorem](https://knowlpedia.com/algebra-groups/lagranges-theorem/) applied to the [group of units](https://knowlpedia.com/algebra-rings/group-of-units/) \((\mathbb Z/n\mathbb Z)^\times\), whose order is \(\varphi(n)\). The case in which \(n=p\) is prime is [Fermat's little theorem](https://knowlpedia.com/algebra-groups/fermats-little-theorem/).

## Examples

- For \(n=10\) and \(a=3\), \(\varphi(10)=4\) and \(3^4=81\equiv1\pmod {10}\).
- The coprimality hypothesis is essential: \(2^{\varphi(8)}=2^4\equiv0\pmod 8\).
