Euler’s totient function, denoted , is the function that counts the positive integers not exceeding a positive integer that are relatively prime to . Two integers are relatively prime, or coprime, when their greatest common divisor is . A central function in number theory, the totient connects prime factorization with the structure of multiplication in modular arithmetic. It is named after Leonhard Euler, who studied it in connection with his generalization of Fermat’s little theorem.
Definition and examples
For every positive integer ,
where denotes the number of elements in a finite set.
The convention follows directly from this definition, since . For , the endpoint is not counted, so the definition is equivalent to counting coprime integers strictly between and .
For example, the integers from through that are coprime to are
and therefore .
The first twelve values are:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 |
For , the ratio is the probability that an integer chosen uniformly from is coprime to .
Formula from prime factorization
If
is the factorization of into distinct primes , then
or, equivalently,
The product is over the distinct prime divisors of , not over their repeated occurrences. For , the empty-product convention gives the same formula.
For example,
so
Why the formula holds
An integer is coprime to exactly when it is divisible by none of the primes dividing . Among the integers from through , exactly are divisible by a prime divisor .
The inclusion–exclusion principle therefore gives
which factors into the product formula.
Thus depends only on which primes divide , not on their exponents.
Primes and prime powers
For a prime ,
because every integer from to is coprime to .
More generally, for ,
The excluded integers are precisely the multiples of .
Conversely, if and , then is prime.
Multiplicativity and divisor identities
The totient is a multiplicative arithmetic function:
The coprimality condition is essential. For example,
Thus the totient is not completely multiplicative.
One explanation of multiplicativity comes from the Chinese remainder theorem: when and are coprime, invertible residue classes modulo correspond bijectively to pairs of invertible residue classes modulo and modulo .
A fundamental divisor-sum identity is
To see this, partition the integers according to their greatest common divisor with . For each divisor , the integers satisfying are exactly those of the form with
There are such integers, and their counts sum to .
Applying Möbius inversion yields another useful formula:
where is the Möbius function.
Euler’s theorem and the group of units
The residue classes modulo that have multiplicative inverses form the group of units, written
A residue class is invertible exactly when its representatives are coprime to , so this group has elements.
Consequently, Lagrange’s theorem from group theory gives Euler’s theorem:
For example, , and
When is prime, Euler’s theorem becomes
which is Fermat’s little theorem.
The totient gives the size of the group of units, but not necessarily the smallest exponent that works for every element. That exponent is the Carmichael function , which divides . For instance,
because every odd integer has square congruent to modulo .
Further interpretations and applications
Reduced fractions
For , is the number of fractions
that are already in lowest terms. The divisor identity above can therefore also be understood by reducing fractions and grouping them by their reduced denominators.
Cyclotomic polynomials
A complex number is a primitive th root of unity if its multiplicative order is exactly . There are such roots. Hence the cyclotomic polynomial , whose roots are precisely those primitive roots, has degree
This connects the totient to polynomials, complex numbers, and the study of field extensions.
RSA cryptography
In the RSA cryptosystem, a modulus is commonly constructed as
where and are distinct primes. Then
A standard derivation chooses exponents satisfying
Euler’s theorem explains why the corresponding exponentiations undo one another on invertible residue classes. Correctness on all residue classes modulo this squarefree modulus follows by considering the congruences modulo and separately. RSA may also use the condition modulo .
For a product of two distinct primes, knowing and is enough to recover the factors:
The primes are then the roots of
Thus the totient of an RSA modulus is sensitive information.
Computation
When the distinct prime divisors of are known, the product formula makes evaluation straightforward:
- Set .
- For each distinct prime divisor , replace by .
- Return .
For a single integer, trial division can find the required primes using trial divisions in a simple implementation. For large inputs, factorization may dominate the work; this bound concerns the numeric value of , rather than its bit length.
To compute every value up to a bound , a sieve initializes , then updates every multiple of each prime by
The standard sieve takes arithmetic operations and storage, expressed in big-O notation. Linear-sieve variants can compute the table in arithmetic operations.
Size and average behavior
For every ,
Moreover, is even whenever : the coprime residues pair as and , with no fixed point.
The function is not monotone. For example,
Its average growth is described by
Thus the average of its first values is asymptotic to .
A related but different average is
The same constant is the limiting probability that two independently and uniformly chosen integers from are coprime as tends to infinity.
Individually, the ratio can be arbitrarily close to , as along large primes, and arbitrarily close to , as along products of increasingly many distinct small primes. The function therefore has substantial relative fluctuations despite its regular average behavior.
Inverse questions and open problems
Not every positive integer is a totient value. Since is even for , the only odd value it takes is . Some even integers, such as , are also absent from its range.
Different inputs can give the same output:
Carmichael’s totient conjecture asserts that no positive integer occurs as a totient value exactly once: whenever , there is some with .
Lehmer’s totient problem asks whether a composite integer can satisfy
Every prime satisfies this divisibility condition, but no composite example is known.