Euler Totient Function Calculator

What is Euler's totient function?

Euler's totient function φ(n) counts the positive integers up to n that are coprime to n, meaning their greatest common divisor with n is 1. For n = 12 the numbers 1, 5, 7 and 11 qualify, so φ(12) = 4. For a prime p every smaller positive integer is coprime to it, so φ(p) = p − 1.

The function appears all over number theory and cryptography. It gives the size of the group of units modulo n, it appears in Euler's theorem, and in RSA the private exponent d is the inverse of the public exponent e modulo φ(n).

The product formula

If n = p₁^e₁ p₂^e₂ … pₖ^eₖ, then φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … × (1 − 1/pₖ). Equivalently, φ is multiplicative: φ(ab) = φ(a)φ(b) whenever gcd(a, b) = 1, and for a prime power φ(p^e) = p^e−1(p − 1). The calculator applies both versions to the prime factorization of n and checks that they agree.

Example: 360 = 2³ × 3² × 5, so φ(360) = 4 × 6 × 4 = 96. Using the other form, 360 × (1/2) × (2/3) × (4/5) = 96.

Euler's theorem and RSA

Euler's theorem states that a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1. Fermat's little theorem is the special case n = p, where it reads a^p−1 ≡ 1 (mod p). In RSA, with n = pq for two primes, φ(n) = (p − 1)(q − 1). Choosing e coprime to φ(n) and d with ed ≡ 1 (mod φ(n)) makes decryption undo encryption, because m^ed = m^{1 + kφ(n)} ≡ m (mod n).

Checking the answer

For n up to 200 000 the calculator also counts the coprime integers directly, one gcd at a time, and confirms the formula. For small n up to 60 it prints the full list of coprime residues so you can compare with a hand count. Larger values rely on the exact formula, which is reliable for any size once n is factored.