Euler's Totient Function

What is φ(n)?

Euler’s totient function counts how many numbers from 1 to n are coprime with n.

We write it as $\phi(n)$ — that’s the Greek letter “phi”.

Remember: two numbers are coprime when they share no common factors.

Example: φ(10)

Which numbers from 1 to 10 are coprime with 10?

$1, 2, 3, 4, 5, 6, 7, 8, 9, 10$

We need to find which ones share no common factors with 10.

What are 10’s factors? $10 = 2 \times 5$

So any number divisible by 2 or 5 shares a factor with 10 — not coprime.

Go through each number:

• 1 — coprime (shares nothing with anything)
• 2 — divisible by 2, shares a factor
• 3 — coprime
• 4 — divisible by 2, shares a factor
• 5 — divisible by 5, shares a factor
• 6 — divisible by 2, shares a factor
• 7 — coprime
• 8 — divisible by 2, shares a factor
• 9 — coprime
• 10 — divisible by both, shares factors

What’s left: 1, 3, 7, 9

φ(10) = 4

The Shortcut

Counting works, but there’s a faster way.

When n is a product of two primes:

$\phi(p \times q) = (p - 1) \times (q - 1)$

Subtract 1 from each prime, multiply.

For a Single Prime

What if n is just one prime?

Every number from 1 to p-1 is coprime with p. (A prime has no factors to share.)

$\phi(p) = p - 1$

Example: φ(7)

7 is prime. Numbers 1, 2, 3, 4, 5, 6 are all coprime with 7.

$\phi(7) = 7 - 1 = 6$