Euler's Theorem (Generalized Fermat) — Mathematics Knowledge System

Overview

Euler's theorem, proved by Leonhard Euler in 1736 (the same paper that contains his proof of Fermat's little theorem), extends Fermat's result from prime moduli to any modulus n: for a coprime to n, a raised to the totient φ(n) is congruent to 1 modulo n. When n happens to be prime p, φ(p) = p − 1 and the statement collapses to Fermat's little theorem exactly, which is why Euler's theorem is often called its generalization. The practical payoff is enormous: it lets you reduce huge exponents modulo φ(n) instead of modulo n itself, which is exactly the trick that makes RSA decryption work (choosing exponents so that raising to them and back is the identity map modulo φ(n)) and is the standard tool for computing a^k mod n by hand or by fast exponentiation software when k is astronomically large.

Intuition

The residues modulo n that are coprime to n form a group under multiplication (the unit group), and that group has exactly φ(n) elements. A basic fact of finite group theory (Lagrange's theorem for groups) says raising any element to the power of the group's size always returns the identity — here, 1. So a^φ(n) ≡ 1 (mod n) is really just 'raise any element of a size-φ(n) group to that size and you land back on the identity,' the same mechanism that powered the pairing/permutation argument in Fermat's little theorem, just generalized from the prime residue group (size p − 1) to the unit group modulo any n (size φ(n)).

Formal Definition

Definition

Let n ≥ 1 and let a be an integer with gcd(a, n) = 1. Let φ(n) denote Euler's totient function.

\gcd(a,n) = 1 \ \Rightarrow\ a^{\varphi(n)} \equiv 1 \pmod{n}

Euler's theorem

a^{k} \equiv a^{k \bmod \varphi(n)} \pmod{n} \quad \text{(when } \gcd(a,n)=1\text{)}

Exponent reduction consequence

n = p \text{ prime} \ \Rightarrow\ \varphi(p) = p - 1, \text{ recovering } a^{p-1} \equiv 1 \pmod p

Fermat's little theorem as the prime special case

Worked Examples

φ(10) = φ(2)·φ(5) = 1·4 = 4.
$\varphi(10) = 4$
Compute 3^4.
$3^{4} = 81$
81 = 8·10 + 1, so 81 ≡ 1 (mod 10), confirming the theorem.
$81 \equiv 1 \pmod{10}$

Answer: 3^4 ≡ 1 (mod 10). ✓

Practice Problems

Difficulty 4/10

Compute 64 mod 9.

Difficulty 7/10

Use Euler's theorem to compute 3^100 mod 10 by reducing the exponent modulo φ(10) = 4.

Difficulty 5/10

Explain why Euler's theorem reduces exactly to Fermat's little theorem when n is prime.

Quiz

Summary

For gcd(a, n) = 1, a^φ(n) ≡ 1 (mod n) — Euler's generalization of Fermat's little theorem to any modulus.
The proof uses the fact that the φ(n) units modulo n form a group, and raising to the group's order returns the identity.
Consequence: exponents can be reduced modulo φ(n), the mechanism behind RSA and efficient modular exponentiation.

References

WebsiteWikipedia — Euler's theorem