Euler's Totient Function

Definition and first values

Euler's totient function φ(n), sometimes written Φ(n), is defined for positive integers n as

φ(n) = |{k : 1 ≤ k ≤ n, gcd(k, n) = 1}|

That is, φ(n) counts the integers in [1, n] that share no prime factor with n. The convention is φ(1) = 1 (the integer 1 is coprime to itself). For prime p, every integer in [1, p − 1] is coprime to p, so φ(p) = p − 1. For prime powers, φ(p^k) = p^k − p^(k − 1) = p^(k − 1)(p − 1) — every p-th integer is divisible by p and so not coprime, so we subtract them.

The first 20 values are:

n   |  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
φ(n)|  1   1   2   2   4   2   6   4   6   4  10   4  12   6   8   8  16   6  18   8

Note the irregular shape: φ(11) = 10 and φ(12) = 4. The totient drops sharply when n acquires small prime factors, because each new prime factor scales φ down by (1 − 1/p).

The closed-form formula

If n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k is the prime factorisation of n into distinct primes, then

φ(n) = n × (1 − 1/p_1)(1 − 1/p_2)...(1 − 1/p_k)
     = n × ∏_{p | n} (1 − 1/p)

where the product runs over distinct prime divisors of n.

The formula falls out of inclusion-exclusion. Let A_i be the multiples of p_i in [1, n]. There are exactly n/p_i of them. The integers not coprime to n are precisely the union of the A_i. Inclusion-exclusion gives

|A_1 ∪ ... ∪ A_k| = Σ n/p_i − Σ n/(p_i p_j) + Σ n/(p_i p_j p_l) − ...

φ(n) = n − Σ n/p_i + Σ n/(p_i p_j) − ...
     = n × (1 − 1/p_1)(1 − 1/p_2)...(1 − 1/p_k)

The product form is the same alternating sum factored back into a product, which works because the primes are pairwise coprime — the "events" of being divisible by different primes are independent.

Worked example: φ(360) = 96

Let's compute φ(360) using the closed form, then verify by other paths.

360 = 2³ × 3² × 5

Distinct prime divisors of 360: {2, 3, 5}

φ(360) = 360 × (1 − 1/2)(1 − 1/3)(1 − 1/5)
       = 360 × (1/2) × (2/3) × (4/5)
       = 360 × 8 / 30
       = 360 × 4 / 15
       = 24 × 4
       = 96

Sanity check via prime-power decomposition:

φ(2³) = 2³ − 2² = 8 − 4 = 4
φ(3²) = 3² − 3 = 9 − 3 = 6
φ(5) = 5 − 1 = 4

φ(360) = φ(2³) × φ(3²) × φ(5)   [multiplicativity]
       = 4 × 6 × 4
       = 96  ✓

Both routes give 96 — the multiplicativity of φ on coprime arguments is the same identity factored differently.

Why φ is multiplicative

The claim: if gcd(m, n) = 1, then φ(mn) = φ(m) × φ(n). The proof goes via the Chinese Remainder Theorem.

CRT establishes a bijection between residue classes mod (mn) and pairs of residue classes (mod m, mod n). An integer k is coprime to mn iff it is coprime to both m and n. So under the CRT bijection, integers coprime to mn correspond exactly to pairs (a mod m, b mod n) with gcd(a, m) = 1 and gcd(b, n) = 1. There are φ(m) choices for the first coordinate and φ(n) for the second, giving φ(mn) = φ(m) × φ(n).

Multiplicativity fails when gcd(m, n) > 1: for instance, φ(2 × 4) = φ(8) = 4 (the coprime integers are 1, 3, 5, 7), but φ(2) × φ(4) = 1 × 2 = 2. The hypothesis of coprimality is essential.

This makes φ a multiplicative arithmetic function: its value at any n is determined by its values at the prime-power factors of n. Other multiplicative functions include the divisor count d(n), the divisor sum σ(n), and the Möbius function μ(n).

Euler's theorem and RSA

