The Euler Totient Function

How many numbers between $1$ and $n$ share no common factor with $n$ ? This deceptively simple counting question was first studied systematically by Leonhard Euler in the 1760s. It turns out to govern the arithmetic of every cyclic system built from the integers. The answer is captured by a single arithmetic function, Euler's totient $\varphi(n)$ . The question of how to compute it efficiently forces us to confront something deeper. We must face the interaction between the additive structure of "counting" and the multiplicative structure of "factoring." The totient function matters because it is the prototype of a multiplicative function. This is one whose value on a product of coprime integers factors as the product of the values. This single structural property, once established, converts an intractable counting problem into an easy calculation. That calculation comes straight from the prime factorization of $n$ . The same pattern recurs throughout number theory. First, define a function combinatorially. Then prove multiplicativity. Then read off a closed formula from prime powers. And $\varphi$ is the cleanest possible place to learn it. The big picture is that $\varphi(n)$ is not just a counting curiosity. It is exactly the order of the group of units $(\mathbb{Z}/n\mathbb{Z})^\times$ . This is the multiplicative group of residues coprime to $n$ . Every theorem about that group rests on knowing $\varphi(n)$ precisely. This includes Euler's generalization of Fermat's Little Theorem, the structure theory of cyclic groups, and ultimately the security proof behind RSA encryption. This article gives the rigorous definition of $\varphi$ . It proves from first principles that it is multiplicative, using the Chinese Remainder Theorem. It also derives the classical prime-power product formula. Along the way we build the intuition and work two nontrivial numerical examples. We show exactly why coprimality of the arguments cannot be dropped. Finally, we point toward Mobius Inversion and the RSA Cryptosystem as the natural continuations.

Key takeaways

$\varphi(n)$ counts integers in $\{1,\dots,n\}$ coprime to $n$ ; $\varphi(1)=1$ by convention.
$\varphi$ is a multiplicative function: $\gcd(m,n)=1 \implies \varphi(mn)=\varphi(m)\varphi(n)$ .
The proof uses the Chinese Remainder Theorem to build a bijection between unit residues mod $mn$ and pairs of unit residues mod $m$ , mod $n$ .
On a prime power, $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$ , proved by direct sieving of multiples of $p$ .
Combining these via the Fundamental Theorem of Arithmetic gives the product formula $\varphi(n) = n\prod_{p\mid n}\left(1-\tfrac1p\right)$ .
Dropping coprimality breaks multiplicativity entirely: $\varphi(4)=2$ but $\varphi(2)\varphi(2)=1\ne 2$ .
Key idea: counting coprime residues is hard directly but easy after factoring $n$ , because $\varphi$ respects the multiplicative structure of $\mathbb{Z}$ .

Where this lives today

The totient function is the load-bearing gear inside the RSA Cryptosystem: given a large $n = pq$ for secret primes $p,q$ , the private key is computed as the modular inverse of the public exponent modulo $\varphi(n) = (p-1)(q-1)$ , and the entire security argument rests on the fact that computing $\varphi(n)$ is exactly as hard as factoring $n$ . In group theory, $\varphi(n)$ is the order of the abelian group $(\mathbb{Z}/n\mathbb{Z})^\times$ , feeding directly into the classification of finite abelian groups and into constructions of finite fields and cyclic groups used throughout algebra. In analytic number theory, $\varphi$ is a key example in the theory of arithmetic functions, and its behavior is studied via Mobius Inversion, which recovers $\varphi$ from the identity $\sum_{d\mid n}\varphi(d) = n$ and expresses $\varphi(n) = \sum_{d\mid n}\mu(d)\frac{n}{d}$ using the Möbius function $\mu$ . The average order of $\varphi(n)/n$ over long ranges connects to the density of squarefree numbers and to results like $\sum_{n\le x}\varphi(n) \sim \frac{3}{\pi^2}x^2$ , linking $\varphi$ to $\zeta(2) = \pi^2/6$ . In combinatorics, $\varphi(n)$ counts the number of generators of a cyclic group of order $n$ , the number of primitive $n$ -th roots of unity, and the number of distinct necklaces or rotational symmetries in various counting problems via Burnside-type arguments.

Ask the tutor: How does Möbius inversion recover the totient formula from the divisor-sum identity $\sum_{d\mid n}\varphi(d)=n$ ?

n

Intuition

