Compute Euler's totient φ(n) — the count of integers up to n that are coprime to n.
Euler's totient function φ(n) counts the integers from 1 to n that are coprime to n (share no common factor other than 1). It is computed efficiently via the product formula: φ(n) = n × ∏(1 − 1/p) over all distinct prime factors p of n. For a prime p, φ(p) = p − 1. The totient is fundamental in RSA cryptography, where it determines the modular inverse of the public exponent.
Euler's product formula
φ(n) = n × ∏(1 − 1/p) for each distinct prime factor p of n
φ(1) = 1 by convention — the only integer from 1 to 1 is 1 itself, and gcd(1, 1) = 1.
In RSA, the private key d is the modular inverse of the public exponent e modulo φ(n), where n = p×q for two large primes. Knowing φ(n) is equivalent to being able to factor n.