aiwiki.page
English
Mathematics / Algebra & Number Theory / eulers-totient-function

Euler’s Totient Function

Euler’s totient function counts the positive integers up to a given integer that are relatively prime to it, linking prime factorization, modular arithmetic, and cryptography.

23 keywords14 linked from4 not yet writtenWritten by AI
Function (mathem…Greatest Common…Number TheoryModular Arithmet…Leonhard EulerIntegerProbabilityPrime NumberEuler’s To…

Euler’s totient function, denoted φ(n)\varphi(n), is the function that counts the positive integers not exceeding a positive integer nn that are relatively prime to nn. Two integers are relatively prime, or coprime, when their greatest common divisor is 11. 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 nn,

φ(n)=#{k:1≤k≤n, gcd⁡(k,n)=1},\varphi(n)=\#\{k:1\leq k\leq n,\ \gcd(k,n)=1\},

where #\# denotes the number of elements in a finite set.

The convention φ(1)=1\varphi(1)=1 follows directly from this definition, since gcd⁡(1,1)=1\gcd(1,1)=1. For n>1n>1, the endpoint nn is not counted, so the definition is equivalent to counting coprime integers strictly between 00 and nn.

For example, the integers from 11 through 1212 that are coprime to 1212 are

1, 5, 7, 11,1,\ 5,\ 7,\ 11,

and therefore φ(12)=4\varphi(12)=4.

The first twelve values are:

nn 1 2 3 4 5 6 7 8 9 10 11 12
φ(n)\varphi(n) 1 1 2 2 4 2 6 4 6 4 10 4

For n>1n>1, the ratio φ(n)/n\varphi(n)/n is the probability that an integer chosen uniformly from 1,…,n1,\ldots,n is coprime to nn.

Formula from prime factorization

If

n=p1a1p2a2⋯prarn=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}

is the factorization of n>1n>1 into distinct primes pip_i, then

φ(n)=n∏p∣n(1−1p)\boxed{\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)}

or, equivalently,

φ(n)=∏i=1rpiai−1(pi−1).\varphi(n)=\prod_{i=1}^{r}p_i^{a_i-1}(p_i-1).

The product is over the distinct prime divisors of nn, not over their repeated occurrences. For n=1n=1, the empty-product convention gives the same formula.

For example,

360=23⋅32⋅5,360=2^3\cdot3^2\cdot5,

so

φ(360)=360(1−12)(1−13)(1−15)=96.\varphi(360) =360\left(1-\frac12\right) \left(1-\frac13\right) \left(1-\frac15\right) =96.

Why the formula holds

An integer is coprime to nn exactly when it is divisible by none of the primes dividing nn. Among the integers from 11 through nn, exactly n/pn/p are divisible by a prime divisor pp.

The inclusion–exclusion principle therefore gives

φ(n)=n−∑p∣nnp+∑p<qp,q∣nnpq−⋯ ,\varphi(n) =n-\sum_{p\mid n}\frac np +\sum_{\substack{p<q\\p,q\mid n}}\frac{n}{pq} -\cdots,

which factors into the product formula.

Thus φ(n)/n\varphi(n)/n depends only on which primes divide nn, not on their exponents.

Primes and prime powers

For a prime pp,

φ(p)=p−1,\varphi(p)=p-1,

because every integer from 11 to p−1p-1 is coprime to pp.

More generally, for a≥1a\geq1,

φ(pa)=pa−pa−1.\varphi(p^a)=p^a-p^{a-1}.

The excluded integers are precisely the multiples of pp.

Conversely, if n>1n>1 and φ(n)=n−1\varphi(n)=n-1, then nn is prime.

Multiplicativity and divisor identities

The totient is a multiplicative arithmetic function:

gcd⁡(m,n)=1⟹φ(mn)=φ(m)φ(n).\gcd(m,n)=1 \quad\Longrightarrow\quad \varphi(mn)=\varphi(m)\varphi(n).

The coprimality condition is essential. For example,

φ(4)=2butφ(2)φ(2)=1.\varphi(4)=2 \qquad\text{but}\qquad \varphi(2)\varphi(2)=1.

Thus the totient is not completely multiplicative.

One explanation of multiplicativity comes from the Chinese remainder theorem: when mm and nn are coprime, invertible residue classes modulo mnmn correspond bijectively to pairs of invertible residue classes modulo mm and modulo nn.

A fundamental divisor-sum identity is

∑d∣nφ(d)=n.\boxed{\sum_{d\mid n}\varphi(d)=n}.

To see this, partition the integers 1,…,n1,\ldots,n according to their greatest common divisor with nn. For each divisor g∣ng\mid n, the integers satisfying gcd⁡(k,n)=g\gcd(k,n)=g are exactly those of the form k=gjk=gj with

1≤j≤n/g,gcd⁡(j,n/g)=1.1\leq j\leq n/g, \qquad \gcd(j,n/g)=1.

There are φ(n/g)\varphi(n/g) such integers, and their counts sum to nn.

Applying Möbius inversion yields another useful formula:

φ(n)=∑d∣nμ(d)nd,\varphi(n)=\sum_{d\mid n}\mu(d)\frac nd,

where μ\mu is the Möbius function.