The key application of φ is Euler's theorem, which generalises Fermat's little theorem to composite moduli:

If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n).

For prime n = p, φ(p) = p − 1 and Euler's theorem reduces to Fermat's: a^(p − 1) ≡ 1 (mod p). The composite case is what RSA needs.

RSA picks two large primes p, q and uses modulus n = pq, with

φ(n) = φ(p) × φ(q) = (p − 1)(q − 1)

by multiplicativity. Choose a public exponent e coprime to φ(n) (typically e = 65537 = 2^16 + 1). Compute the private exponent d as the modular inverse: d = e^(−1) mod φ(n). Then for any message m coprime to n,

m^(e × d) ≡ m^(1 + k × φ(n)) ≡ m × (m^φ(n))^k ≡ m × 1^k ≡ m (mod n)

so encryption (c = m^e mod n) followed by decryption (m = c^d mod n) recovers the original message. The whole construction rests on knowing φ(n) — which requires knowing the factorisation n = pq. An attacker who can factor n can compute φ(n) and break RSA; an attacker who can compute φ(n) directly without factoring would also break it (and could in fact recover the factorisation). The conjectural equivalence between factoring and computing φ is the security foundation.

Euler's totient vs related arithmetic functions

Function	Definition	Multiplicative	Closed form for prime power	Key application
φ(n)	Coprime integers ≤ n	Yes (coprime args)	p^(k−1)(p − 1)	RSA, Euler's theorem
σ₀(n) = d(n)	Number of divisors	Yes (coprime args)	k + 1	Divisor counting, perfect numbers
σ(n) = σ₁(n)	Sum of divisors	Yes (coprime args)	(p^(k+1) − 1)/(p − 1)	Perfect / amicable / abundant numbers
μ(n)	±1 on squarefree, else 0	Yes (coprime args)	0 if k ≥ 2, else −1	Möbius inversion, prime counting
λ(n) (Carmichael)	Smallest k with a^k ≡ 1 (mod n) for all coprime a	No, but lcm-multiplicative	p^(k−1)(p − 1) for odd p	Tighter RSA bound, often = φ(n)
π(x) (prime count)	Number of primes ≤ x	No	Not applicable	Prime number theorem
Λ(n) (von Mangoldt)	log p if n = p^k, else 0	No	log p	Analytic number theory

φ sits in the family of "totient-style" functions that count restricted residue classes; σ and d count and sum divisors; μ encodes squarefreeness with sign. Together they form the toolkit of elementary multiplicative number theory.

The divisor sum identity

One of the most-used totient identities is the divisor sum:

Σ_{d | n} φ(d) = n

Sum φ over all positive divisors of n and the result is n itself. For n = 12, divisors are 1, 2, 3, 4, 6, 12 with φ values 1, 1, 2, 2, 2, 4 — summing to 12. ✓

The combinatorial proof: classify each integer in {1, 2, ..., n} by its gcd with n. The integers with gcd(k, n) = d are exactly d × {integers coprime to n/d}, and there are φ(n/d) of them. Summing over divisors d of n covers every integer in [1, n] exactly once:

n = Σ_{d | n} φ(n/d) = Σ_{d | n} φ(d)

(the second equality is just re-indexing d ↦ n/d, which is a bijection on the divisors of n).

By Möbius inversion, the divisor sum gives a different formula for φ:

φ(n) = Σ_{d | n} μ(d) × n/d

This is sometimes faster than the closed-form product when n is small or when computing in a setting where the Möbius function is precomputed.

Where Euler's totient shows up

