Engineering / Mathematics — Integer Foundations
Euler's Phi Function
Euler's totient function: its definition, multiplicativity, closed form from the prime factorisation, and computational status.
Executive summary
Euler's phi function counts the integers up to n that are coprime to n, equivalently the order of the group of units modulo n. It is the single most important arithmetic function in this subject.
Its closed form follows from multiplicativity and the Chinese remainder theorem, and computing it is provably as hard as factoring — a fact RSA depends on directly.
Learning objectives
- Define phi and compute it from a prime factorisation.
- Prove multiplicativity via the Chinese remainder theorem.
- Explain the equivalence between computing phi and factoring.
01Definition and first values
Euler's phi function
φ(n) is the number of integers k with 1 ≤ k ≤ n and gcd(k, n) = 1.
Equivalently, φ(n) = |Z_n*|, the order of the group of units modulo n.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(n) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 4 |
For a prime p, every one of 1, ..., p−1 is coprime to p, so φ(p) = p − 1. For a prime power p^k, the integers not coprime to it are exactly the multiples of p, of which there are p^{k−1}, giving φ(p^k) = p^k − p^{k−1}.
02Multiplicativity and the closed form
Multiplicativity
If gcd(m, n) = 1 then φ(mn) = φ(m)φ(n).
The proof is the Chinese remainder theorem restricted to units. The isomorphism Z_{mn} ≅ Z_m × Z_n carries units to pairs of units, because an element is invertible in a product ring exactly when each component is. Counting both sides gives the result.
Closed form
If n = p₁^e₁ ··· pₖ^eₖ then
φ(n) = n · ∏(1 − 1/pᵢ).
The product is over distinct primes dividing n, and the exponents do not appear except through n itself. This is why φ(n) depends on which primes divide n more sensitively than on their multiplicities.
03Computing phi is as hard as factoring
The closed form requires the factorisation. The question is whether some other route might compute φ(n) without it, and the answer is essentially no.
Equivalence for semiprimes
For n = pq with p, q distinct primes, knowledge of φ(n) yields the factorisation in polynomial time.
Reason. φ(n) = (p−1)(q−1) = n − p − q + 1, so p + q = n − φ(n) + 1. With the sum and product of p and q known, both are roots of a known quadratic.
- Given the factorisation
O(len(n)²)Apply the closed form directly - Given n only
SubexponentialRequires factoring n first - Given n and φ(n)
O(len(n)²)Recovers the factorisation
04Frequently asked questions
Is φ(1) = 1 or 0?
It is 1. The single integer in range is 1 itself, and gcd(1,1) = 1, so it counts. This also makes the closed form and multiplicativity work without exception at n = 1.
Why is φ(n) always even for n > 2?
Because the units modulo n come in pairs {a, n−a}, which are distinct unless a = n−a, requiring n = 2a and forcing gcd(a,n) = a > 1 for n > 2. So no unit is its own pair-partner and the count is even.
Is there a formula for φ that avoids factoring?
None is known, and finding one would break RSA. The best known methods for computing φ(n) for general n proceed by factoring n, at subexponential cost.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 24-25.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.