Euler's Totient Function
Calculate Euler's totient φ(n) — the count of integers from 1 to n that share no common factor with n. Essential for RSA key generation and number theory problems.
About this calculator
Euler's totient function φ(n) counts how many integers in [1, n] are coprime to n (share no factor other than 1). The formula uses the prime factorization of n: φ(n) = n × ∏(1 − 1/p) for each distinct prime factor p of n. For example, if n = 12 = 2² × 3, then φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 4. The algorithm finds prime factors by trial division up to √n, then applies the product formula to the original n. Key properties: φ(1) = 1, φ(p) = p − 1 for any prime p, and φ is multiplicative for coprime inputs. In RSA encryption, φ(n) defines the order of the multiplicative group used for key derivation.
How to use
Enter n = 36. Its prime factors are found by trial division: 36 = 2² × 3². Apply the formula: φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 0.5 × 0.667 = 12. You can verify by listing integers 1–36 coprime to 36: {1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35} — exactly 12 values. Type any positive integer and the calculator returns φ(n) instantly.
Frequently asked questions
How is Euler's totient function used in RSA encryption?
In RSA, you choose two large primes p and q, compute n = p × q, then derive φ(n) = (p − 1)(q − 1). The public exponent e and private exponent d satisfy e × d ≡ 1 (mod φ(n)), meaning d is the modular inverse of e. Knowing φ(n) is computationally hard without knowing p and q, which is the security foundation of RSA. An attacker who factors n can compute φ(n) and break the key, which is why large primes are essential.
What is the difference between Euler's totient and Carmichael's function?
Both functions describe the structure of modular multiplicative groups, but Carmichael's function λ(n) gives the smallest exponent m such that a^m ≡ 1 (mod n) for all coprime a. Euler's φ(n) always satisfies a^φ(n) ≡ 1 (mod n) by Euler's theorem, but λ(n) may be a proper divisor of φ(n). For prime n they are equal: φ(p) = λ(p) = p − 1. Modern RSA implementations sometimes use λ(n) instead of φ(n) for slightly smaller private exponents.
Why does φ(n) equal n − 1 for prime numbers?
Every integer from 1 to p − 1 is coprime to a prime p, because p has no divisors other than 1 and itself. Therefore all p − 1 integers in that range satisfy gcd(k, p) = 1, giving φ(p) = p − 1. This property makes primes especially useful in modular arithmetic, since all non-zero residues form a complete multiplicative group. It also explains why Fermat's Little Theorem states a^(p−1) ≡ 1 (mod p) for any a not divisible by p.