Here is a question that sounds almost too simple to matter: for a number n, how many of the whole numbers from 1 to n share no common factor with it? That count is called Euler's totient function, written \varphi(n) — and it turns out to be the secret ingredient inside one of the most important pieces of technology on the internet: RSA encryption. Every time your browser sets up a secure connection, a computer somewhere is quietly generating keys built from a value of \varphi(n).

Formally, \varphi(n) counts the numbers coprime to n — the size of the set of "invertible" residues, and one of the most-used functions in all of number theory.

Definition

For n = 12, the numbers coprime to it are 1, 5, 7, 11 — four of them — so \varphi(12) = 4. These are exactly the residues with a modular inverse, the "units" of \mathbb{Z}_n.

A smaller sanity check: for n = 10, run through 1, 2, \dots, 10 and keep only the ones sharing no factor with 10 = 2 \times 5. That leaves 1, 3, 7, 9 — every even number and the multiple of 5 are out — so \varphi(10) = 4. Direct counting like this always works; it just gets slow for large n, which is exactly why the formula below is worth having.

A formula from the prime factorisation

Two facts make \varphi easy to compute:

• For a prime p: every number 1, \dots, p-1 is coprime to it, so \varphi(p) = p - 1. For a prime power, \varphi(p^k) = p^k - p^{k-1} = p^{k}\!\left(1 - \tfrac1p\right) — every multiple of p below p^k is thrown out, and nothing else is.
• It is multiplicative for coprime factors: if \gcd(m, n) = 1 then \varphi(mn) = \varphi(m)\varphi(n) — a consequence of the Chinese Remainder Theorem.

Putting them together gives the product formula over the distinct primes dividing n:

Where the formula comes from

You don't have to take the product formula on faith — it falls straight out of counting what gets excluded. Start with all n numbers from 1 to n, then throw out the ones that share a factor with n, one prime at a time.

Throwing out every multiple of a prime p \mid n removes a fraction \tfrac1p of the numbers, leaving a fraction 1 - \tfrac1p behind. Because a number can be divisible by several of n's prime factors at once, naively multiplying the leftover fractions for each prime would double-remove the overlaps — but that's exactly what an inclusion–exclusion argument handles cleanly, and it settles out to precisely the product n\prod_{p \mid n}\left(1 - \tfrac1p\right) above, with every overlap accounted for exactly once. It's the same bookkeeping idea as the multiplicative property: each prime factor's "exclusion zone" is independent of the others, which is only true because distinct primes never share factors with each other.

Worked examples

1. Compute \varphi(12) two ways. Counting directly: among 1, 2, \dots, 12, the ones coprime to 12 = 2^2 \cdot 3 are 1, 5, 7, 11 — everything else shares a factor of 2 or 3 with it. That's 4 survivors, so \varphi(12) = 4. The formula agrees:

2. Compute \varphi(13), a prime. Since 13 is prime, every number from 1 to 12 is coprime to it (none of them can share a factor with a prime, since a prime's only factors are 1 and itself). So \varphi(13) = 13 - 1 = 12 — this is why \varphi(p) = p-1 for every prime p, with no exceptions.

3. Verify the multiplicative shortcut. Split 12 = 3 \times 4, and note \gcd(3,4) = 1 — they share no factor. Separately, \varphi(3) = 2 (the numbers 1, 2) and \varphi(4) = 2 (the numbers 1, 3). Multiplying: \varphi(3)\varphi(4) = 2 \times 2 = 4 — exactly the \varphi(12) = 4 found above. The shortcut works because 3 and 4 are coprime; the next vignette shows what happens when they aren't.

4. A number with three prime factors: \varphi(30). Since 30 = 2 \times 3 \times 5, the product formula runs over all three primes:

The multiplicative shortcut agrees, applied twice (each step splitting off a factor coprime to the rest): \varphi(30) = \varphi(2)\varphi(3)\varphi(5) = 1 \times 2 \times 4 = 8. Only 8 of the 30 numbers from 1 to 30 — namely 1, 7, 11, 13, 17, 19, 23, 29 — dodge every one of 2, 3, and 5.

Visualising \varphi(n)

Plot \varphi(n) for the first thirty values of n and it looks nothing like a smooth curve — it jitters up and down, with primes forming a distinctive upper ridge (since \varphi(p) = p - 1 is as large as the totient ever gets below p) while numbers with lots of small prime factors dip low.

Despite all that jitter, \varphi(n)/n settles into a very tidy long-run average: about 6/\pi^2 \approx 0.608. That's the same constant that answers a completely different-sounding question — "if you pick two whole numbers at random, what is the chance they share no common factor?" — because both questions are, underneath, asking how often a random pair dodges every prime at once.

The case that builds RSA

The single most important value: for two distinct primes p and q,

Anyone who knows p and q can compute this instantly; anyone who knows only the product n = pq cannot — computing \varphi(n) is as hard as factoring. That asymmetry is precisely the trapdoor RSA is built on, via Euler's theorem.