Chapter 124

Euler's Totient Function

φ(n) counts integers 1 ≤ k ≤ n where gcd(k, n) = 1. φ(p) = p-1 for prime p. φ(n) = n × Π(1 − 1/p) for prime factors p. Used in Euler's theorem and modular inverses.

Computing φ(n) via Prime Factors

C++ — Euler's totient (single value)

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

// O(√N). For all values up to N, use the sieve (next chapter).