Euler's Totient Function

⚡ Key Takeaways

Euler's totient function $\varphi(n)$ counts the positive integers up to $n$ that are coprime to $n$ . Key result: it is multiplicative, with $\varphi(p^k) = p^k - p^{k-1}$ , giving the product formula $\varphi(n) = n\prod_{p\mid n}(1 - 1/p)$ . Where it applies: number theory, the structure of $(\mathbb{Z}/n\mathbb{Z})^\times$ , RSA cryptography, and Euler's theorem. Who/when: introduced by Leonhard Euler (1763), with the notation $\varphi$ standardized by Gauss (1801).

💡 The Core Insight

Counting integers coprime to $n$ becomes easy when you break $n$ into its prime-power building blocks. The Chinese Remainder Theorem guarantees that being coprime to $n = p_1^{a_1}\cdots p_r^{a_r}$ is equivalent to being simultaneously coprime to each $p_i^{a_i}$ independently. This independence makes $\varphi$ multiplicative, so the whole function is determined by its values on prime powers, which can be counted directly by subtracting off the multiples of each prime.

DefinitionEuler's Totient Function

For a positive integer $n$ , the totient $\varphi(n)$ is the number of integers $k$ with $1 \le k \le n$ such that $\gcd(k, n) = 1$ :

1

\quad \varphi(n) = \#\{\, k \in \mathbb{Z} : 1 \le k \le n,\ \gcd(k,n) = 1 \,\}

Derivation hint: This is a direct count; $\varphi(1) = 1$ by the convention that $\gcd(1,1)=1$ , so $1$ is counted. Here $\gcd(k,n)$ denotes the greatest common divisor of $k$ and $n$ . The integers counted are called totatives of $n$ . Equivalently, $\varphi(n)$ is the order (cardinality) of the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$ of residue classes that are invertible modulo $n$ .

DefinitionMultiplicative Function

An arithmetic function $f$ is multiplicative if $f(mn) = f(m)f(n)$ whenever $\gcd(m,n) = 1$ , and completely multiplicative if this holds for all $m,n$ . The totient is multiplicative but not completely multiplicative (see the warning below).

TheoremProduct Formula for the Totient

Let $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$ be the prime factorization of $n > 1$ , with distinct primes $p_i$ and exponents $a_i \ge 1$ . Then

2

\quad \varphi(n) = \prod_{i=1}^{r}\left(p_i^{a_i} - p_i^{a_i - 1}\right) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)

Derivation hint: Compute $\varphi$ on each prime power, then multiply using multiplicativity; the second form factors $p_i^{a_i}$ out of each term. The product $\prod_{p\mid n}$ runs over the distinct prime divisors of $n$ only (the exponents do not appear in the second form).

TheoremPrime-Power Value

For a prime $p$ and integer $k \ge 1$ ,

3

\quad \varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1) = p^k\left(1 - \frac{1}{p}\right)

Derivation hint: Among $1,\dots,p^k$ the integers sharing a factor with $p^k$ are exactly the multiples of $p$ , of which there are $p^{k-1}$ . In particular $\varphi(p) = p - 1$ for any prime $p$ .

TheoremDivisor Sum Identity (Gauss)

For every positive integer $n$ ,

4

\quad \sum_{d \mid n} \varphi(d) = n

Derivation hint: Partition $\{1,\dots,n\}$ according to the value of $\gcd(k,n)=n/d$ ; each class with that gcd has exactly $\varphi(d)$ elements.

TheoremEuler's Theorem

If $\gcd(a,n) = 1$ , then

5

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

Derivation hint: The unit $a$ lives in the group $(\mathbb{Z}/n\mathbb{Z})^\times$ of order $\varphi(n)$ ; Lagrange's theorem forces $a^{\varphi(n)} = e$ . This generalizes Fermat's Little Theorem $a^{p-1}\equiv 1 \pmod p$ , recovered by setting $n = p$ prime so $\varphi(p)=p-1$ .

ProofMultiplicativity of the Totient

We prove $\varphi(mn) = \varphi(m)\varphi(n)$ whenever $\gcd(m,n)=1$ .

Step 1 — Set up the bijection. By the Chinese Remainder Theorem (CRT), since $\gcd(m,n)=1$ , there is a ring isomorphism

\mathbb{Z}/mn\mathbb{Z} \;\cong\; \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z},

sending $k \bmod mn$ to the pair $(k \bmod m,\ k \bmod n)$ .

Step 2 — Units correspond to units. A ring isomorphism maps the group of units of one ring onto the group of units of the other, and units of a product ring are exactly the pairs of units:

