Euler's Totient Function: Counting the Numbers That Share Nothing With n

For any positive integer $n$, how many integers from $1$ to $n$ share no common factor with $n$ other than $1$? This is the question Leonhard Euler asked in the 1760s, and the function he defined to answer it — denoted $\varphi(n)$ — has turned out to be one of the most useful tools in number theory.

The first few values of the Euler totient function are straightforward to compute. For $n = 6$, the integers $1, 2, 3, 4, 5, 6$ have $\gcd$‘s $1, 2, 3, 2, 1, 6$ with $6$. Only $1$ and $5$ are coprime to $6$, so $\varphi(6) = 2$. For $n = 10$, the coprime numbers up to $10$ are $\{1, 3, 7, 9\}$, so $\varphi(10) = 4$. For a prime $p$, every integer from $1$ to $p - 1$ is coprime to $p$, so $\varphi(p) = p - 1$.

What at first appears to be an unremarkable counting function turns out to govern the structure of modular arithmetic, the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$, the RSA encryption algorithm that secures the web, and a great deal of analytic number theory. This article is about $\varphi(n)$, what makes it useful, and how its properties cascade through pure and applied mathematics.

The formula

For prime powers, the totient is easy. Consider $\varphi(p^k)$ where $p$ is prime. The integers from $1$ to $p^k$ that share a factor with $p^k$ are exactly the multiples of $p$: namely $p, 2p, 3p, \dots, p^{k-1}\cdot p = p^k$, a total of $p^{k-1}$ numbers. So $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$.

For general $n$, the totient is multiplicative: if $\gcd(m, n) = 1$, then $\varphi(mn) = \varphi(m)\varphi(n)$. The proof uses the Chinese Remainder Theorem: every integer mod $mn$ corresponds uniquely to a pair of integers mod $m$ and mod $n$, and the pair is coprime to $mn$ exactly when each component is coprime to its respective modulus.

Combining these two facts, if $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ is the prime factorisation, then

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

The product runs over all distinct primes dividing $n$. For $n = 60 = 2^2 \cdot 3 \cdot 5$:

$\varphi(60) = 60 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} \cdot \tfrac{4}{5} = 16.$

A quick check: among $1, 2, \dots, 60$, the coprime numbers are $1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59$ — exactly $16$ values.

Erratic behaviour

For all that the closed-form formula is clean, the function $\varphi(n)$ behaves erratically as $n$ varies. It depends only on the prime structure of $n$, not on its size, so numbers with many small prime factors have small totients and numbers that are prime (or products of large primes) have nearly the maximum possible totient. The plot below shows $\varphi(n)/n$ for $n = 1, 2, \dots, 30$.

The pattern is exactly what the formula predicts. Prime numbers $p$ have $\varphi(p)/p = (p-1)/p$, which approaches $1$ for large primes — almost every integer below $p$ is coprime to it. Smooth numbers with many small prime factors — like $n = 30 = 2 \cdot 3 \cdot 5$, which has $\varphi(30)/30 = (1/2)(2/3)(4/5) = 4/15 \approx 0.267$ — have very small totients relative to their size. The function $\varphi(n)/n$ thus encodes how “prime-like” or “composite-like” $n$ is, in a precise multiplicative sense.

Euler’s theorem and modular arithmetic

The totient function’s most important property links it to the multiplicative structure of integers modulo $n$. Euler’s theorem (1763) states:

If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$.

This generalises Fermat’s little theorem ($a^{p-1} \equiv 1 \pmod p$ for prime $p$), which is the special case $\varphi(p) = p - 1$. The proof is short: the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^*$ of units modulo $n$ has exactly $\varphi(n)$ elements, and by Lagrange’s theorem, every element raised to the power of the group’s order gives the identity. So $a^{\varphi(n)} = 1$ in $(\mathbb{Z}/n\mathbb{Z})^*$, i.e., $\equiv 1 \pmod n$ over integers.

This deceptively simple result is the engine of all of modular exponentiation. When you need to compute $a^N \pmod n$ for some huge integer $N$, you don’t need to compute the full power — you can replace $N$ by $N \bmod \varphi(n)$ and get the same answer. This is what makes large-exponent computations tractable in cryptography.

Connection to RSA

The most consequential application of the totient function is in RSA encryption, the cornerstone of public-key cryptography. Here is how it works in outline.

Choose two large prime numbers $p$ and $q$, and let $n = pq$. By the multiplicativity of $\varphi$, $\varphi(n) = (p-1)(q-1)$. Choose an integer $e$ that is coprime to $\varphi(n)$ — this is the encryption exponent, and it is published openly along with $n$. Privately, compute the multiplicative inverse of $e$ modulo $\varphi(n)$, call it $d$ — this is the decryption exponent, kept secret.

To encrypt a message $m$, compute $c = m^e \pmod n$. To decrypt, compute $m = c^d \pmod n$. The fact that decryption recovers $m$ follows from Euler’s theorem: $c^d = m^{ed} \equiv m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \pmod n$, since $m^{\varphi(n)} \equiv 1$ for $m$ coprime to $n$.