Picture the integers from $1$ to $n$ laid out in a row, and imagine crossing out every number that shares a factor with $n$ . What survives is exactly the set counted by $\varphi(n)$ . For a prime $p$ , nothing is crossed out except multiples of $p$ itself, so $\varphi(p) = p - 1$ : all residues except $0$ survive. For $n = 12 = 2^2 \cdot 3$ , we must cross out multiples of $2$ (namely $2,4,6,8,10,12$ ) and multiples of $3$ (namely $3,6,9,12$ ), being careful not to double-remove the multiples of $6$ . What's left is $\{1,5,7,11\}$ , so $\varphi(12) = 4$ . The key structural insight is that this "sieving" process interacts beautifully with factorization. If $n = mn'$ with $\gcd(m,n')=1$ , the Chinese Remainder Theorem tells us that living modulo $n$ is the same information as living modulo $m$ and modulo $n'$ simultaneously — residues mod $n$ correspond bijectively to pairs (residue mod $m$ , residue mod $n'$ ). Being a unit mod $n$ translates exactly to being a unit in both coordinates, and unit-ness in each coordinate is an independent condition. This independence is the engine behind multiplicativity: it converts a single hard count into a product of two easier counts.

Figure

The reduced residues mod 12, sieved from residues mod 4 and mod 3

The central theorem

m, n

p

Worked examples

Example 1: $n = 2\,450$ . Factor $n$ : $2450 = 2 \cdot 1225 = 2 \cdot 5^2 \cdot 245 = 2 \cdot 5^2 \cdot 5 \cdot 49$ . Let's be careful and redo this cleanly.

2450 = 2 \cdot 1225, \qquad 1225 = 5^2 \cdot 49 = 5^2 \cdot 7^2.

So $2450 = 2^1 \cdot 5^2 \cdot 7^2$ . Check: $2 \cdot 25 \cdot 49 = 2\cdot 1225 = 2450$ . Correct. By the product formula,

\varphi(2450) = 2450 \left(1 - \frac12\right)\left(1-\frac15\right)\left(1-\frac17\right) = 2450 \cdot \frac12 \cdot \frac45 \cdot \frac67.

Compute stepwise: $2450 \cdot \tfrac12 = 1225$ . Then $1225 \cdot \tfrac45 = 980$ . Then $980 \cdot \tfrac67 = 840$ . So $\varphi(2450) = 840$ . Cross-check via the prime-power factors directly: $\varphi(2) = 1$ , $\varphi(5^2) = 5^1(5-1) = 20$ , $\varphi(7^2) = 7^1(7-1) = 42$ . By multiplicativity (applicable since $2, 25, 49$ are pairwise coprime),

\varphi(2450) = \varphi(2)\cdot\varphi(25)\cdot\varphi(49) = 1 \cdot 20 \cdot 42 = 840.

Both routes agree: $\varphi(2450) = 840$ .

Example 2: verifying multiplicativity on a genuinely asymmetric coprime pair, $m = 63$ , $n = 100$ . Here $\gcd(63,100)=1$ since $63 = 3^2\cdot 7$ and $100 = 2^2\cdot 5^2$ share no prime factor. We compute $\varphi(63)$ , $\varphi(100)$ , and $\varphi(6300)$ independently and check the multiplicativity identity numerically, which is a genuine test of the theorem (not a restatement of it). $\varphi(63) = \varphi(3^2)\cdot \varphi(7) = 3(3-1)\cdot 6 = 6\cdot 6 = 36$ . $\varphi(100) = \varphi(2^2)\cdot\varphi(5^2) = 2(2-1)\cdot 5(5-1) = 2\cdot 20 = 40$ . Now compute $\varphi(6300)$ directly from its own factorization. Since $6300 = 63 \times 100 = 3^2\cdot 7\cdot 2^2\cdot 5^2$ , the product formula gives

\varphi(6300) = 6300\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)\left(1-\frac17\right).

Compute stepwise: $6300\cdot\tfrac12 = 3150$ ; $3150 \cdot \tfrac23 = 2100$ ; $2100\cdot\tfrac45 = 1680$ ; $1680\cdot\tfrac67 = 1440$ . So $\varphi(6300) = 1440$ . And indeed $\varphi(63)\cdot\varphi(100) = 36 \times 40 = 1440$ . The two independent computations match exactly, confirming multiplicativity in this nontrivial, non-symmetric case where $m\ne n$ and neither is a prime power alone.

\gcd(m,n)=1

Scope, edge cases & common traps

Situation	What holds	What to watch for
$\gcd(m,n)=1$	$\varphi(mn)=\varphi(m)\varphi(n)$	Fails badly if $\gcd(m,n)>1$ ; see counterexample
$n = p^k$ , $p$ prime	$\varphi(p^k) = p^{k-1}(p-1)$	Requires $k\ge 1$ ; $\varphi(p^0)=\varphi(1)=1$ trivially, not from this formula
$n=1$	$\varphi(1) = 1$ by convention	Empty-product edge case in the product formula: $n=1$ has no prime factors, and the empty product is $1$ , consistent
General $n\ge2$	$\varphi(n) = n\prod_{p\mid n}(1-1/p)$	The product is over distinct primes dividing $n$ , not over prime-power factors — a common bookkeeping slip
$\varphi$ is not completely multiplicative	$\varphi(p^2)\ne \varphi(p)\varphi(p)$ in general	e.g. $\varphi(4)=2$ but $\varphi(2)^2=1$ ; multiplicative $\ne$ completely multiplicative

Common trapThe classic error: forgetting "distinct primes" and misapplying multiplicativity

A frequent mistake is to write $\varphi(n) = \varphi(p_1)^{a_1}\varphi(p_2)^{a_2}\cdots$ or to apply the multiplicativity identity $\varphi(mn)=\varphi(m)\varphi(n)$ to a factorization $n = m\cdot n'$ without checking $\gcd(m,n')=1$ first. As the counterexample shows, this hypothesis is not optional bookkeeping — omitting it produces a wrong numeric answer, not just an inelegant proof. Always factor $n$ into prime powers with distinct bases before invoking multiplicativity; multiplicativity combines the totients of coprime pieces, and each individual prime-power totient must be computed by the separate sieving formula $\varphi(p^k)=p^{k-1}(p-1)$ , not by iterating multiplicativity on $p\cdot p\cdot p\cdots$ .

