Euler's Totient Function

5 min read#number-theory

φ(n) counts the integers from 1 to n that share no factor with n — the size of the group of units that powers RSA.

Contents

Euler's Totient Function

Euler's totient function, written \varphi(n), counts how many integers from 1 to n are coprime to n — that is, share no common factor with it beyond 1. For n = 12, the integers coprime to it are 1, 5, 7, 11, so \varphi(12) = 4. These are exactly the numbers that have a multiplicative inverse in arithmetic mod $n$, which makes \varphi the quiet engine inside RSA.

Counting the coprime residues

Below, the integers 1 \dots n are arranged around a ring. Those coprime to n — sharing only a gcd of 1 — light up; the rest dim. Their count is \varphi(n).

Residues 1…n around a ring. Highlighted points are coprime to n (gcd = 1); dim points share a factor. The lit count is φ(n). Drag left↔right to change n and watch φ jump around — high for primes, low for highly composite numbers.

A product formula from the primes

You never have to count one by one. The totient is multiplicative — \varphi(ab) = \varphi(a)\varphi(b) whenever a and b are coprime — and for a prime power \varphi(p^k) = p^k - p^{k-1}. Combining these via the Fundamental Theorem of Arithmetic gives a clean product over the distinct primes dividing n:

\varphi(n) \;=\; n\prod_{p \mid n}\left(1 - \frac{1}{p}\right)
(1)

For n = 12 = 2^2\cdot 3: \varphi(12) = 12\left(1-\tfrac12\right)\left(1-\tfrac13\right) = 12\cdot\tfrac12\cdot\tfrac23 = 4 — matching the four points we lit up. The two special cases worth memorizing:

  • For a prime p: \varphi(p) = p - 1, since every smaller number is coprime to a prime.
  • For two primes: \varphi(pq) = (p-1)(q-1) — the exact quantity RSA needs.
φ(n) for n = 9…16
The totient spikes at primes (φ(11)=10, φ(13)=12 — one less than n) and dips for numbers rich in small factors (φ(12)=4). It is jagged, not smooth — a direct readout of n's factor structure.

Euler's theorem and RSA

The reason \varphi rules cryptography is Euler's theorem, the generalization of Fermat's Little Theorem to any modulus:

a^{\varphi(n)} \equiv 1 \pmod{n} \qquad\text{whenever } \gcd(a, n) = 1.

This says the coprime residues, under multiplication, form a group of size \varphi(n), so raising to that power returns to the identity. RSA chooses its public and private exponents e, d so that ed \equiv 1 \pmod{\varphi(n)}; Euler's theorem then guarantees m^{ed} \equiv m, so decryption perfectly undoes encryption.

If p and q are distinct primes, what is φ(pq)?

See also