18.11 Euler Phi Function

Euler's phi function counts how many numbers in a range are coprime to a given integer. It appears naturally in modular arithmetic, cryptography, primitive roots, multiplicative functions, and counting problems over residue classes.

The function is usually written as:

φ(n)

It counts the positive integers k such that:

1 ≤ k ≤ n

and:

gcd(k,n) = 1

For example:

φ(9) = 6

because the numbers coprime to 9 are:

1 2 4 5 7 8

The numbers 3, 6, and 9 are excluded because they share a factor with 9.

Problem

Given an integer:

compute:

φ(n)

efficiently.

Example:

φ(10) = 4

because the numbers from 1 to 10 that are coprime to 10 are:

1 3 7 9

A direct count using GCD works, but it is too slow for large n or repeated queries.

Direct Counting

The most literal implementation tests every number.

from math import gcd

def phi_naive(n):
    count = 0

    for k in range(1, n + 1):
        if gcd(k, n) == 1:
            count += 1

    return count

Example:

print(phi_naive(10))

Output:

Complexity:

O(n log n)

because each GCD computation costs logarithmic time.

This is useful for testing, but not for production algorithms.

Prime Case

If p is prime, every number:

1, 2, ..., p-1

is coprime to p.

Only p itself is not coprime to p.

Therefore:

φ(p) = p - 1

Examples:

φ(5) = 4
φ(7) = 6
φ(13) = 12

This property is central to Fermat's Little Theorem and finite-field arithmetic.

Prime Power Case

Now consider:

n = p^e

where p is prime.

The only numbers not coprime to p^e are multiples of p.

From 1 through p^e, there are:

p^(e-1)

multiples of p.

So:

φ(p^e) = p^e - p^(e-1)

Factor:

φ(p^e) = p^e(1 - 1/p)

Example:

φ(8) = φ(2^3)

There are:

8 - 4 = 4

coprime values:

1 3 5 7

So:

φ(8) = 4

General Formula

If:

n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ

then:

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₖ)

The exponents do not appear directly in the product except through the original value of n.

Example:

n = 36 = 2² × 3²

Then:

φ(36) = 36 × (1 - 1/2) × (1 - 1/3)

φ(36) = 36 × 1/2 × 2/3 = 12

The numbers coprime to 36 are:

1 5 7 11 13 17 19 23 25 29 31 35

There are 12 of them.

Computing Phi from Factorization

The formula can be implemented by iterating over distinct prime factors.

def phi(n):
    result = n
    x = n
    p = 2

    while p * p <= x:
        if x % p == 0:
            result -= result // p

            while x % p == 0:
                x //= p

        p += 1

    if x > 1:
        result -= result // x

    return result

Example:

print(phi(36))
print(phi(10))
print(phi(13))

Output:

12
4
12

The update:

result -= result // p

implements multiplication by:

1 - 1/p

without using floating-point arithmetic.

Why Integer Arithmetic Matters

Avoid this implementation style:

result = int(result * (1 - 1 / p))

It introduces floating-point arithmetic into an exact integer problem. For large numbers, rounding can produce incorrect results.

Use:

result -= result // p

This keeps the calculation exact.

Example Walkthrough

Compute:

φ(60)

Factorization:

60 = 2² × 3 × 5

Start:

result = 60

Process prime factor 2:

result = 60 - 60/2 = 30

Process prime factor 3:

result = 30 - 30/3 = 20

Process prime factor 5:

result = 20 - 20/5 = 16

Therefore:

φ(60) = 16

Multiplicativity

Euler's phi function is multiplicative.

If:

gcd(a,b) = 1

then:

φ(ab) = φ(a)φ(b)

Example:

a = 8
b = 9

Since:

gcd(8,9) = 1

we have:

φ(72) = φ(8)φ(9)

Now:

φ(8) = 4
φ(9) = 6

so:

φ(72) = 24

This agrees with the formula:

72 = 2³ × 3²

φ(72) = 72 × (1 - 1/2) × (1 - 1/3) = 24

Euler's Theorem

Euler's phi function controls powers modulo composite moduli.

If:

gcd(a,n) = 1

then:

a^φ(n) ≡ 1 (mod n)