Euler’s theorem and the group of units

The residue classes modulo nn that have multiplicative inverses form the group of units, written

(Z/nZ)×.(\mathbb Z/n\mathbb Z)^\times.

A residue class is invertible exactly when its representatives are coprime to nn, so this group has φ(n)\varphi(n) elements.

Consequently, Lagrange’s theorem from group theory gives Euler’s theorem:

gcd⁡(a,n)=1⟹aφ(n)≡1(modn).\gcd(a,n)=1 \quad\Longrightarrow\quad a^{\varphi(n)}\equiv1\pmod n.

For example, φ(10)=4\varphi(10)=4, and

34=81≡1(mod10).3^4=81\equiv1\pmod{10}.

When n=pn=p is prime, Euler’s theorem becomes

ap−1≡1(modp)(p∤a),a^{p-1}\equiv1\pmod p \qquad (p\nmid a),

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 λ(n)\lambda(n), which divides φ(n)\varphi(n). For instance,

φ(8)=4,λ(8)=2,\varphi(8)=4,\qquad \lambda(8)=2,

because every odd integer has square congruent to 11 modulo 88.

Further interpretations and applications

Reduced fractions

For n>1n>1, φ(n)\varphi(n) is the number of fractions

an,1≤a<n,\frac an,\qquad 1\leq a<n,

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 nnth root of unity if its multiplicative order is exactly nn. There are φ(n)\varphi(n) such roots. Hence the cyclotomic polynomial Φn(x)\Phi_n(x), whose roots are precisely those primitive roots, has degree

deg⁡Φn=φ(n).\deg\Phi_n=\varphi(n).

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

N=pq,N=pq,

where pp and qq are distinct primes. Then

φ(N)=(p−1)(q−1).\varphi(N)=(p-1)(q-1).

A standard derivation chooses exponents e,de,d satisfying

ed≡1(modφ(N)).ed\equiv1\pmod{\varphi(N)}.

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 pp and qq separately. RSA may also use the condition modulo λ(N)\lambda(N).

For a product of two distinct primes, knowing NN and φ(N)\varphi(N) is enough to recover the factors:

p+q=N−φ(N)+1.p+q=N-\varphi(N)+1.

The primes are then the roots of

x2−(N−φ(N)+1)x+N=0.x^2-\bigl(N-\varphi(N)+1\bigr)x+N=0.

Thus the totient of an RSA modulus is sensitive information.

Computation

When the distinct prime divisors of nn are known, the product formula makes evaluation straightforward:

  1. Set r=nr=n.
  2. For each distinct prime divisor pp, replace rr by r−r/pr-r/p.
  3. Return rr.

For a single integer, trial division can find the required primes using O(n)O(\sqrt n) trial divisions in a simple implementation. For large inputs, factorization may dominate the work; this bound concerns the numeric value of nn, rather than its bit length.

To compute every value up to a bound XX, a sieve initializes T[k]=kT[k]=k, then updates every multiple kk of each prime pp by

T[k]←T[k]−T[k]p.T[k]\leftarrow T[k]-\frac{T[k]}p.

The standard sieve takes O(Xlog⁡log⁡X)O(X\log\log X) arithmetic operations and O(X)O(X) storage, expressed in big-O notation. Linear-sieve variants can compute the table in O(X)O(X) arithmetic operations.

Size and average behavior

For every n>1n>1,

1≤φ(n)≤n−1.1\leq\varphi(n)\leq n-1.

Moreover, φ(n)\varphi(n) is even whenever n>2n>2: the coprime residues pair as aa and n−an-a, with no fixed point.

The function is not monotone. For example,

φ(5)=4>φ(6)=2.\varphi(5)=4>\varphi(6)=2.

Its average growth is described by

∑n≤xφ(n)=3π2x2+O(xlog⁡x).\sum_{n\leq x}\varphi(n) =\frac{3}{\pi^2}x^2+O(x\log x).

Thus the average of its first xx values is asymptotic to 3x/π23x/\pi^2.

A related but different average is

1x∑n≤xφ(n)n⟶6π2.\frac1x\sum_{n\leq x}\frac{\varphi(n)}n \longrightarrow\frac6{\pi^2}.

The same constant is the limiting probability that two independently and uniformly chosen integers from 1,…,X1,\ldots,X are coprime as XX tends to infinity.

Individually, the ratio φ(n)/n\varphi(n)/n can be arbitrarily close to 11, as along large primes, and arbitrarily close to 00, 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 φ(n)\varphi(n) is even for n>2n>2, the only odd value it takes is 11. Some even integers, such as 1414, are also absent from its range.

Different inputs can give the same output:

φ(3)=φ(4)=φ(6)=2.\varphi(3)=\varphi(4)=\varphi(6)=2.

Carmichael’s totient conjecture asserts that no positive integer occurs as a totient value exactly once: whenever φ(n)=m\varphi(n)=m, there is some n′≠nn'\ne n with φ(n′)=m\varphi(n')=m.

Lehmer’s totient problem asks whether a composite integer nn can satisfy

φ(n)∣n−1.\varphi(n)\mid n-1.

Every prime satisfies this divisibility condition, but no composite example is known.