Euler's Totient Function — Definition, Formula & Examples

Euler's totient function, written

\phi(n)

, counts how many integers from

1

n

share no common factor with

n

other than

1

. For example,

\phi(12) = 4

because only

1, 5, 7, 11

are coprime to

12

For a positive integer $n$ , Euler's totient function is defined as $\phi(n) = |\{k \in \mathbb{Z} : 1 \le k \le n,\; \gcd(k, n) = 1\}|$ . The function is multiplicative: if $\gcd(a,b) = 1$ , then $\phi(ab) = \phi(a)\phi(b)$ .

Key Formula

\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)

Where:

$n$ = A positive integer
$p$ = Each distinct prime factor of n

How It Works

To compute

\phi(n)

, first find the prime factorization of

n

. Then apply the product formula, which multiplies

n

by a factor of

(1 - 1/p)

for each distinct prime

p

dividing

n

. For any prime

p

\phi(p) = p - 1

since every integer less than a prime is coprime to it. The multiplicative property lets you break the computation into smaller pieces when the factorization has multiple distinct primes.

Worked Example

Problem: Compute φ(36).

Factor: Find the prime factorization of 36.

36 = 2^2 \times 3^2

Apply the formula: The distinct primes dividing 36 are 2 and 3. Substitute into the product formula.

\phi(36) = 36 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3}

Simplify: Multiply the factors together.

\phi(36) = 36 \cdot \frac{2}{6} = 12

Answer: φ(36) = 12. There are 12 integers between 1 and 36 that are coprime to 36.

Visualization

Why It Matters

Euler's totient function is central to Euler's theorem:

a^{\phi(n)} \equiv 1 \pmod{n}

when

\gcd(a,n)=1

. This theorem underpins the RSA cryptosystem, where

\phi(n)

determines the relationship between public and private encryption keys. It also appears throughout number theory in counting problems, group theory (the order of the multiplicative group mod

n

), and the Möbius inversion formula.

Common Mistakes

Mistake: Multiplying by (1 − 1/p) for every prime power in the factorization instead of each distinct prime once.

Correction: The product runs over distinct primes only. For n = 36 = 2² × 3², you use (1 − 1/2) and (1 − 1/3), not four separate factors.