This is Euler's theorem.

For example:

a = 5
n = 8

Since:

gcd(5,8) = 1

and:

φ(8) = 4

we get:

5⁴ ≡ 1 (mod 8)

Check:

625 mod 8 = 1

Fermat's Little Theorem is the special case where n is prime.

Modular Inverses with Phi

Euler's theorem gives another way to compute modular inverses.

If:

gcd(a,n) = 1

then:

a^φ(n) ≡ 1 (mod n)

So:

a × a^(φ(n)-1) ≡ 1 (mod n)

Therefore:

a⁻¹ ≡ a^(φ(n)-1) (mod n)

This is valid for composite moduli too, provided a and n are coprime.

In practice, Extended Euclid is usually faster for a single inverse because it avoids factoring n.

Sieve for Phi Values

If we need φ(x) for every x <= n, we can compute all values with a sieve.

def phi_sieve(n):
    phi = list(range(n + 1))

    for p in range(2, n + 1):
        if phi[p] == p:
            for multiple in range(p, n + 1, p):
                phi[multiple] -= phi[multiple] // p

    return phi

Example:

values = phi_sieve(10)

for i in range(1, 11):
    print(i, values[i])

Output:

Complexity:

O(n log log n)

This is useful for batch computations.

Linear Sieve for Phi

A linear sieve can compute phi values in O(n).

def phi_linear_sieve(n):
    primes = []
    is_composite = [False] * (n + 1)
    phi = [0] * (n + 1)

    phi[1] = 1

    for x in range(2, n + 1):
        if not is_composite[x]:
            primes.append(x)
            phi[x] = x - 1

        for p in primes:
            if x * p > n:
                break

            is_composite[x * p] = True

            if x % p == 0:
                phi[x * p] = phi[x] * p
                break

            phi[x * p] = phi[x] * (p - 1)

    return phi

This version is more complex but useful when computing several multiplicative functions together.

Application: Counting Reduced Fractions

The number of reduced fractions:

a/n

with:

1 ≤ a ≤ n

equals:

φ(n)

because the fraction is reduced exactly when:

gcd(a,n) = 1

For example, with denominator 10, the reduced fractions are:

1/10
3/10
7/10
9/10

There are:

φ(10) = 4

Application: RSA

RSA relies directly on phi.

Given:

n = pq

where p and q are distinct primes:

φ(n) = (p-1)(q-1)

The private exponent d is chosen so that:

ed ≡ 1 (mod φ(n))

This is why factoring n breaks RSA: once p and q are known, φ(n) becomes easy to compute.

Common Mistakes

Confusing φ(n) with Number of Divisors

φ(n) counts coprime residues. It does not count divisors.

For example:

φ(12) = 4

but 12 has six positive divisors:

1 2 3 4 6 12

Forgetting Distinct Prime Factors Only

In the formula:

φ(n) = n × Π(1 - 1/p)

each prime factor appears once.

For:

72 = 2³ × 3²

use 2 and 3, not repeated copies.

Using Floating-Point Arithmetic

Keep the computation integer-only.

Use:

result -= result // p

Assuming Multiplicativity Without Coprimality

The identity:

φ(ab) = φ(a)φ(b)

requires:

gcd(a,b) = 1

It does not hold in general.

Testing

Basic tests:

def test_phi():
    assert phi(1) == 1
    assert phi(2) == 1
    assert phi(5) == 4
    assert phi(8) == 4
    assert phi(9) == 6
    assert phi(10) == 4
    assert phi(36) == 12

Cross-check against the naive version for small inputs:

def test_phi_against_naive():
    for n in range(1, 200):
        assert phi(n) == phi_naive(n)

The naive implementation is slow, but it is excellent as a correctness oracle for small values.

Takeaway

Euler's phi function counts the integers up to n that are coprime to n. Its efficient computation depends on the distinct prime factors of n, using the formula φ(n) = n Π(1 - 1/p). Phi is multiplicative over coprime inputs, governs Euler's theorem, and supports modular inverses, RSA, reduced-fraction counting, and many multiplicative-function algorithms. For repeated queries, sieve-based methods compute phi values for all integers in a range efficiently.