Euler's Totient Theorem

Compute huge powers mod n by reducing exponents modulo (n).

The idea

Theorem (Euler's theorem).

Let $\varphi(n)$ be the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}.$

Fermat's little theorem is the special case of a prime modulus, where $\varphi(p) = p - 1$. Euler's theorem extends it to every modulus: the exponent that returns $a$ to $1$ is the number of invertible residues, whether $n$ is prime, a prime power, or a product of several primes.

The theorem reduces exponents. Since $a^{\varphi(n)} \equiv 1$, multiplying by a factor of $a^{\varphi(n)}$ changes nothing modulo $n$.

Corollary.

If $\gcd(a, n) = 1$, then for every $k \ge 0$, $a^{k} \equiv a^{k \bmod \varphi(n)} \pmod{n}.$

A power with an enormous exponent collapses to one small enough to evaluate by hand. The first step in such a problem is to compute $\varphi(n)$ from the prime factorization: apply $\varphi(p^{k}) = p^{k} - p^{k-1}$ to each prime power and multiply the results.

Ways to work on it

• Walkthrough. Build (n), then reduce exponents with a^ (n) 1.
• Proof. Prove a^ (n) 1 by permuting the units mod n.
• Practice. Reduce a large power modulo n using (n).
• Hardest. Find the last two digits of a large power.

Not sure where to start? Take the ten-question placement test.