The mathematician behind it

Origins · 1 minLeonhard Euler and how this was discovered

Leonhard Euler

1707–1783 · 18th-century Basel/Berlin/St. Petersburg

Leonhard Euler was among the most prolific mathematicians in history, contributing foundational results across analysis, mechanics, graph theory, and number theory. He introduced the totient function (originally denoted $\pi(n)$ or later $\varphi(n)$ , called the "Euler phi function" today) in the course of generalizing Fermat's Little Theorem to composite moduli, a result now known as Euler's theorem: $a^{\varphi(n)}\equiv 1 \pmod n$ whenever $\gcd(a,n)=1$ . His interest in the function grew from a purely combinatorial question about counting fractions with denominator $n$ in lowest terms, but he quickly recognized its multiplicative structure as a computational shortcut — precisely the theorem proved above.

History

- 1736: Euler proves the special case of his theorem for prime modulus, matching Fermat's earlier (unpublished) claim.

- 1760: Euler introduces the totient function while working on generalizing Fermat's Little Theorem to arbitrary moduli.

- 1763: Euler publishes the general theorem

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

for

\gcd(a,n)=1

, establishing the totient's central role.

- 1801: Carl Friedrich Gauss, in Disquisitiones Arithmeticae, introduces the modern notation

\varphi(n)

and systematizes its properties within congruence theory.

- 1970s: The totient function becomes a cornerstone of public-key cryptography with the invention of RSA, which relies on

\varphi(n)

for key generation when

n

is a product of two large primes.

Is Euler's totient function ever equal to an odd number greater than 1?

No. For $n \ge 3$ , $\varphi(n)$ is always even. If $n$ has an odd prime factor $p$ , the factor $(p-1)$ appearing in the product formula is even, making the whole product even. If $n$ is a power of $2$ greater than $2$ , say $n = 2^k$ with $k\ge2$ , then $\varphi(n) = 2^{k-1}(2-1) = 2^{k-1}$ , which is even since $k-1\ge1$ . The only values with $\varphi(n)$ odd are $n=1$ (where $\varphi(1)=1$ ) and $n=2$ (where $\varphi(2)=1$ ); every other input yields an even output, a fact often used to rule out candidate totient values quickly.

Does

\varphi(n) = \varphi(n+1)

