Euler's Totient Function

Definition

Euler's totient function, denoted by $\varphi(n)$, counts the integers less than or equal to $n$ that are coprime to $n$.

For example, $\varphi(1) = 1$.

When $n$ is prime, clearly $\varphi(n) = n - 1$.

Properties

• The Euler totient function is a multiplicative function.

  That is, for any integers satisfying $\gcd(a, b) = 1$, written as $a,b$, we have $\varphi(ab) = \varphi(a)\varphi(b)$.

  In particular, when $n$ is odd, $\varphi(2n) = \varphi(n)$.

  See composition of residue systems for a proof.

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

  ???+ note "Proof" This follows from Möbius inversion and related facts.

  It can also be seen as follows: if $\gcd(k, n) = d$, then $\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )$.
  
  Let $f(x)$ denote the number of integers satisfying $\gcd(k, n) = x$. Then $n = \sum_{i = 1}^n{f(i)}$.
  
  From the argument above, we find that $f(x) = \varphi(\dfrac{n}{x})$, and hence $n = \sum_{d \mid n}\varphi(\dfrac{n}{d})$. Since the divisors $d$ and $\dfrac{n}{d}$ are symmetric, this becomes $n = \sum_{d \mid n}\varphi(d)$.
  

• If $n = p^k$, where $p$ is prime, then $\varphi(n) = p^k - p^{k - 1}$. (This follows directly from the definition.)

• By the fundamental theorem of arithmetic, let $n = \prod_{i=1}^{s}p_i^{k_i}$, where each $p_i$ is prime. Then $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$.

  ???+ note "Proof" - Lemma: for any prime $p$, $\varphi(p^k)=p^{k-1}\times(p-1)$.

      Proof: among the integers from 1 to $p^k$, exactly $p^{k-1}$ are multiples of $p$; all the others are coprime to $p^k$. Thus $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)$.
  
  We next prove $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$. By the fundamental theorem of arithmetic and the multiplicativity of $\varphi(x)$,
  
  $$
  \begin{aligned}
      \varphi(n) &= \prod_{i=1}^{s} \varphi(p_i^{k_i}) \\
      &= \prod_{i=1}^{s} (p_i-1)\times {p_i}^{k_i-1}\\
      &=\prod_{i=1}^{s} {p_i}^{k_i} \times(1 - \frac{1}{p_i})\\
      &=n~ \prod_{i=1}^{s} (1- \frac{1}{p_i})
      &\square
  \end{aligned}
  $$
  

• For any integers that are not both $0$, written as $m,n$, $\varphi(mn)\varphi(\gcd(m,n))=\varphi(m)\varphi(n)\gcd(m,n)$.

  This follows by direct calculation from the preceding identity.

Implementation

If only the totient of one number is needed, factor the number according to the definition while computing the answer. This process can be optimized with the Pollard Rho algorithm.

#include <cmath>

int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

import math


def euler_phi(n):
    ans = n
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            ans = ans // i * (i - 1)
            while n % i == 0:
                n = n // i
    if n > 1:
        ans = ans // n * (n - 1)
    return ans

For the totients of multiple numbers, use the linear sieve introduced later.

For details, see sieving for the Euler totient function.

Applications

The Euler totient function is often used to simplify sums of greatest common divisors. Some Chinese articles call this Euler inversion¹.

In the conclusion

Substituting $n=\gcd(a,b)$ into it gives

where $[\cdot]$ is an Iverson bracket. Summing the identity yields

The key observation is $\sum_{i=1}^n[d|i]=\lfloor\frac{n}{d}\rfloor$: between $1$ and $n$, the number of integers divisible by $d$, indexed by $i$, is $\lfloor\frac{n}{d}\rfloor$.

Using this identity, we can enumerate the divisors and sum over them. For multiple queries, precompute prefix sums of the Euler totient function and use number-theoretic block decomposition.

Euler's Theorem

A theorem closely related to the Euler totient function is Euler's theorem. It states:

If $\gcd(a, m) = 1$, then $a^{\varphi(m)} \equiv 1 \pmod{m}$.

Extended Euler Theorem

The extended Euler theorem handles the general case of $a$ and $m$.

For the proof and exercises, see Euler's theorem.

Exercises

• SPOJ ETF. Euler Totient Function
• UVa 10179. Irreducible Basic Fractions
• UVa 10299. Relatives
• UVa 11327. Enumerating Rational Numbers
• TIMUS 1673. Admission to Exam
• Luogu P1390 Sum of Divisors
• Luogu P2155 [SDOI2008] The Salad Princess's Confusion
• Luogu P2568 GCD

References and Notes