Euler's Totient Function, in depth: the product formula, single-value and sieve computation, exponent reduction and why RSA uses λ(n)

Definition and first values

By definition, φ(n) is the number of k with 1 <= k <= n and gcd(k, n) = 1. The first values:

Two patterns jump out. For a prime p every smaller positive integer is coprime to it, so φ(p) = p - 1. And φ(1) = 1 by convention, because gcd(1, 1) = 1; code that special-cases n = 1 to return 0 is wrong. Values for prime powers follow from counting what is excluded: among 1 to p^k the only numbers sharing a factor with p^k are the multiples of p, and there are p^(k-1) of them, so φ(p^k) = p^k - p^(k-1). For 8 that gives 8 - 4 = 4.

The product formula

φ is multiplicative: if gcd(m, n) = 1 then φ(mn) = φ(m) φ(n). The Chinese remainder theorem gives the proof. It pairs each residue modulo mn with a unique pair of residues (modulo m, modulo n), and a residue is coprime to mn exactly when both halves are coprime to their moduli. So the coprime residues modulo mn are in one-to-one correspondence with pairs of coprime residues, and there are φ(m) times φ(n) of those.

Combining multiplicativity with the prime-power case gives the product formula over the distinct primes dividing n:

phi(n) = n * product over primes p | n of (1 - 1/p)

Worked example: 360 = 2^3 * 3^2 * 5, so φ(360) = 360 * (1/2) * (2/3) * (4/5) = 96. Only the distinct primes matter, not their exponents. Check it against the multiplicative form: φ(8) * φ(9) * φ(5) = 4 * 6 * 4 = 96. In integer code never multiply by a fraction; subtract instead, using result -= result // p, which stays exact because p divides the running result at every step.

Computing φ for one number

For a single n, factor it and apply the formula. Trial division up to the square root is enough for n around 10^12 to 10^14; beyond that, use a probabilistic factoriser such as Pollard's rho together with a Miller-Rabin primality test.

def phi(n):
    """Euler's totient by trial division. O(sqrt(n))."""
    if n < 1:
        raise ValueError("phi is defined for n >= 1")
    result, m, p = n, n, 2
    while p * p <= m:
        if m % p == 0:
            while m % p == 0:
                m //= p
            result -= result // p
        p += 1 if p == 2 else 2    # 2, then odd candidates only
    if m > 1:                      # one prime factor above sqrt(n) remains
        result -= result // m
    return result

assert [phi(i) for i in range(1, 13)] == [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]
assert phi(360) == 96 and phi(97) == 96

Two lines carry the correctness. Dividing m by p until it no longer divides makes each prime count once. The final check catches the one prime factor that can remain after the loop, larger than the square root of what is left; forgetting it is the most common bug in this function, and it breaks every prime and most composites: φ(6) would come out as 3.

Computing φ for every number up to N

When a problem needs φ for every number up to N, factoring each one costs far too much. A sieve applies the product formula to all multiples of each prime at once, mirroring the sieve of Eratosthenes:

def phi_table(N):
    """phi[i] for all 0 <= i <= N in O(N log log N)."""
    phi = list(range(N + 1))
    for p in range(2, N + 1):
        if phi[p] == p:                # untouched, so p is prime
            for j in range(p, N + 1, p):
                phi[j] -= phi[j] // p
    return phi

t = phi_table(400)
assert t[360] == 96 and t[1] == 1

A slot still equal to its index when the loop reaches it has not been touched by any smaller prime, so it is prime. Each multiple of p receives the factor (1 - 1/p) exactly once. The linear sieve variant reaches O(N) by visiting every composite once through its smallest prime factor and using φ(i p) = φ(i) p when p divides i, and φ(i) (p - 1) otherwise; it also yields the prime list, but the simpler version is usually fast enough. Memory dominates: 10^8 entries as 32-bit integers take 400 MB, so in Python use array('I') or NumPy rather than a list.

Euler's theorem and exponent reduction

Euler's theorem: if gcd(a, n) = 1 then a^φ(n) ≡ 1 (mod n). The proof is one idea. Multiplying every coprime residue by a permutes them, so the product of all coprime residues equals a^φ(n) times itself modulo n, and that product is invertible. Fermat's little theorem is the case n = p.

The practical use is shrinking exponents. To compute 7^222 mod 10, note φ(10) = 4 and 222 mod 4 = 2, so the answer is 7^2 = 49, which is 9 modulo 10. The condition matters. Try 2^100 mod 12: φ(12) = 4 and 100 mod 4 = 0, which suggests 2^0 = 1, but the true answer is 4, because 2 and 12 share a factor. The generalised rule handles any base: when b >= φ(m),

