Euler's Totient Function

Euler's totient function $\phi :{\mathbb{Z}}^{+}\to {\mathbb{Z}}^{+}$ assigns to each positive integer $n$ the number of integers in $\{1,2,\dots ,n\}$ that share no common factor with $n$ other than $1$. It is one of the most fundamental arithmetic functions because it precisely measures the size of the multiplicative group of integers modulo $n$, the group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ of units. This single quantity controls the orders of elements in modular arithmetic, underlies Euler's generalization of Fermat's Little Theorem, and is the secret-key ingredient of the RSA cryptosystem. A surprising fact: although $\phi (n)$ measures "how many numbers are coprime to $n$," its values are extraordinarily erratic—yet they satisfy the beautiful, exact summation identity ${\sum }_{d\mid n}\phi (d)=n$.

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 $\phi$ 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.

Formal Statement

Euler's Totient Function

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

Here $\gcd (k,n)$ denotes the greatest common divisor of $k$ and $n$. The integers counted are called totatives of $n$. Equivalently, $\phi (n)$ is the order (cardinality) of the multiplicative group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ of residue classes that are invertible modulo $n$.

Multiplicative 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).

Product 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

The product ${\prod }_{p\mid n}$ runs over the distinct prime divisors of $n$ only (the exponents do not appear in the second form).

Prime-Power Value

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

In particular $\phi (p)=p-1$ for any prime $p$.

Divisor Sum Identity (Gauss)

For every positive integer $n$,

Euler's Theorem

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

This generalizes Fermat's Little Theorem $a^{p-1}\equiv 1(\mathrm{mod}p)$, recovered by setting $n=p$ prime so $\phi (p)=p-1$.

Why It Holds / Derivation

Multiplicativity of the Totient

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

Gauss's Divisor Sum Identity

We prove ${\sum }_{d\mid n}\phi (d)=n$.

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 $\phi$; he wrote the function descriptively. The notation $\phi (n)$, and the German name Totient, came later—$\phi$ 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.

Building Intuition

Think of $\phi (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(\mathrm{mod}n)$ is solvable exactly under that condition (Bézout's identity). So $\phi (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.

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

Worked Examples

Computing φ(360) from the Factorization

Using Euler's Theorem to Reduce a Huge Power

Common Misconceptions

• $\phi (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.
• $\phi (n)$ is even for all $n>2$. There is no $n$ with $\phi (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."

Failure of Complete Multiplicativity

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

Connections

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}=\phi \ast 1$, Möbius inversion recovers $\phi =\mathrm{Id}\ast \mu$, linking $\phi$ 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 $\phi$ connects to Analytic Number Theory through the asymptotic density of coprime pairs and the Riemann Zeta Function via the Dirichlet series $\sum \phi (n)n^{-s}=\zeta (s-1)/\zeta (s)$.

Real-World Applications

1. RSA cryptography. Key generation uses $n=pq$ for secret primes $p,q$; the encryption/decryption exponents satisfy $ed\equiv 1(\mathrm{mod}\phi (n))$, where $\phi (n)=(p-1)(q-1)$. Security rests on the hardness of recovering $\phi (n)$ without factoring $n$.
2. Diffie–Hellman and ElGamal. Choosing generators of $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ relies on knowing $\phi (p)=p-1$ and its factorization to verify primitive roots.
3. Random number generators. The period of a linear congruential generator with multiplier coprime to the modulus is bounded by the totient/order structure of the unit group.
4. Cyclotomic polynomials. The $n$-th cyclotomic polynomial ${\Phi }_n(x)$ has degree exactly $\phi (n)$, used in error-correcting BCH codes and primality tests (AKS).
5. Hashing and check-digit schemes. Modular inverses (existing iff coprime, counted by $\phi$) underpin invertible mixing steps in checksum algorithms.
6. Music and rhythm theory. Counting distinct necklaces/rhythmic patterns of period $n$ uses $\phi (d)$ terms via Burnside/Pólya counting.
7. Continued fractions and Farey sequences. The number of fractions in the Farey sequence $F_n$ is $1+{\sum }_{k=1}^n\phi (k)$, applied in numerical approximation.

Historical Development

• 1640 — Pierre de Fermat states his "Little Theorem" $a^{p-1}\equiv 1(\mathrm{mod}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^{\phi (n)}\equiv 1(\mathrm{mod}n)$ in Theoremata arithmetica nova methodo demonstrata.
• 1801 — Gauss, in Disquisitiones Arithmeticae, systematizes modular arithmetic, introduces the symbol $\phi$, and proves the divisor-sum identity ${\sum }_{d\mid n}\phi (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 $\phi$.
• 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 $\phi (pq)$, making the totient a cornerstone of modern security.

Subtleties & Limits

Several deep questions about $\phi$ remain unresolved:

• Carmichael's Totient Conjecture (1907). For every $n$, is there always another integer $m\ne n$ with $\phi (m)=\phi (n)$? In other words, no totient value is attained exactly once. It has been verified for $n$ up to enormous bounds ($\phi (n)<10^{10^{10}}$) but no proof exists.
• Lehmer's Totient Problem (1932). Does $\phi (n)\mid (n-1)$ ever hold for composite $n$? For primes it always holds since $\phi (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}\phi (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 $\phi$ (the "totient chain" reaching $1$) and its length is studied but not fully understood.

See Also