Euler's totient function, written φ(n), counts how many positive integers up to n share no common factor with n. It looks like a simple counting exercise, but it underpins modular arithmetic, Euler's generalization of Fermat's little theorem, and the key-generation step of RSA cryptography. This calculator computes φ(n) via prime factorization, shows the step-by-step derivation, and — for small n — lists every coprime integer directly.
What φ(n) actually counts
φ(n) counts the positive integers k in the range 1 ≤ k ≤ n for which gcd(k, n) = 1 — that is, k and n are coprime. For n = 1, φ(1) = 1 by convention. For a prime p, every integer below it is automatically coprime, so φ(p) = p − 1. This calculator's Coprime List tab lists these integers directly whenever n is small enough (up to 2,000) to display them all.
How prime factorization gives the formula
The fastest way to compute φ(n) for a large n isn't to check every integer for coprimality — it's to prime-factorize n first. Euler's totient is a multiplicative function, meaning φ(mn) = φ(m)φ(n) whenever gcd(m, n) = 1. Combined with the fact that φ(p^k) = p^k − p^(k-1) = p^k(1 − 1/p) for any prime power, this gives the general formula φ(n) = n·Π(1 − 1/p) over each distinct prime factor p of n — the exponents themselves drop out of the formula entirely. This calculator's Prime Factorization tab shows exactly this derivation, term by term, for whatever n you enter.
Why cryptography cares about φ(n)
RSA encryption generates a public/private key pair from two large distinct primes p and q, letting n = pq be the public modulus. The private exponent is derived using φ(n) = (p−1)(q−1) — the same formula this calculator's interpretation line highlights whenever n factors into exactly two distinct primes. In real RSA implementations p and q are hundreds of digits long, but the underlying totient calculation is identical to the one shown here for small examples. Related tools like the Prime Factorization Calculator and the Modulo Calculator are useful for exploring the other number-theory building blocks behind modular arithmetic and cryptography.