a^b ≡ a^((b mod φ(m)) + φ(m))   (mod m)        valid for every a, when b >= φ(m)

def capped(bases, cap):
    """min(true value of the tower, cap), without building huge integers."""
    if len(bases) == 1:
        return min(bases[0], cap)
    e, r = capped(bases[1:], 64), 1    # cap 64: 2**64 exceeds any phi we use
    for _ in range(e):
        r *= bases[0]
        if r >= cap:
            return cap
    return r

def tower_mod(bases, m):
    """bases[0]^(bases[1]^(...)) mod m via the generalised rule, recursively."""
    if m == 1:
        return 0
    if len(bases) == 1:
        return bases[0] % m
    f = phi(m)
    e = capped(bases[1:], f)           # exact exponent if it is below phi(m)
    if e >= f:                         # large exponent: reduce, then add phi back
        e = tower_mod(bases[1:], f) + f
    return pow(bases[0], e, m)

Applied to 2^100 mod 12: (100 mod 4) + 4 = 4, and 2^4 = 16, which is 4 modulo 12, as required. Checked by brute force for every modulus below 200, every base below 60 and every exponent up to three times the modulus, the rule held whenever b >= φ(m). Power towers of the form a^b^c mod m are the classic application: φ(φ(...φ(m))) falls to 1 in logarithmically many steps, so the recursion is shallow. The delicate part is deciding whether the exponent really is at least φ(m); capped answers that exactly without materialising the tower. Test any tower code against Python's exact integers on small inputs before trusting it.

Identities that become algorithms

A handful of identities turn counting problems into sums of φ.

• Divisor sum. sum of φ(d) over d | n equals n. Group the fractions k/n by their reduced denominator d; exactly φ(d) of them reduce to denominator d. For n = 12: 1 + 1 + 2 + 2 + 2 + 4 = 12.
• Farey sequences. The number of reduced fractions in [0, 1] with denominator at most n is 1 + φ(1) + ... + φ(n); for n = 8 that is 23. A sieved prefix sum answers it for every n at once.
• gcd sums. sum of gcd(i, n) for i = 1..n equals sum of d φ(n/d) over d | n, because exactly φ(n/d) values of i have gcd d. For n = 12 both sides equal 40, and the right side needs only the divisors.
• Group structure. When the group of units modulo n is cyclic, it has φ(φ(n)) generators. Primitive roots, and the discrete-log algorithms built on them, are covered in primitive roots and discrete logarithms.

φ, λ and RSA

Textbook RSA computes d = e^(-1) mod φ(N). Any d that inverts e modulo the Carmichael function λ(N) = lcm(p - 1, q - 1) also works, because λ(N) is the smallest exponent that sends every unit to 1. For p = 61, q = 53 and e = 17, N = 3233, φ(N) = 3120 and λ(N) = 780. Inverting modulo φ gives d = 2753; modulo λ gives d = 413, and 2753 mod 780 = 413. Both decrypt correctly. The λ value is the smallest valid exponent, and FIPS 186 key generation computes d modulo the lcm form. The toy key sizes here are for arithmetic only.

φ(N) must stay secret. Given N and φ(N), the primes fall out: p + q = N - φ(N) + 1 and pq = N, so p and q are the roots of a quadratic. Computing φ(N) is therefore exactly as hard as factoring N, which is the reason the sieve and the formula are useless to an attacker on a 2048-bit modulus.

Failure modes

• Reducing exponents with a non-coprime base. Plain Euler reduction gave 1 for 2^100 mod 12; the answer is 4. Use the generalised rule or check the gcd first.
• Forgetting the last prime factor. The m > 1 check after trial division.
• Floating-point formulas. n * (1 - 1/p) in floats loses exactness past about 2^53; subtract with integer division instead.
• Overflow in fixed-width code. p * p <= m overflows near 2^63; compare p <= m / p.
• Using φ where λ is meant. Correct but non-minimal private exponents, and comparisons against reference keys fail.
• Sieving too far. A table to 10^9 rarely fits; use the single-value function or a segmented approach for sparse queries.

Trade-offs

Choose by query pattern, not by elegance: one query on a large n wants factoring; many queries up to a bound want the table. The broader toolkit sits in number theory for programmers.

What to do next

1. Implement phi by trial division and test it on 1 to 12, on 360 and on a prime times a large prime.
2. Implement phi_table and cross-check it against phi for every n up to 10^4.
3. Brute-force-check the generalised exponent rule for small moduli before using it in production code.
4. Grep your codebase for exponent reductions modulo φ and confirm each one either proves coprimality or uses the generalised rule.
5. Recompute the toy RSA key with both φ and λ and confirm that d = 2753 and d = 413 both decrypt.
6. Use the divisor-sum identity as a property test on any totient code you write.