Euler's Totient Function Explained — Phi(n) Computation, Sieve Variant in O(N log log N) [Cryptography, Google]

Algorithm Statement#

Euler's totient function $\varphi(n)$ counts the positive integers up to $n$ that are coprime to $n$: \varphi(n) = |\\{k : 1 \le k \le n, \ \gcd(k, n) = 1\\}|.

Two regimes:

1. Single value: factor $n$ and apply $\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$ in $O(\sqrt{n})$.
2. All values up to $N$: sieve in $O(N \log \log N)$ similar to the Eratosthenes sieve.

Constraints:

• $1 \le n \le 10^{12}$ for single value.
• $1 \le N \le 10^7$ for the sieve variant.

Examples:

phi(1)  = 1
phi(9)  = 6      (coprime: 1, 2, 4, 5, 7, 8)
phi(10) = 4      (coprime: 1, 3, 7, 9)
phi(36) = 12     (n=36 = 2^2 * 3^2 → 36 * (1/2) * (2/3))

Why This Problem Matters#

Euler's totient function appears in three high-leverage interview contexts:

1. Cryptography. RSA encryption uses $\varphi(n)$ where $n = pq$ is the product of two primes; the security reduces to factoring $n$.
2. Modular inverse for composite moduli. Euler's theorem says $a^{\varphi(m)} \equiv 1 \pmod{m}$ when $\gcd(a, m) = 1$. So $a^{-1} \equiv a^{\varphi(m) - 1} \pmod{m}$, which extends Fermat to composite $m$.
3. Counting coprime pairs. Problems like LeetCode "Coprime Pairs in a Tree", or Codeforces problems counting fractions in lowest terms, all reduce to summations of $\varphi$.

Google has used $\varphi$ in distributed-systems interviews to derive the period of pseudo-random generators. Competitive programmers see it constantly in problems involving the Mobius function, divisor-sum identities, and the multiplicative inverse mod a non-prime.

The Core Insight#

Multiplicativity. $\varphi$ is a multiplicative function: if $\gcd(a, b) = 1$, then $\varphi(a b) = \varphi(a) \cdot \varphi(b)$. This reduces $\varphi(n)$ to its values on prime powers.

On a prime power. $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$. Reasoning: among $1, 2, \dots, p^k$, the multiples of $p$ are $p, 2p, \dots, p^{k-1} \cdot p$, exactly $p^{k-1}$ of them. The rest are coprime to $p^k$.

General formula. Combining:

For example, $\varphi(36) = 36 \cdot (1 - 1/2) \cdot (1 - 1/3) = 36 \cdot 1/2 \cdot 2/3 = 12$.

Sieve construction. Initialize phi[i] = i for all $i$. For each prime $p$ (detected when phi[p] == p), iterate over multiples $m = p, 2p, 3p, \dots$ and update phi[m] -= phi[m] / p. This is the same as multiplying by $(1 - 1/p)$, but using only integer arithmetic. Each composite $m$ gets touched once per distinct prime factor, so the total work is $O(N \log \log N)$.

Proof of Euler's product formula. Let $n = p_1^{e_1} \cdots p_k^{e_k}$. Inclusion-exclusion over the primes dividing $n$: count integers $\le n$ divisible by none of $p_1, \dots, p_k$. The result simplifies to $n \prod_i (1 - 1/p_i)$.

Visual Dry Run#

Compute $\varphi(60)$ via the formula. $60 = 2^2 \cdot 3 \cdot 5$.

phi(60) = 60 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5)
        = 60 * 1/2 * 2/3 * 4/5
        = 60 * 8/30
        = 16
 
Coprime check: count k in [1, 60] with gcd(k, 60) = 1.
{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59}
That is 16 values. Confirms phi(60) = 16.

Sieve up to $N = 10$.

Initial: phi = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 
p = 2 (phi[2] == 2 → prime)
  for m in 2,4,6,8,10:
    phi[m] -= phi[m] / 2
    phi[2] = 2 - 1 = 1
    phi[4] = 4 - 2 = 2
    phi[6] = 6 - 3 = 3
    phi[8] = 8 - 4 = 4
    phi[10] = 10 - 5 = 5
 
p = 3 (phi[3] == 3 → prime)
  phi[3] = 3 - 1 = 2
  phi[6] = 3 - 1 = 2
  phi[9] = 9 - 3 = 6
 
p = 5 (phi[5] == 5 → prime)
  phi[5] = 5 - 1 = 4
  phi[10] = 5 - 1 = 4
 
p = 7 (phi[7] == 7 → prime)
  phi[7] = 7 - 1 = 6
 
Final: phi = [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4]

Verify: $\varphi(6) = 2$ (coprime: 1, 5). $\varphi(10) = 4$ (coprime: 1, 3, 7, 9). Correct.

Solution (Optimal)#