ever happen, or is the function strictly increasing?

The totient function is not monotonic and such coincidences do occur; for example $\varphi(1)=\varphi(2)=1$ , and later $\varphi(5)=4=\varphi(8)$ . There is no theorem forcing $\varphi(n) < \varphi(n+1)$ in general, because $\varphi(n)$ depends on the number and size of prime factors of $n$ , which fluctuates irregularly. What is true, and provable from the product formula, is that $\varphi(n) \to \infty$ as $n\to\infty$ , so equal values can only recur among small or specially structured $n$ ; asymptotically $\varphi(n)$ grows without bound, though with large gaps of near-constant behavior for numbers with many small prime factors.

How is

\varphi(n)

related to the number of generators of a cyclic group of order

n

If $G$ is cyclic of order $n$ , generated by $g$ , then $g^k$ generates $G$ if and only if $\gcd(k,n)=1$ . This is because the order of $g^k$ in a cyclic group of order $n$ equals $n/\gcd(k,n)$ , and this order equals $n$ (i.e., $g^k$ generates the whole group) precisely when $\gcd(k,n)=1$ . Since $k$ ranges over $\{1,\dots,n\}$ to enumerate all elements $g^k$ , the count of generators is exactly $\varphi(n)$ by definition. This is the reason $\varphi(n)$ also counts primitive $n$ -th roots of unity in $\mathbb{C}$ , since these form a cyclic group of order $n$ under multiplication.

Why is

\varphi

called "multiplicative" rather than "completely multiplicative"?

A function $f$ is multiplicative if $f(mn)=f(m)f(n)$ only when $\gcd(m,n)=1$ , while completely multiplicative means this holds for all $m,n$ with no coprimality restriction. The totient function satisfies the weaker property only: as the counterexample shows, $\varphi(4) = 2 \ne \varphi(2)\varphi(2) = 1$ , so $\varphi$ fails to be completely multiplicative. This distinction matters throughout analytic number theory because many important functions (like $\varphi$ , the divisor function $d(n)$ , and the Möbius function $\mu$ ) are multiplicative but not completely multiplicative, while others (like $n^s$ for the Dirichlet series variable $s$ ) are completely multiplicative, and the two classes behave differently under Dirichlet convolution.

Can

\varphi(n)

be computed without factoring

n

No efficient general method is known, and this is precisely why $\varphi(n)$ underlies RSA security. The product formula shows that knowing $\varphi(n)$ is computationally equivalent to knowing the prime factorization of $n$ : given the factorization, $\varphi(n)$ is easy to compute via the formula proved above, and conversely, if $n=pq$ for two unknown primes, knowing both $n$ and $\varphi(n)$ lets you recover $p$ and $q$ by solving the quadratic $x^2 - (n-\varphi(n)+1)x + n = 0$ , whose roots are $p$ and $q$ . Since factoring large semiprimes is believed to be computationally hard, computing $\varphi(n)$ for such $n$ is believed equally hard, absent the factorization.

What is the relationship between

\varphi(n)

and the sum

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

There is a beautiful identity, $\sum_{d\mid n}\varphi(d) = n$ , sometimes called Gauss's theorem on the totient function. It follows from partitioning $\{1,\dots,n\}$ by the value of $\gcd(k,n)$ : for each divisor $d$ of $n$ , exactly $\varphi(n/d)$ integers $k$ in that range satisfy $\gcd(k,n)=d$ . Summing $\varphi(n/d)$ over all divisors $d$ of $n$ (equivalently, summing $\varphi(d)$ over all divisors $d$ , by re-indexing) recovers all $n$ integers exactly once, giving the identity. This identity is the launching point for deriving $\varphi$ via Mobius Inversion, expressing $\varphi(n) = \sum_{d\mid n}\mu(d)(n/d)$ .

Is the product formula the fastest way to compute

\varphi(n)

by hand for large

n

Yes, given the factorization of $n$ , the product formula is essentially optimal: it requires one term per distinct prime factor, versus checking $\gcd(k,n)=1$ for every $k$ from $1$ to $n$ directly from the definition, which takes $n$ steps. The bottleneck is factoring $n$ itself, not evaluating the formula afterward — for a number with $r$ distinct prime factors, the formula needs only $O(r)$ arithmetic operations once factorization is known, which is exponentially faster than the brute-force gcd-counting definition for large $n$ .