Euler's Theorem

Fermat's theorem shrinks exponents for a prime modulus. Euler found the version for any modulus: replace $p - 1$ by $\varphi(n)$, the number of units. It is the theorem that makes RSA work.

Euler's theorem. If $\gcd(a, n) = 1$, then $$a^{\varphi(n)} \equiv 1 \pmod{n}.$$ For a prime, $\varphi(p) = p - 1$ and this is Fermat's theorem. As before, exponents may be reduced mod $\varphi(n)$: if $e \equiv r \pmod{\varphi(n)}$, then $a^{e} \equiv a^{r}$.

Why it works

Copy Fermat's proof, using only the units. Let $u_1, \dots, u_{\varphi(n)}$ be the units mod $n$. Multiplying each by $a$ (itself a unit) gives units again, all different (cancel $a$ with its inverse), so $au_1, \dots, au_{\varphi(n)}$ are the same units in a new order. Multiply everything: $$a^{\varphi(n)} \, u_1 \cdots u_{\varphi(n)} \equiv u_1 \cdots u_{\varphi(n)} \pmod{n}.$$ The product of units is a unit, so it cancels.

The last digit of a power of 7 cycles through 7, 9, 3, 1, a period of $\varphi(10) = 4$. So the last digit of $7^{222}$ is the last digit of $7^{2}$, since $222 = 4 \cdot 55 + 2$.

Worked example: Last digit

Find the last digit of $7^{222}$.

We want $7^{222} \bmod 10$. $\gcd(7, 10) = 1$ and $\varphi(10) = 4$.
$222 = 4 \cdot 55 + 2$, so $7^{222} \equiv 7^{2} = 49 \equiv 9$.

Answer: $9$.

Worked example: Last two digits

Find the last two digits of $3^{1000}$.

Work mod 100. $\varphi(100) = \varphi(4)\varphi(25) = 2 \cdot 20 = 40$, and $\gcd(3, 100) = 1$.
$1000 = 40 \cdot 25$, so $3^{1000} = (3^{40})^{25} \equiv 1 \pmod{100}$.

Answer: The last two digits are $01$.

Worked example: An exponent tower

Find $3^{3^{3}} \bmod 10$.

The exponent is $3^{3} = 27$. Reduce it mod $\varphi(10) = 4$: $27 \equiv 3$.
$3^{27} \equiv 3^{3} = 27 \equiv 7 \pmod{10}$.

Answer: $7$.

Worked example: Inverses from Euler

Find $5^{-1} \bmod 12$ using Euler's theorem.

$5 \cdot 5^{\varphi(12) - 1} = 5^{\varphi(12)} \equiv 1$, so $5^{-1} \equiv 5^{\varphi(12) - 1} = 5^{3}$. In general $a^{-1} \equiv a^{\varphi(n) - 1}$ for a unit $a$.
$5^{3} = 125 = 12 \cdot 10 + 5$, so $5^{-1} \equiv 5$. Check: $5 \cdot 5 = 25 \equiv 1 \pmod{12}$.

Answer: $5$.

Common mistake

Reducing the exponent mod $n$ instead of mod $\varphi(n)$, or using the theorem when $\gcd(a, n) > 1$. Mod 10, $2^{\varphi(10)} = 2^{4} = 16 \equiv 6$, not 1: the powers of 2 never reach 1 mod 10, because 2 is not a unit. When $\gcd(a, n) > 1$, factor $n$ and use the CRT, or look for the repeating pattern directly.

This theorem is the engine of RSA. If $ed \equiv 1 \pmod{\varphi(n)}$, then $ed = 1 + k\varphi(n)$, and for every unit $m$, $(m^{e})^{d} = m \cdot (m^{\varphi(n)})^{k} \equiv m$. Raising to the power $e$ scrambles $m$; raising to the power $d$ unscrambles it.

$\varphi(n)$ is a period, not always the shortest one. Mod 15, $\varphi(15) = 8$, yet $2^{4} = 16 \equiv 1$ already. The shortest period is the order of $a$, which always divides $\varphi(n)$.

Key idea

If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$, so reduce exponents mod $\varphi(n)$. Check the gcd first.

Sources and further reading

William Stein, Elementary Number Theory: Primes, Congruences, and Secrets (Springer, 2009; free online edition), chapter 2, The Ring of Integers Modulo n (Euler's theorem)

Lehman, Leighton and Meyer, Mathematics for Computer Science (MIT OpenCourseWare 6.042J), chapter on number theory: Euler's theorem

Euler's Theorem

Practice

Builds on

Leads to

Sources and further reading