Number Theory & Algebra contents

Euler's Totient Function

Count the integers up to n that are coprime to n, compute φ(n) from the factorization or for all n at once, and apply Euler's theorem.

Intermediate5 min readtotienteulernumber theorymodular arithmetic

Read first: Integer Factorization

Euler's totient function $\varphi(n)$ counts the integers in $[1, n]$ that are coprime to $n$ :

\varphi(n) = \#\{\, 1 \le k \le n : \gcd(k, n) = 1 \,\}

The first values are:

$n$	1	2	3	4	5	6	7	8	9	10
$\varphi(n)$	1	1	2	2	4	2	6	4	6	4

Properties

For a prime $p$ : $\varphi(p) = p - 1$ , since every smaller positive number is coprime to it.
For a prime power: $\varphi(p^k) = p^k - p^{k-1}$ , because only the multiples of $p$ are not coprime, and there are $p^{k-1}$ of them.
Multiplicative: if $\gcd(a, b) = 1$ then $\varphi(ab) = \varphi(a)\varphi(b)$ .

Combining these gives the formula from the prime factorization $n = p_1^{e_1} \cdots p_k^{e_k}$ :

\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) = \prod_{i=1}^{k} p_i^{e_i - 1}(p_i - 1)

For example $\varphi(36) = 36 \cdot \frac12 \cdot \frac23 = 12$ .

Computing $\varphi(n)$ for one number, $O(\sqrt n)$

Factor $n$ by trial division and apply $n \leftarrow n - n/p$ for each distinct prime $p$ :

python

def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p          # multiply by (1 - 1/p) exactly
        p += 1
    if n > 1:                              # one prime factor larger than sqrt(n) remains
        result -= result // n
    return result

from math import gcd

assert [phi(n) for n in range(1, 11)] == [1, 1, 2, 2, 4, 2, 6, 4, 6, 4]
assert phi(36) == 12 and phi(10 ** 9 + 7) == 10 ** 9 + 6
assert all(phi(n) == sum(1 for k in range(1, n + 1) if gcd(k, n) == 1) for n in range(1, 300))

result -= result // p is the integer version of result *= (1 - 1/p); it is exact because result is still divisible by p.

The totient of all numbers up to $n$ in $O(n \log\log n)$

Sieve-style: start with $\varphi(i) = i$ and, for every prime $p$ , apply the factor $(1 - 1/p)$ to all multiples of $p$ .

python

def phi_sieve(n):
    phi = list(range(n + 1))
    for i in range(2, n + 1):
        if phi[i] == i:                      # untouched so far: i is prime
            for j in range(i, n + 1, i):
                phi[j] -= phi[j] // i
    return phi

table = phi_sieve(1000)
assert table[:11] == [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4]
assert all(table[i] == phi(i) for i in range(1, 1001))

Divisor sum property

Summing $\varphi$ over the divisors of $n$ gives back $n$ :

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

Intuitively, sort the fractions $\frac{k}{n}$ for $1 \le k \le n$ by their reduced denominator $d$ ; there are exactly $\varphi(d)$ fractions with denominator $d$ .

python

for n in range(1, 400):
    assert sum(phi(d) for d in range(1, n + 1) if n % d == 0) == n

The property yields another way to build all values, with $\varphi(n) = n - \sum_{d \mid n,\, d < n} \varphi(d)$ , in $O(n \log n)$ .

Euler's theorem

If $\gcd(a, m) = 1$ then

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

For a prime modulus this is Fermat's little theorem, $a^{p-1} \equiv 1 \pmod p$ . Two consequences that appear constantly:

Modular inverse: $a^{-1} \equiv a^{\varphi(m) - 1} \pmod m$ (see Modular Inverse).
Huge exponents: $a^n \equiv a^{\,n \bmod \varphi(m)} \pmod m$ when $\gcd(a, m) = 1$ .

python

m, a = 1000, 7                                       # gcd(7, 1000) = 1
assert pow(a, phi(m), m) == 1
huge = 10 ** 100 + 12345
assert pow(a, huge, m) == pow(a, huge % phi(m), m)   # reduce the exponent first

Counting

Because $\varphi(n)$ counts numbers coprime to $n$ , it counts the reduced fractions with denominator $n$ in $(0, 1]$ ; the number of reduced fractions with denominator at most $N$ is $\sum_{n=1}^{N} \varphi(n)$ (the length of the Farey sequence).

python

N = 30
farey = {(a // gcd(a, b), b // gcd(a, b)) for b in range(1, N + 1) for a in range(1, b + 1)}
assert len(farey) == sum(phi_sieve(N)[1:])

Properties

Computing φ(n)\varphi(n)φ(n) for one number, O(n)O(\sqrt n)O(n​)

The totient of all numbers up to nnn in O(nlog⁡log⁡n)O(n \log\log n)O(nloglogn)

Divisor sum property

Euler's theorem

Counting

Practice problems

Computing $\varphi(n)$ for one number, $O(\sqrt n)$

The totient of all numbers up to $n$ in $O(n \log\log n)$