Last updated: 2026-07-13

Definition

Euler's totient function $\varphi(n)$ counts how many integers from $1$ to $n$ are coprime to $n$ — that is, how many share no common factor with $n$ other than $1$. Two integers are coprime when their greatest common divisor is $1$.

For example, $\varphi(9) = 6$: among $1, 2, \dots, 9$, the values $1, 2, 4, 5, 7, 8$ are coprime to $9$, while $3, 6, 9$ are not.

The function is named after Leonhard Euler, who introduced it in 1763. It is sometimes written $\phi(n)$ and is also called the phi function.

The Product Formula

You never need to test every integer up to $n$. Once $n$ is broken into its distinct prime factors, the totient follows directly:

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

The product runs over the distinct primes dividing $n$ — the exponents do not appear. Each prime $p$ removes the fraction $1/p$ of the numbers (those divisible by $p$), and because the primes act independently, the fractions multiply.

Worked example — n = 36. The prime factorization is $36 = 2^2 \cdot 3^2$, so the distinct primes are $2$ and $3$:

$\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

The twelve integers coprime to $36$ are $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$.

Primes and Prime Powers

Two building-block cases make the formula easy to reason about:

• Prime $p$: every integer from $1$ to $p - 1$ is coprime to $p$, so $\varphi(p) = p - 1$. For instance $\varphi(7) = 6$.
• Prime power $p^k$: the only integers not coprime to $p^k$ are the multiples of $p$, of which there are $p^{k-1}$. Hence

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$

So $\varphi(8) = \varphi(2^3) = 2^2(2 - 1) = 4$ and $\varphi(27) = \varphi(3^3) = 3^2(3 - 1) = 18$.

Multiplicativity

The totient is multiplicative: whenever $m$ and $n$ are coprime,

$\varphi(mn) = \varphi(m)\,\varphi(n)$

This is why the product formula works — write $n$ as a product of prime powers, apply $\varphi(p^k) = p^{k-1}(p-1)$ to each, and multiply. For example, $36 = 4 \cdot 9$ with $\gcd(4, 9) = 1$, so $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$.

Note the coprime condition: $\varphi(mn) = \varphi(m)\varphi(n)$ can fail when $m$ and $n$ share a factor. For instance $\varphi(2 \cdot 2) = \varphi(4) = 2$, not $\varphi(2)\varphi(2) = 1$.

Euler's Theorem

The totient governs modular exponentiation. Euler's theorem states that if $\gcd(a, n) = 1$, then

$a^{\varphi(n)} \equiv 1 \pmod{n}$

This generalizes Fermat's little theorem ($a^{p-1} \equiv 1 \pmod p$ for a prime $p$), which is just the special case $n = p$, where $\varphi(p) = p - 1$.

Example. Take $a = 3$, $n = 10$. Here $\varphi(10) = 4$, so $3^4 = 81 \equiv 1 \pmod{10}$ — and indeed $81$ ends in $1$. The theorem lets you reduce huge exponents modulo $\varphi(n)$ before computing.

Application to RSA

RSA public-key cryptography is built directly on the totient. A modulus is formed from two large primes, $n = p \cdot q$, giving

$\varphi(n) = (p - 1)(q - 1)$

The public exponent $e$ and private exponent $d$ are chosen so that $e \cdot d \equiv 1 \pmod{\varphi(n)}$. Euler's theorem then guarantees that decrypting reverses encrypting: $(m^e)^d \equiv m \pmod n$.

The security rests on a gap: anyone can publish $n$, but computing $\varphi(n) = (p-1)(q-1)$ requires knowing $p$ and $q$. Recovering those from $n$ alone is factoring a large semiprime — believed to be computationally infeasible for suitably large primes. In fact, knowing $\varphi(n)$ is equivalent to factoring $n$.

Worked Examples

$n$	Factorization	Product form	$\varphi(n)$
$10$	$2 \cdot 5$	$10\,(1 - \tfrac12)(1 - \tfrac15)$	$4$
$12$	$2^2 \cdot 3$	$12\,(1 - \tfrac12)(1 - \tfrac13)$	$4$
$36$	$2^2 \cdot 3^2$	$36\,(1 - \tfrac12)(1 - \tfrac13)$	$12$
$100$	$2^2 \cdot 5^2$	$100\,(1 - \tfrac12)(1 - \tfrac15)$	$40$
$101$	$101$ (prime)	$101\,(1 - \tfrac{1}{101})$	$100$

Special Cases

• $n = 1$: by convention $\varphi(1) = 1$. The single integer in range, $1$, is coprime to itself.
• $n$ prime: $\varphi(n) = n - 1$, the maximum possible for that size — primes have the most coprime residues.
• $n$ even: at least half the integers are removed by the factor $(1 - \tfrac12)$, so $\varphi(n) \le n/2$.
• Sum over divisors: the totients of all divisors of $n$ add up to $n$ itself: $\sum_{d \mid n} \varphi(d) = n$. For $n = 12$: $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$.

Quick Reference

Concept	Formula
Definition	$\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}$
Product formula	$\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$
Prime	$\varphi(p) = p - 1$
Prime power	$\varphi(p^k) = p^{k-1}(p - 1)$
Multiplicative	$\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m, n) = 1$
Euler's theorem	$a^{\varphi(n)} \equiv 1 \pmod n$ when $\gcd(a, n) = 1$
Divisor sum	$\sum_{d \mid n} \varphi(d) = n$

Frequently Asked Questions (FAQ)

What is Euler's totient function?

Euler's totient function φ(n) counts the positive integers up to n that are coprime to n — those sharing no common factor with n other than 1. For example, φ(9) = 6 because 1, 2, 4, 5, 7, and 8 are each coprime to 9, while 3, 6, and 9 are not. By convention φ(1) = 1.

How do you calculate φ(n)?

Factor n into its distinct primes p₁, p₂, …, pₖ, then apply φ(n) = n · ∏(1 − 1/p) over those primes. For n = 36 = 2² · 3², φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · 1/2 · 2/3 = 12. Only the distinct primes matter, not their exponents.

What is the totient of a prime number?

For a prime p, every integer from 1 to p − 1 is coprime to p, so φ(p) = p − 1. For a prime power pᵏ the formula gives φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1). For example φ(7) = 6 and φ(8) = φ(2³) = 8 − 4 = 4.

Why does the totient matter in RSA and Euler’s theorem?

Euler's theorem states that if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n) — a generalization of Fermat's little theorem. RSA encryption relies on this: for a modulus n = p·q of two primes, φ(n) = (p − 1)(q − 1), and the public and private exponents are chosen so that e·d ≡ 1 (mod φ(n)). Knowing φ(n) is equivalent to factoring n, which is what keeps RSA secure.