Euler's Theorem - Knowlpedia

Euler's theorem. Let $n\ge 1$ and $a\in\mathbb Z$ . If the greatest common divisor 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 applied to the 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.

Examples