Fermat and Euler's Theorem: powers mod n go round a cycle

The idea: powers mod n go round a cycle

Take a number a and keep multiplying by it, working mod n: a, a², a³, … Each power is one of the n remainders 0 … n − 1, so sooner or later a value comes back, and from then on the powers repeat. On a clock with n hours the powers run round a cycle. The powers of 3 mod 7 are 3, 2, 6, 4, 5, 1, and the next one is 3 again (Demo: Fermat, powers of 3 mod 7).

Whenever a shares no factor with n, the cycle passes through 1. The first k with a^k ≡ 1 is the order of a mod n. 3 has order 6 mod 7, and 2 has order 3 (2, 4, 1) (Demo: shorter cycle, powers of 2 mod 7).

Euler's totient φ(n)

Euler's totient φ(n) counts the numbers 1 … n − 1 that are coprime to n, meaning gcd(a, n) = 1. For n = 15 they are 1, 2, 4, 7, 8, 11, 13, 14, so φ(15) = 8 (Demo: Euler's totient φ(15) = 8). On the canvas these are the blue rows of the table.

n	factors	coprime numbers	φ(n)
7	prime	1, 2, 3, 4, 5, 6	7 − 1 = 6
10	2·5	1, 3, 7, 9	1·4 = 4
12	2²·3	1, 5, 7, 11	2·2 = 4
15	3·5	1, 2, 4, 7, 8, 11, 13, 14	2·4 = 8

For a prime p, every number below it counts: φ(p) = p − 1. For two different primes, φ(p·q) = (p − 1)(q − 1). Finding the factors is the hard part; see Prime Factorization.

Euler's theorem

Euler's theorem: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). The reason is that the order of a always divides φ(n). The powers of a form a cycle of length d inside the φ(n) coprime numbers. Multiplying that cycle by any other coprime number gives another cycle of the same length that does not overlap it, so the coprime numbers split into equal blocks of size d. Then φ(n) = d·j, and a^φ(n) = (a^d)^j ≡ 1^j = 1.

The powers of 2 mod 15 are 2, 4, 8, 1: order 4, and 4 divides 8, so 2⁸ ≡ 1 (Demo: Euler, powers of 2 mod 15). The full power table shows it for every row at once: column k = φ(n) holds a 1 in every blue row (Demo: the full power table mod 15).

A useful consequence: exponents can be reduced mod φ(n). 2¹⁰⁰ mod 15 = 2^{100 mod 8} = 2⁴ ≡ 1. For computing big powers quickly, see Modular Exponentiation and Toy RSA.

Fermat's little theorem

When n = p is prime, φ(p) = p − 1 and Euler's theorem becomes Fermat's little theorem: if p does not divide a, then a^{p − 1} ≡ 1 (mod p). Mod 7 every row of the table has a 1 in column 6. Fermat stated it in 1640; Euler proved it and extended it to any n in 1763.

The theorem gives a quick test for primes: if 2^{n − 1} mod n is not 1, then n is certainly not prime. 2¹⁴ mod 15 = 4, so 15 is composite, with no factoring needed. The converse fails for a few numbers (341 = 11·31 passes for base 2), which is why real tests such as Miller–Rabin add more checks.

When gcd(a, n) > 1

If a shares a factor g > 1 with n, every power of a is a multiple of g, even after reducing mod n, and 1 is not. So the powers still fall into a loop, but the loop never contains 1. The powers of 2 mod 12 are 2, 4, 8, 4, 8, … (Demo: no 1 when gcd > 1 (2 mod 12)). That is why Euler's theorem needs gcd(a, n) = 1; the grey rows of the table have no green cells. The gcd itself comes from Euclid's algorithm.

Why RSA decryption works

RSA picks n = p·q and two exponents with e·d ≡ 1 (mod φ(n)), that is e·d = 1 + j·φ(n). Encrypting is c = m^e mod n and decrypting is c^d mod n. By Euler's theorem:

c^d = m^(e·d) = m^(1 + j·φ(n)) = m · (m^φ(n))^j ≡ m · 1^j = m   (mod n)

In powers-on-a-clock terms, decrypting walks the powers of m for e·d steps: some whole cycles plus one step, so it lands back on m. The toy key on the canvas is n = 15, φ = 8, e = d = 3, and 3·3 = 9 = 8 + 1. With m = 2, c = 2³ = 8, and 8³ = 512 ≡ 2 (Demo: why RSA decryption works (n = 15)). Mod 8 every coprime number is its own inverse, so a key this small has e = d; with the textbook key n = 3233, φ = 3120, e = 17 and d = 2753 differ.

Where d = e⁻¹ mod φ(n) comes from is animated on Extended Euclid, Modular Inverse and Toy RSA; Euler's theorem also explains why Diffie-Hellman key exchange exponents live mod p − 1. RSA decryption is often split mod p and mod q with the Chinese Remainder Theorem.

What the page leaves out

The page uses small moduli (7, 10, 12, 15) so the whole table fits. It does not cover primitive roots in general (3 is one mod 7: its order is φ(7)), Carmichael's function λ(n), which gives the smallest exponent that works for every coprime a (λ(15) = 4), or the group-theory proof through Lagrange's theorem. RSA also works for messages that share a factor with n, by the Chinese remainder theorem, and real RSA uses 2048-bit moduli, e = 65537 and random padding (OAEP); none of that is drawn here.

References

Euler's theorem (Wikipedia)

Fermat's little theorem (Wikipedia)

Euler's totient function (Wikipedia)

RFC 8017: PKCS #1 RSA Cryptography Specifications v2.2