Python — Single Value#

def phi(n: int) -> int:
    """Compute Euler's totient phi(n) in O(sqrt n)."""
    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      # leftover prime factor
    return result

Complexity: $O(\sqrt{n})$ time, $O(1)$ extra space.

Python — Sieve up to N#

def phi_sieve(N: int) -> list[int]:
    phi = list(range(N + 1))
    for p in range(2, N + 1):
        if phi[p] == p:                # p is prime
            for m in range(p, N + 1, p):
                phi[m] -= phi[m] // p
    return phi

Complexity: $O(N \log \log N)$ time, $O(N)$ space.

JavaScript — Single Value#

function phi(n) {
    let result = n;
    for (let p = 2; p * p <= n; p++) {
        if (n % p === 0) {
            while (n % p === 0) n = Math.floor(n / p);
            result -= Math.floor(result / p);
        }
    }
    if (n > 1) result -= Math.floor(result / n);
    return result;
}

JavaScript — Sieve#

function phiSieve(N) {
    const phi = Array.from({ length: N + 1 }, (_, i) => i);
    for (let p = 2; p <= N; p++) {
        if (phi[p] === p) {
            for (let m = p; m <= N; m += p) {
                phi[m] -= Math.floor(phi[m] / p);
            }
        }
    }
    return phi;
}

Common Mistakes#

1. Multiplying by $(1 - 1/p)$ in floats. Floating-point rounding gives the wrong integer answer. Always use the integer rewrite result -= result / p.
2. Reducing by every divisor instead of every prime divisor. The product $\prod (1 - 1/p)$ runs over distinct prime divisors only.
3. Forgetting the leftover prime. After the trial-division loop, if the residual $n > 1$ then $n$ itself is a prime factor.
4. Wrong base case. $\varphi(1) = 1$, not 0. The single value $1$ is coprime to itself by convention.
5. Using Fermat for inverse mod composite. Fermat requires the modulus to be prime. For composite $m$, use $a^{\varphi(m) - 1} \bmod m$ (provided $\gcd(a, m) = 1$).
6. Order of operations in the sieve. Update phi[m] -= phi[m] / p only before processing higher primes; the SPF-style sieve traversal order matters.

Interview Tips#

• State the multiplicativity of $\varphi$ early: "$\varphi(ab) = \varphi(a)\varphi(b)$ when $\gcd(a, b) = 1$." Interviewers respect when you reach for structure.
• For RSA-flavored questions, mention Carmichael's $\lambda(n)$ if asked — it is the smaller exponent that suffices for $a^{\lambda(n)} \equiv 1$.
• For sums like $\sum_{d \mid n} \varphi(d) = n$ (Euler's identity), cite it directly to save derivation time.
• If the problem is "count coprime pairs $(i, j)$ with $i, j \le N$", the answer is $\frac{2 \sum_{k=1}^{N} \varphi(k) - 1}{1}$. Memorize that.

Follow-up Questions#

Q1: Compute $a^{-1} \bmod m$ when $m$ is composite and $\gcd(a, m) = 1$. A: Use $a^{\varphi(m) - 1} \bmod m$. Or use Extended Euclidean — usually faster in practice because it does not require factoring $m$.

Q2: Show that $\sum_{d \mid n} \varphi(d) = n$. A: Group the integers $1, 2, \dots, n$ by the value of $\gcd(k, n)$. For each divisor $d$ of $n$, exactly $\varphi(n/d)$ integers have $\gcd = d$. Sum over $d$.

Q3: Compute $\varphi$ for all values up to $10^7$ in optimal time. A: Use the linear sieve, which extends the SPF sieve to compute $\varphi$ in $O(N)$.

Q4: Apply $\varphi$ to count fractions in lowest terms with denominator $\le N$. A: The Farey sequence count is $1 + \sum_{k=2}^{N} \varphi(k)$, computable in $O(N \log \log N)$ with the sieve.

Key Takeaways#

• $\varphi(n)$ counts integers in $[1, n]$ coprime to $n$, with the closed form $n \prod_{p \mid n} (1 - 1/p)$.
• Multiplicativity $\varphi(ab) = \varphi(a)\varphi(b)$ when $\gcd(a,b)=1$ reduces every computation to prime powers.
• The sieve variant runs in $O(N \log \log N)$ by initializing phi[i] = i then peeling off each prime via phi[m] -= phi[m] / p.
• Euler's theorem generalizes Fermat: $a^{\varphi(m)} \equiv 1 \pmod{m}$ when $\gcd(a, m) = 1$, enabling modular inverse for composite moduli.
• The identity $\sum_{d \mid n} \varphi(d) = n$ underpins divisor-sum problems and Mobius inversion.
• $\varphi$ is the bridge between number theory and cryptography (RSA, ElGamal) and competitive-programming counting problems.