(\mathbb{Z}/mn\mathbb{Z})^\times \;\cong\; (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times.

Step 3 — Count both sides. Taking cardinalities, $\#(\mathbb{Z}/mn\mathbb{Z})^\times = \varphi(mn)$ , and the product side has $\varphi(m)\cdot\varphi(n)$ elements. Hence $\varphi(mn) = \varphi(m)\varphi(n)$ . $\blacksquare$

Step 4 — Derive the product formula. Write $n = \prod p_i^{a_i}$ . Repeated application of multiplicativity gives $\varphi(n) = \prod \varphi(p_i^{a_i})$ . By equation $[3]$ , $\varphi(p_i^{a_i}) = p_i^{a_i}(1 - 1/p_i)$ . Multiplying and collecting the $p_i^{a_i}$ into $n$ yields $\varphi(n) = n\prod_{p\mid n}(1 - 1/p)$ , which is equation $[2]$ . $\blacksquare$

∎

ProofGauss's Divisor Sum Identity

We prove $\sum_{d\mid n}\varphi(d) = n$ .

Step 1 — Classify by gcd. Each integer $k$ in $\{1,2,\dots,n\}$ has a well-defined value $g = \gcd(k,n)$ , which is a divisor of $n$ . Partition the set into classes $S_g = \{k : \gcd(k,n) = g\}$ .

Step 2 — Count one class. Write $k = g\cdot j$ . Then $\gcd(k,n) = g$ iff $\gcd(j, n/g) = 1$ , with $1 \le j \le n/g$ . The number of such $j$ is exactly $\varphi(n/g)$ .

Step 3 — Sum over classes. The classes partition $\{1,\dots,n\}$ , so

n = \sum_{g \mid n} \#S_g = \sum_{g\mid n} \varphi(n/g).

Step 4 — Reindex. As $g$ ranges over divisors of $n$ , so does $d = n/g$ . Therefore $n = \sum_{d\mid n}\varphi(d)$ . $\blacksquare$

∎

mathematician · Leonhard Euler | 1707–1783

The Swiss polymath Leonhard Euler introduced the totient function in his 1763 paper Theoremata arithmetica nova methodo demonstrata, where he proved the congruence now bearing his name as a generalization of Fermat's Little Theorem. Euler used the function to extend results about residues to composite moduli, a critical step toward the structure theory of modular arithmetic. He did not use the symbol $\varphi$ ; he wrote the function descriptively. The notation $\varphi(n)$ , and the German name Totient, came later— $\varphi$ from Carl Friedrich Gauss in the Disquisitiones Arithmeticae (1801), and "totient" coined by J. J. Sylvester. Euler's contributions to number theory, analysis, mechanics, and graph theory make him one of the most prolific mathematicians in history.

🧠 Intuition

Think of $\varphi(n)$ as answering: "Of the residue classes mod $n$ , how many can be inverted by multiplication?" An element $a$ has a multiplicative inverse mod $n$ precisely when $\gcd(a,n)=1$ —because the equation $ax \equiv 1 \pmod n$ is solvable exactly under that condition (Bézout's identity). So $\varphi(n)$ literally counts the "usable" multipliers. The product formula $n\prod(1-1/p)$ has a probabilistic reading. Pick a random integer near $n$ ; the "chance" it avoids the prime $p$ as a factor is $1 - 1/p$ . Because divisibility by distinct primes behaves independently, you multiply these chances together, and scaling by $n$ converts a probability into a count. This independence is exactly what the Chinese Remainder Theorem makes rigorous.

Figure

Totatives of n = 12: integers coprime to 12 are highlighted; the count gives φ(12) = 4

ExampleComputing φ(360) from the Factorization

Given: $n = 360$ . Compute $\varphi(360)$ .

Step 1 — Factor. $360 = 2^3 \cdot 3^2 \cdot 5$ . The distinct primes are $2, 3, 5$ .

Step 2 — Apply the product formula (equation $[2]$ ):

\varphi(360) = 360\left(1 - \tfrac12\right)\left(1 - \tfrac13\right)\left(1 - \tfrac15\right).

Step 3 — Evaluate.

\varphi(360) = 360 \cdot \tfrac12 \cdot \tfrac23 \cdot \tfrac45 = 360 \cdot \tfrac{8}{30} = \tfrac{2880}{30} = 96.

Step 4 — Cross-check via prime powers (equation $[3]$ ): $\varphi(2^3)=8-4=4$ , $\varphi(3^2)=9-3=6$ , $\varphi(5)=4$ ; product $4\cdot 6\cdot 4 = 96$ . ✓

\boxed{\varphi(360) = 96 \text{ integers in } \{1,\dots,360\} \text{ are coprime to } 360}

ExampleUsing Euler's Theorem to Reduce a Huge Power

Given: Find the last two digits of $7^{803}$ , i.e. compute $7^{803} \bmod 100$ .

Step 1 — Set up. Last two digits means working mod $100$ . Since $\gcd(7,100)=1$ , Euler's theorem (equation $[5]$ ) applies.

Step 2 — Compute the modulus exponent. $100 = 2^2 \cdot 5^2$ , so

\varphi(100) = 100\left(1-\tfrac12\right)\left(1-\tfrac15\right) = 100\cdot \tfrac12 \cdot \tfrac45 = 40.

Step 3 — Reduce the exponent mod 40. $803 = 40\cdot 20 + 3$ , so $7^{803} = (7^{40})^{20}\cdot 7^3 \equiv 1^{20}\cdot 7^3 \pmod{100}$ .

Step 4 — Finish. $7^3 = 343 \equiv 43 \pmod{100}$ .

\boxed{7^{803} \equiv 43 \pmod{100} \;\Rightarrow\; \text{last two digits are } 43}

⚠️ Common mistake

The totient is multiplicative, NOT completely multiplicative. The identity $\varphi(mn)=\varphi(m)\varphi(n)$ requires $\gcd(m,n)=1$ . When the arguments share a factor it fails. Likewise, beware these traps:

$\varphi(p^k) \ne (p-1)^k$ in general; the correct value is $p^{k-1}(p-1)$ .
In the product formula $n\prod_{p\mid n}(1-1/p)$ , the product is over distinct primes; do not repeat a prime for higher exponents.
$\varphi(n)$ is even for all $n > 2$ . There is no $n$ with $\varphi(n) = 14$ (it is not in the image), so not every even number is a totient value—values like $14, 26, 34, \dots$ are "nontotients."

CounterexampleFailure of Complete Multiplicativity

Take $m = n = 6$ , which are not coprime. Then

\varphi(6\cdot 6) = \varphi(36) = \varphi(2^2\cdot 3^2) = 36\cdot\tfrac12\cdot\tfrac23 = 12,

but

\varphi(6)\cdot\varphi(6) = 4\cdot 4 = 16 \ne 12.

The two disagree precisely because $\gcd(6,6) = 6 \ne 1$ . A smaller case: $\varphi(4) = 2$ while $\varphi(2)\varphi(2) = 1\cdot 1 = 1$ . Multiplicativity simply does not apply to non-coprime arguments.

connection

The totient sits at the crossroads of several core structures. It is the order of the unit group studied in Modular Arithmetic, so its value governs element orders and the existence of Primitive Roots (which exist mod $n$ exactly when $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic). Equation $[4]$ is a special case of Dirichlet Convolution: writing $\mathrm{Id} = \varphi * \mathbf{1}$ , Möbius inversion recovers $\varphi = \mathrm{Id} * \mu$ , linking $\varphi$ to the Möbius Function. Euler's theorem (equation $[5]$ ) is a corollary of Lagrange's Theorem (Group Theory) applied to the unit group, and generalizes Fermat's Little Theorem. The summatory behavior of $\varphi$ connects to Analytic Number Theory through the asymptotic density of coprime pairs and the Riemann Zeta Function via the Dirichlet series $\sum \varphi(n)n^{-s} = \zeta(s-1)/\zeta(s)$ .

🔬 Where this appears

⏳ History

- 1640 — Pierre de Fermat states his "Little Theorem"

a^{p-1}\equiv 1\pmod p

, the prime-modulus precursor to Euler's generalization.

- 1736 — Euler publishes the first known proof of Fermat's Little Theorem.

- 1763 — Euler introduces the totient idea and proves

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

in Theoremata arithmetica nova methodo demonstrata.

- 1801 — Gauss, in Disquisitiones Arithmeticae, systematizes modular arithmetic, introduces the symbol

\varphi

, and proves the divisor-sum identity

\sum_{d\mid n}\varphi(d)=n

.

- 1832 — Gauss's framework clarifies the structure of

(\mathbb{Z}/n\mathbb{Z})^\times

and the existence of primitive roots, all phrased through

\varphi

.

- 1879 — J. J. Sylvester coins the term "totient."

- 1932 — Robert Carmichael studies the related

\lambda(n)

(Carmichael function), the exact exponent of the unit group, refining Euler's bound.

- 1962 — Wacław Sierpiński and others investigate the distribution of nontotients and Carmichael's totient-uniqueness conjecture.

- 1977 — Rivest, Shamir, and Adleman base the RSA cryptosystem on

\varphi(pq)

, making the totient a cornerstone of modern security.

open-problem

Several deep questions about $\varphi$ remain unresolved:

Carmichael's Totient Conjecture (1907). For every $n$ , is there always another integer $m \ne n$ with $\varphi(m) = \varphi(n)$ ? In other words, no totient value is attained exactly once. It has been verified for $n$ up to enormous bounds ( $\varphi(n) < 10^{10^{10}}$ ) but no proof exists.
Lehmer's Totient Problem (1932). Does $\varphi(n) \mid (n-1)$ ever hold for composite $n$ ? For primes it always holds since $\varphi(p)=p-1$ ; whether a composite counterexample exists is unknown. Any such $n$ must have at least 15 prime factors.
Distribution of values. The average order satisfies $\frac{1}{n}\sum_{k\le n}\varphi(k) \sim \frac{3}{\pi^2}n$ , but the fine fluctuations and the precise structure of the image (totients vs. nontotients) involve subtle analytic estimates (Ford's theorem, 1998, on the multiplicity of totient values).
Iterated totients. The behavior of repeatedly applying $\varphi$ (the "totient chain" reaching $1$ ) and its length is studied but not fully understood.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also