What is Euler's Totient function?
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. See also our Remainder Calculator.
How is φ(n) calculated?
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.
What is φ(n) when n is prime?
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.
What are two integers coprime (relatively prime)?
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. You might also find our Inverse Modulo Calculator useful.
What is Euler's Totient theorem used for?
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.
What are some key properties of Euler's Totient function?
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.
What is the inverse totient problem (Inverse Phi)?
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.
Can φ(n) ever equal n?
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).