Euler's totient function

Start with modulus 10\.

Its possible residue classes can be represented by

Which representatives are coprime to 10?

Any even number shares the factor 2 with 10, while 0 and 5 share a factor greater than 1 with 10\. That leaves

There are four surviving classes.

Now try modulus 6\. Its representatives are 0, 1, 2, 3, 4 and 5\. Only 1 and 5 are coprime to 6, so there are two.

This counting problem occurs so often that mathematics gives it a function of its own: \\Euler's totient function\\.

It is written using the Greek letter phi, $\varphi$.

The value $\varphi(n)$ counts the integers from 1 through $n$ that are coprime to $n$. Equivalently — and more naturally for modular arithmetic — it counts the residue classes modulo $n$ that are coprime to $n$.

Thus

and

(There are several standard ways to choose representatives for residue classes. Using $0,1,\ldots,n-1$ or using $1,2,\ldots,n$ gives the same totient count. What matters is the modular classes being counted, not which representative we write down.)

The totient becomes particularly useful when we organise prime numbers into modular lanes.

Modulo 6, only two of the six classes are coprime to the modulus:

Apart from the exceptional primes 2 and 3, larger primes must live in those two classes.

Modulo 30,

and eight of its thirty residue classes are coprime to 30:

Modulo 210,

and

This is why turn modulus 210 creates such a striking structure in the Prime Spring. Of the 210 residue classes, 162 share at least one factor with 210\. The remaining 48 survive the divisibility tests imposed by 2, 3, 5 and 7\.

Again, surviving is not the same as being prime. The totient counts classes that are \\coprime to the modulus\\, not classes containing only prime numbers.

Once the counting idea is established, Euler's totient can be calculated directly from the distinct prime factors of $n$. If the distinct primes dividing $n$ are denoted by $p$, then

(The product symbol $\prod$ means “multiply together”. Here we take one factor $\left(1-1/p\right)$ for each distinct prime $p$ dividing $n$. Each factor accounts for the fraction of candidates removed by divisibility by that prime.)

For 30, the distinct prime divisors are 2, 3 and 5, so

This formula makes the sieve-like structure especially clear. Divisibility by 2 removes one fraction of the classes, divisibility by 3 removes another and divisibility by 5 removes another, with overlaps accounted for by the product.

Euler's totient function therefore measures more than a bare number of lanes. It tells us how much of a modular system remains after classes sharing factors with the modulus have been excluded.

That is why $\varphi(q)$ appears naturally in the study of primes in arithmetic progressions. Dirichlet's theorem identifies the residue classes coprime to $q$ as precisely the classes in which primes occur infinitely often.

A deeper result — the Prime Number Theorem for arithmetic progressions — says that, for fixed $q$, the primes become asymptotically equally distributed among those $\varphi(q)$ coprime classes, even though substantial fluctuations can remain at finite scales.

(“Asymptotically” means that this equal sharing is a statement about the long-run behaviour as we look farther and farther out among the integers. It does not say that every finite Prime Spring view contains exactly the same number of primes in every surviving lane.)

The function is named after Leonhard Euler, whose work on primes, products and infinite series helped create much of the mathematical setting from which later analytic number theory developed.

See also: coprime, greatest common divisor, residue class, modular arithmetic, prime number, Euler product, distribution of primes, Who was Leonhard Euler?, Prime Spring.