What Is Euler's Totient Function? φ(n) Explained for Coding Interviews

Euler's totient function shows up in one of the most common coding interview traps: computing a modular inverse when the modulus isn't prime. Most engineers reach for pow(a, p-2, p) and move on. That trick only works for prime moduli. When the modulus is composite, you need φ(n), and if you've been using the prime shortcut on autopilot, you've been trusting a formula whose precondition you've never checked.

What φ(n) Actually Counts

φ(n) counts how many integers from 1 to n share no common factor with n.

Formally, φ(n) is the count of integers k in [1, n] where gcd(k, n) = 1. Take n = 12.

The integers from 1 to 12: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

Which ones share a factor with 12? Since 12 = 2² × 3, anything divisible by 2 or 3 is out.

Divisible by 2: 2, 4, 6, 8, 10, 12
Divisible by 3 (not already caught): 3, 9

What's left: 1, 5, 7, 11. So φ(12) = 4.

Integers 1-12 with coprime ones highlighted, 1, 5, 7, 11 survive the gcd filter

The four survivors: 1, 5, 7, and 11. Everyone else shares a prime factor with 12 and gets shown the door.

For a prime p, every integer from 1 to p-1 is coprime with p. Primes have no factors to share, so nothing gets filtered out. φ(p) = p - 1.

The Formula (No Counting Required)

Checking gcd(k, n) for every k from 1 to n costs O(n log n). For n = 12, that's fine. For n = 10⁹, that's a timeout and a very long wait while you question your choices.

The closed-form formula is faster. Factor n into its distinct prime factors p₁, p₂, ..., pₖ:

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

Back to n = 12 = 2² × 3:

φ(12) = 12 × (1 - 1/2) × (1 - 1/3)
       = 12 × (1/2) × (2/3)
       = 4

That matches. φ is multiplicative: if gcd(m, n) = 1, then φ(mn) = φ(m) × φ(n). This is what makes the formula work. You compute φ independently for each prime power and multiply. No loops over every integer, no gcd calls, no suffering.

O(√n) via Trial Division

The algorithm mirrors trial division. Walk up to √n, apply each prime factor's contribution, and handle whatever is left:

def euler_totient(n: int) -> int:
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

The line result -= result // p applies (1 - 1/p) in integer arithmetic: result * (1 - 1/p) = result - result/p. No floating point, no rounding errors sneaking in to ruin your day.

euler_totient(12)  # 4
euler_totient(7)   # 6 (prime, so p-1)
euler_totient(36)  # 12

Time: O(√n). Space: O(1). Fast enough for any single φ(n) call in an interview.

The Theorem That Makes This Useful

Euler's Theorem: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n).

Raise a to the power φ(n), get back 1 modulo n, as long as a and n share no common factor. That's the whole theorem. It sounds academic until you realize it's why modular inverses work.

Fermat's Little Theorem is a special case. When n = p (prime), φ(p) = p - 1, so:

a^(p-1) ≡ 1 (mod p)

That's Fermat's. Euler's theorem is the general version that works for any modulus, prime or not. Fermat's gets the press because competitive programmers ran into primes first and stopped looking for the bigger picture.

Why `pow(a, p-2, p)` Will Lie to Your Face on Composite Moduli

The modular inverse of a (mod n) is the integer b such that a × b ≡ 1 (mod n). You need this whenever you're dividing inside a modular expression.

From Euler's theorem: a^φ(n) ≡ 1 (mod n), which means a × a^(φ(n)-1) ≡ 1 (mod n).

So a^(φ(n)-1) is the modular inverse of a, mod n, as long as gcd(a, n) = 1.

def mod_inverse(a: int, n: int) -> int:
    phi = euler_totient(n)
    return pow(a, phi - 1, n)

When n is prime, φ(n) = n - 1, so the inverse collapses to pow(a, n-2, n). That's the formula you've seen a hundred times in competitive programming. It's Euler's theorem with φ(p) = p - 1 substituted in.

For composite n = 12, φ(12) = 4, not 11. Using n - 2 = 10 as the exponent gives the wrong answer. Python won't throw an error. You'll get a plausible-looking integer, verify it against the wrong test cases, and spend the next hour convinced the bug is somewhere else entirely.

Computing φ for All Values Up to n

If you need φ(k) for every k from 1 to n, running the single-value algorithm on each costs O(n √n). That's a lot. The sieve drops it to O(n log log n), which is the same asymptotic class as the Sieve of Eratosthenes, and shares its core idea:

def euler_totient_sieve(n: int) -> list[int]:
    phi = list(range(n + 1))  # phi[i] = i initially
    for i in range(2, n + 1):
        if phi[i] == i:  # i is prime (unchanged)
            for j in range(i, n + 1, i):
                phi[j] -= phi[j] // i
    return phi

This applies the (1 - 1/p) factor for each prime p across all its multiples. After the sieve, phi[i] holds φ(i) for every i. The check phi[i] == i detects primes: composites have already been modified by their smallest prime factor, so only primes arrive at index i still equal to i. It's a neat trick that falls out of the algorithm for free.

Time: O(n log log n). Space: O(n).

Where This Shows Up in Interviews

The most direct appearance is LeetCode 372 (Super Pow): compute a^b mod 1337, where b is given as an array of digits. 1337 = 7 × 191. Since the modulus is composite, Fermat's Little Theorem doesn't apply. The problem looks like it's testing modular exponentiation. It's actually testing whether you notice that 1337 isn't prime before you write pow(a, mod-2, mod) and commit.

With Euler's theorem, you reduce the exponent mod φ(1337) = 6 × 190 = 1140 and proceed normally.

More broadly, reach for totient when you see:

Modular inverses with a non-prime modulus
Counting integers coprime to n in some range
Cryptography-adjacent number theory (RSA uses φ(pq) = (p-1)(q-1) internally)
Simplifying a^(huge exponent) mod n

The connection to modular arithmetic runs deep. If you've been computing modular inverses without thinking about why the formula works, totient is the missing piece.

GCD, Coprimality, and Totient Are the Same Thread

φ(n) is inseparable from GCD. The definition is built on coprimality (gcd = 1), the formula requires factoring n, and Euler's theorem requires gcd(a, n) = 1. When you see "coprime," "gcd = 1," or "modular inverse" in a problem, totient is almost always nearby. The GCD algorithm and the totient function share the same number-theoretic DNA.

Three concepts. One underlying structure. If you're shaky on any one, the other two are harder to use correctly under pressure.

Euler's Totient Function: Quick Reference

φ(n) counts integers from 1 to n that share no common factor with n
For prime p: φ(p) = p - 1
Formula: φ(n) = n × ∏(1 - 1/p) for each distinct prime factor p
Single value: O(√n) via trial division; all values up to n: O(n log log n) sieve
Euler's theorem: a^φ(n) ≡ 1 (mod n) when gcd(a, n) = 1
Modular inverse of a: a^(φ(n)-1) mod n, which generalizes pow(a, p-2, p) to composite moduli
Fermat's Little Theorem is Euler's theorem when n is prime

If you want to practice explaining number theory concepts like this out loud under time pressure, SpaceComplexity runs voice-based mock interviews with real-time feedback on both your reasoning and communication, the parts that separate candidates who know the algorithm from candidates who can actually use it in an interview.