Skip to content

Euler's Totient Function

Definition

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

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

When \(n\) is a prime number, it is obvious that \(\varphi(n) = n - 1\).

Properties

  • Euler's totient function is a multiplicative function.

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

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

    For proof, see Composition of Residue Systems.

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

    Proof

    This can be derived using knowledge of Möbius inversion.

    Alternatively, consider: if \(\gcd(k, n) = d\), then \(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )\).

    If we define \(f(x)\) as the count of numbers such that \(\gcd(k, n) = x\), then \(n = \sum_{i = 1}^n{f(i)}\).

    From the above proof, we find that \(f(x) = \varphi(\dfrac{n}{x})\), thus \(n = \sum_{d \mid n}\varphi(\dfrac{n}{d})\). Noting the symmetry between divisors \(d\) and \(\dfrac{n}{d}\), the equation simplifies to \(n = \sum_{d \mid n}\varphi(d)\).

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

  • By the unique factorization theorem, let \(n = \prod_{i=1}^{s}p_i^{k_i}\), where \(p_i\) are primes. Then \(\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\).

    Proof

    • Lemma: Let \(p\) be any prime, then \(\varphi(p^k)=p^{k-1}\times(p-1)\).

      Proof: Clearly, among all numbers from 1 to \(p^k\), except for the \(p^{k-1}\) multiples of \(p\), all others are coprime to \(p^k\). Hence, \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)\). QED.

    Next, we prove \(\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}\). By the unique factorization theorem 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 \(m,n\) not both zero, \(\varphi(mn)\varphi(\gcd(m,n))=\varphi(m)\varphi(n)\gcd(m,n)\).

    This can be directly computed from the previous property.

Implementation

If only the Euler's totient value of a single number is required, it can be computed directly by factorization according to the definition. This process can be optimized using the Pollard Rho algorithm.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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

If Euler's totient values for multiple numbers are needed, they can be obtained using the linear sieve method mentioned later.

See also: Sieve Method for Euler's Totient Function

Applications

Euler's totient function is often used to simplify sums involving greatest common divisors. Some domestic articles refer to this as Euler inversion1.

Substituting \(n=\gcd(a,b)\) into the conclusion

\[ n=\sum_{d|n}\varphi(d) \]

yields

\[ \gcd(a,b) = \sum_{d|\gcd(a,b)}\varphi(d) = \sum_d [d|a][d|b]\varphi(d), \]

where \([\cdot]\) is the Iverson bracket. Summing this equation gives

\[ \sum_{i=1}^n\gcd(i,n)=\sum_{d}\sum_{i=1}^n[d|i][d|n]\varphi(d)=\sum_d\left\lfloor\frac{n}{d}\right\rfloor[d|n]\varphi(d)=\sum_{d|n}\left\lfloor\frac{n}{d}\right\rfloor\varphi(d). \]

The key observation here is \(\sum_{i=1}^n[d|i]=\lfloor\frac{n}{d}\rfloor\), i.e., the number of \(i\) between \(1\) and \(n\) divisible by \(d\) is \(\lfloor\frac{n}{d}\rfloor\).

Using this formula, one can sum over divisors. For multiple queries, one can precompute the prefix sum of Euler's totient function and use number-theoretic blocking for queries.

GCD SUM

Given \(n\le 100000\), find

\[ \sum_{i=1}^n\sum_{j=1}^n\gcd(i,j). \]
Idea

Following the derivation above, we obtain

\[ \sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) = \sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor^2\varphi(d). \]

Now we need to compute Euler's totient function from \(1\) to \(n\). Using linear sieve, the answer can be obtained in \(O(n)\).

Euler's Theorem

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

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

Extended Euler's Theorem

There is also the Extended Euler's Theorem, which handles the general case of \(a\) and \(m\).

\[ a^b\equiv \begin{cases} a^{b\bmod\varphi(m)},\,&\gcd(a,\,m)=1\\ a^b,&\gcd(a,\,m)\ne1,\,b<\varphi(m)\\ a^{b\bmod\varphi(m)+\varphi(m)},&\gcd(a,\,m)\ne1,\,b\ge\varphi(m) \end{cases} \pmod m \]

Proof and exercises can be found at Euler's Theorem.

Exercises

References and Notes

  1. This term is not commonly found in academic journals or foreign forums, so caution is advised when using it. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用