Euler's Totient Formula Proof: Step-by-Step Derivation

Why Euler's Totient Formula Matters

Every number theorist encounters this identity: φ(n) = n × Π(1 - 1/p) for prime factors p of n. But why does this elegant formula work? After analyzing this advanced lecture, I'll demonstrate how multiplicative properties and inclusion-exclusion principle unlock its proof. Understanding this derivation is crucial—it transforms how you approach coprime counting problems in cryptography and competitive mathematics.

The Foundation: Prime Powers and Coprimes

First, consider prime powers pᵏ. The video correctly establishes φ(pᵏ) = pᵏ - pᵏ⁻¹ since only multiples of p are non-coprime. This becomes our building block.

Crucially, the totient function is multiplicative: if m and n are coprime, φ(mn) = φ(m)φ(n). This multiplicative property (cited in the lecture from fundamental number theory) lets us decompose composite numbers. For example:

• φ(100) = φ(4×25) = φ(4)φ(25) = 2 × 20 = 40
• Non-coprime pairs like (10,100) are automatically excluded

Deriving the General Formula

For n = p₁ᵃ¹p₂ᵃ²...pᵏᵃᵏ, we apply inclusion-exclusion:

1. Start with all numbers: n
2. Subtract fractions divisible by each pᵢ: n/pᵢ
3. Add back overlaps (divisible by pᵢpⱼ): n/(pᵢpⱼ)
4. Subtract triple intersections, etc.

This telescoping series condenses to n(1 - 1/p₁)(1 - 1/p₂)...(1 - 1/pₖ). The video's example with n=30 showcases this perfectly:

• Initial count: 30
• Remove multiples of 2,3,5: 30 - 15 - 10 - 6
• Add 2-3/3-5/2-5 overlaps: +5 + 3 + 2
• Subtract 2-3-5 intersection: -1 → φ(30)=8

Practical tip: Always factorize n completely before applying the formula. For n=100=2²5²:
φ(100) = 100 × (1 - 1/2) × (1 - 1/5) = 100 × 1/2 × 4/5 = 40

Computational Efficiency and Edge Cases

Beyond the video, this formula optimizes coprime counting. A brute-force check runs in O(n) time, while factorization + formula is O(√n). But note two key nuances:

1. φ(1) = 1 (convention since 1 is coprime to itself)
2. For prime p, φ(p) = p-1 aligns with the formula

Implementation gotcha (as shown in coding segment): When writing totient functions, first handle factorization. Python example:

def phi(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
    return result

This avoids floating-point errors by using integer division. The video's approach worked but used unnecessary casts.

Essential Applications Checklist

1. RSA Cryptography: Key generation uses φ(n) for modulus calculations
2. Primitive Roots: Find generators modulo n using φ(φ(n))
3. Diophantine Equations: Solve ax ≡ b mod m using coprime conditions

Recommended Resources

• Introduction to Analytic Number Theory (Apostol): Chapter 2 explains totient's analytic properties. Ideal for proof rigor.
• Project Euler Problems 69-72: Totient-focused coding challenges to test implementation skills.
• Crypto.stackexchange.com: Real-world discussions on φ(n) in encryption schemes.

Mastering this derivation reveals deeper patterns in multiplicative functions. When implementing totient calculations, which step—prime factorization or product computation—do you anticipate being most challenging? Share your approach in the comments!