What is the Euler Totient Function?

Imagine you have a clock with $n$ hours marked on it. You start at 0 and take steps of size $k$ — that is, you move $k$ hours forward each time. The question is: will you ever hit every single hour on the clock? Or will you get stuck in a loop that visits only some of them?

The answer depends on $k$ and $n$. If $k$ and $n$ share a common divisor greater than 1, you'll only hit a fraction of the hours. But if $k$ and $n$ are coprime (no common factor except 1), you'll eventually visit every hour. The Euler Totient Function, written $\phi(n)$, counts exactly how many numbers $k$ in the range $1 \le k \le n$ are coprime to $n$.

That's the intuition: $\phi(n)$ tells you how many "step sizes" will let you cycle through all $n$ positions on a clock.

The Precise Definition

For a positive integer $n$, the Euler Totient Function $\phi(n)$ is defined as:

Here $\gcd(k, n)$ means the greatest common divisor of $k$ and $n$. When $\gcd(k, n) = 1$, we say $k$ and $n$ are coprime or relatively prime.

Examples to Build Feel

• $\phi(1) = 1$ — by convention, 1 is coprime to itself.
• $\phi(2) = 1$ — only 1 is coprime to 2.
• $\phi(3) = 2$ — 1 and 2 are both coprime to 3.
• $\phi(4) = 2$ — 1 and 3 are coprime to 4; 2 shares a factor of 2.
• $\phi(5) = 4$ — all numbers 1 through 4 are coprime to 5.
• $\phi(6) = 2$ — only 1 and 5 are coprime to 6; 2, 3, 4 all share a factor.

Notice a pattern: for a prime $p$, every number from 1 to $p-1$ is coprime to $p$, so $\phi(p) = p-1$.

Why It Matters

The totient function is the backbone of Euler's Theorem, which says:

This result is the engine behind RSA encryption — the system that secures your online banking, messaging apps, and pretty much every password you type on the web. Without $\phi(n)$, modern cryptography as we know it would not exist.

How to Compute $\phi(n)$ Quickly

You don't have to list all numbers from 1 to $n$ and check each one. There's a formula based on the prime factorization of $n$.

If $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$, where each $p_i$ is a distinct prime, then:

Example: Compute $\phi(12)$. Factor $12 = 2^2 \cdot 3$. Then:

$\phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4$ …