The security of the protocol rests on the difficulty of computing $\varphi(n)$ from $n$ alone. If an attacker could factor $n = pq$, they would immediately know $\varphi(n) = (p-1)(q-1)$ and could invert the encryption. But integer factorisation of large semiprimes (products of two large primes) is currently infeasible: for $n$ of around $2048$ bits, factorisation would require thousands of years on the most powerful computers in existence. So the totient function — defined as a simple count in 1763 — is the mathematical lock that protects every secure HTTPS connection, every encrypted email, every bank transaction on the web.

Other appearances

Beyond cryptography, the totient appears in many corners of number theory.

Möbius inversion. The totient satisfies $\sum_{d \mid n} \varphi(d) = n$, an identity discovered by Gauss. This is one of the simplest applications of Möbius inversion, a technique for inverting summation identities in multiplicative number theory.

Cyclotomic polynomials. The $n$-th cyclotomic polynomial $\Phi_n(x)$ — whose roots are the primitive $n$-th roots of unity — has degree exactly $\varphi(n)$. This connects the totient to Galois theory of cyclotomic field extensions.

Asymptotic density. The average value of $\varphi(n)/n$ over $n \leq N$ tends to $6/\pi^2 \approx 0.6079$ as $N \to \infty$ — the same number $6/\pi^2$ that gives the probability that two random integers are coprime. The connection runs through the Riemann zeta function: $\varphi$ is a multiplicative function whose Dirichlet series is $\zeta(s-1)/\zeta(s)$, and the asymptotic average comes from evaluating this at $s = 2$.

Counting solutions in modular equations. Whenever you want to count the number of solutions of a polynomial equation modulo $n$, the totient often appears in the answer.

A small counting function with enormous reach

Euler defined $\varphi(n)$ as a piece of pure curiosity: how many numbers below $n$ are coprime to it? What he could not have anticipated is that his counting function would, two and a half centuries later, sit at the foundation of a global infrastructure for secure communication. Every time you visit a website over HTTPS, every time you send an encrypted message, every time you authenticate with a public key, the totient function is doing its work behind the scenes.

The beauty of the function is twofold. Pure beauty: a simple count gives a multiplicative function with a clean closed-form formula and an elegant connection to the group structure of modular arithmetic. Applied beauty: the same function provides the mathematical scaffolding for one of the most widely-deployed cryptographic protocols in human history. The gap between definition and impact is enormous, and one of the most striking demonstrations of how often the apparently abstract questions of number theory turn out to underwrite the practical machinery of the modern world.

Euler counted numbers in 1763. Two centuries later, his function was protecting the web. That is what a great mathematical concept looks like.

Frequently asked

What does the word 'totient' actually mean?

It comes from Latin tot, meaning 'so many' — the same root as English 'total'. The mathematician James Joseph Sylvester coined the English word 'totient' in 1879 specifically for Euler's function, describing it as 'the count of numbers that are totient (i.e., that constitute a complete coprime set) with n'. The Greek letter φ (phi) used to denote the function was Gauss's choice in his 1801 Disquisitiones Arithmeticae, where he gave the first systematic treatment of modular arithmetic and the function's properties.

How do you actually compute φ(n)?

Factor n into primes. For each prime p that divides n, the contribution to φ(n) is (p − 1)/p. Multiply n by all these fractions: φ(n) = n · ∏ (1 − 1/p), where the product runs over all distinct primes p dividing n. For example, φ(60) = 60 · (1 − 1/2)(1 − 1/3)(1 − 1/5) = 60 · 1/2 · 2/3 · 4/5 = 16. Factoring n is the hard part; once you have the factorisation, computing φ(n) is essentially free.

What is Euler's theorem?

If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). This generalises Fermat's Little Theorem (a^(p−1) ≡ 1 mod p for prime p, since φ(p) = p − 1). Euler's theorem is the foundation of modular exponentiation in cryptography: when you exponentiate a number to a large power modulo n, the exponent can be reduced modulo φ(n) without changing the result. This is exactly what makes the RSA algorithm tractable: encryption and decryption keys live in arithmetic modulo φ(n), and the whole security argument rests on the difficulty of computing φ(n) without knowing the prime factorisation of n.

How does the totient relate to RSA encryption?

In RSA, you publish a number n that is the product of two large primes p and q. The encryption exponent e is public, and the decryption exponent d is computed as the multiplicative inverse of e modulo φ(n) = (p − 1)(q − 1). To decrypt, an attacker would need to recover d, which requires knowing φ(n), which requires factoring n. Since factoring large semiprimes is currently infeasible, RSA is secure. The whole protocol turns on Euler's totient function and the difficulty of computing it from n alone.

Continue reading

Person

Leonhard Euler

Swiss mathematician of extraordinary range and productivity. Formulated Euler's identity, founded graph theory, and produced more mathematical output than any mathematician before or since.

Read →Blog

RSA Encryption: How Two Primes Lock the World's Secrets

Pick two large primes. Multiply them. Publish the product. Every HTTPS connection and every encrypted message rests on the fact that nobody can factor that product back into the two primes.

Read →Blog

Perfect Numbers and Mersenne Primes: A Twenty-Three-Centuries-Old Hunt

A perfect number equals the sum of its proper divisors. Euclid in 300 BCE showed how to make them from a special prime. Twenty-three centuries later, 52 are known — and no more proven to exist.

Read →