Euler’s Totient Function Calculator — φ(n)
Compute Euler’s totient φ(n), the count of integers from 1 to n that are coprime to n, using the prime factorization and the product formula, with the list of coprime numbers for small n.
How it works
φ(n) = n · ∏ (1 − 1/p) over the distinct primes p dividing n · φ(pᵏ) = pᵏ⁻¹(p − 1) · φ is multiplicative: φ(ab) = φ(a)φ(b) when gcd(a, b) = 1 · φ(p) = p − 1 for a prime p
Euler’s totient φ(n) counts the integers from 1 to n that share no common factor with n other than 1. Because φ is multiplicative, it can be computed from the prime factorization: each distinct prime p removes the fraction 1/p of the numbers. The calculator factors n by trial division (fast up to 10¹²), applies the product formula and lists the coprime numbers for n ≤ 200. φ(n) is the order of the multiplicative group mod n and drives Euler’s theorem a^φ(n) ≡ 1 (mod n) and RSA key generation (Wolfram MathWorld, Totient Function).
Worked example
n = 36 = 2² × 3². φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12. Check with prime powers: φ(4) × φ(9) = 2 × 6 = 12. The 12 coprime numbers are 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35.
Sources: Wolfram MathWorld — Totient Function · OEIS A000010 — Euler totient function
Frequently asked questions
What is Euler’s totient function?
φ(n) is the number of positive integers up to n that are relatively prime to n (their gcd with n is 1). For example φ(9) = 6 because 1, 2, 4, 5, 7 and 8 are coprime to 9.
How do you calculate φ(n) quickly?
Factor n into primes and use φ(n) = n × ∏(1 − 1/p) over the distinct primes. For 100 = 2² × 5², φ(100) = 100 × 1/2 × 4/5 = 40.
What is φ of a prime number?
p − 1, because every number from 1 to p − 1 is coprime to a prime p. Conversely, φ(n) = n − 1 only when n is prime.
Where is the totient used?
In Euler’s theorem a^φ(n) ≡ 1 (mod n) for gcd(a, n) = 1, in reducing huge exponents modulo n, and in RSA, where the private key is the inverse of e modulo φ(pq) = (p − 1)(q − 1).
Related calculators
This calculator is for educational purposes. Double-check important results before acting on them.