Euler's Totient Function Calculator

Euler's Totient function φ(n) is an arithmetic function that counts how many positive integers up to n are coprime with n — meaning their greatest common divisor (GCD) with n is 1. For example, φ(6) = 2 because only 1 and 5 are coprime with 6 among the integers 1 through 6.

The standard formula uses the prime factorization of n. If n = p₁^k₁ × p₂^k₂ × … × pₘ^kₘ, then φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … × (1 − 1/pₘ). Each distinct prime factor p reduces the count by excluding multiples of p that cannot be coprime with n.

When n is prime, every integer from 1 to n−1 is coprime with n, so φ(n) = n − 1. For example, φ(7) = 6 and φ(13) = 12. This is one of the simplest and most important special cases of the totient function.

Two integers a and b are coprime (also called relatively prime) if their greatest common divisor is 1 — that is, they share no common prime factors. For example, 8 and 15 are coprime because gcd(8, 15) = 1, even though neither is a prime number itself.

Euler's theorem states that if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). This result is foundational in number theory and cryptography — it underpins the RSA encryption algorithm, which relies on the difficulty of computing φ(n) when n is a product of two large primes.

Key properties include: φ(1) = 1; φ(p) = p − 1 for any prime p; φ(mn) = φ(m)φ(n) when gcd(m,n) = 1 (multiplicativity); and the sum of φ(d) over all divisors d of n equals n. Also, φ(n) is always even for n > 2.

The inverse totient problem asks: given a value m, find all integers n such that φ(n) = m. Unlike computing φ(n) which is straightforward, finding all pre-images of a given totient value is significantly harder and may yield multiple solutions or none at all.

Only for n = 1. φ(1) = 1 = n because by convention, 1 is considered coprime with itself. For all n > 1, φ(n) < n because at least n itself is excluded (since gcd(n, n) = n ≠ 1).