• RSA cryptography — key generation and decryption. Every RSA key pair (p, q, e, d) satisfies e × d ≡ 1 (mod φ(pq)) where φ(pq) = (p − 1)(q − 1). For 2048-bit RSA, p and q are ~1024-bit primes, and computing φ(n) without knowing the factorisation is conjecturally as hard as factoring. OpenSSL, BoringSSL and every TLS library leverage φ in their RSA operations billions of times per day.
• Lattice cryptography — Ring Learning With Errors. NIST's post-quantum standards Kyber and Dilithium operate in cyclotomic rings ℤ[x]/(Φ_n(x)) where Φ_n is the n-th cyclotomic polynomial of degree φ(n). The choice of n = 256, 512, 1024 with φ(n) = 128, 256, 512 sets the security level.
• Periodicity in dynamical systems — multiplicative orders. The order of a in (ℤ/n)* divides φ(n). For pseudo-random number generators of the form x_(t+1) = a × x_t mod n (multiplicative congruential generators), the period divides φ(n). The Park-Miller "minimal standard" RNG uses a = 16807, n = 2^31 − 1 (Mersenne prime), giving period n − 1 = φ(n).
• Coding theory — Reed-Muller and BCH codes. The cyclotomic-coset structure used to construct BCH codes over GF(q^φ(n)) requires knowing how φ(n) divides the multiplicative order of q. Tables of φ values directly inform code parameter selection in NASA Deep Space Network protocols.
• Music theory — equal temperament resonance. The number of distinct pitch classes producing repeating patterns in a 12-tone scale is φ(12) = 4 (the generators 1, 5, 7, 11). The musical "circle of fifths" is the cyclic group (ℤ/12)* of size φ(12), which is why moving by perfect fifths (interval = 7 semitones) cycles through all 12 notes.

Variants and extensions

• Carmichael function λ(n). The smallest exponent k such that a^k ≡ 1 (mod n) for all a coprime to n. Always divides φ(n). Equal to φ(n) when n is 1, 2, 4, p^k or 2p^k for odd prime p; otherwise strictly smaller. Some textbook RSA implementations use λ instead of φ for marginally smaller private exponents.
• Jordan's totient J_k(n). Generalises φ to count k-tuples (a_1, ..., a_k) with each a_i in [1, n] and gcd(a_1, ..., a_k, n) = 1. J_1 = φ. The closed form J_k(n) = n^k × ∏ (1 − 1/p^k). Used in counting matrix groups over finite rings.
• Dedekind's psi function ψ(n) = n × ∏ (1 + 1/p). Counts pairs (a, b) with a | n and gcd(a, b) = 1; closely related to φ via ψ(n) × φ(n)/n^2 = ∏ (1 − 1/p^2) for squarefree n. Appears in modular-form theory.
• Cyclotomic polynomial Φ_n(x). The unique monic polynomial whose roots are the primitive n-th roots of unity. It has degree φ(n), and its irreducibility over ℚ is one of the most important facts in algebraic number theory.
• Average order — 6/π². The average value of φ(n)/n over n = 1, 2, ..., N tends to 6/π² ≈ 0.6079 as N → ∞. This is "the probability that two random integers are coprime" — an unexpectedly clean appearance of π in a discrete counting problem.

Common pitfalls

• Forgetting φ(1) = 1. Every formula has to handle n = 1 carefully. The empty product convention gives φ(1) = 1, but treating it as 0 (the count of integers in [1, 1] coprime to 1) is wrong because gcd(1, 1) = 1.
• Assuming φ is fully multiplicative. φ is multiplicative for coprime arguments only. φ(mn) = φ(m) × φ(n) requires gcd(m, n) = 1. Plugging non-coprime arguments into the multiplicative identity is a common student mistake.
• Computing φ(n) without knowing the factorisation. Beyond very small n, no efficient algorithm is known. For RSA-scale n (thousands of bits), computing φ(n) directly is conjecturally as hard as factoring n, which is why RSA's security depends on factoring being hard.
• Conflating φ(n) with the totatives themselves. φ(n) is the count, not the set. The set of totatives (the integers in [1, n] coprime to n) is often denoted T(n) or U(ℤ/n).
• Confusing the closed-form factors. The product is over distinct primes dividing n, not over their multiplicities. φ(72) = 72 × (1 − 1/2) × (1 − 1/3), not 72 × (1 − 1/2)³ × (1 − 1/3)² — the multiplicities are absorbed into the leading factor n.