Euler's Totient Function Calculator
Computes Euler's totient φ(n), the count of integers from 1 to n that share no common factor with n. Essential for RSA encryption key generation and modular arithmetic problems.
About this calculator
Euler's totient function φ(n) counts positive integers up to n that are coprime to n (i.e., share no prime factor with n). 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 with prime factors 2 and 3, then φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 4. This function is fundamental to Euler's theorem, which states that a^φ(n) ≡ 1 (mod n) for any a coprime to n. In cryptography, φ(n) determines the order of the multiplicative group modulo n, underpinning the security of RSA encryption.
How to use
Suppose you want φ(36). First, find the prime factors of 36: 2 and 3. Apply the formula: φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 0.5 × 0.6667 = 12. This means 12 integers between 1 and 36 are coprime to 36. Enable 'Show Prime Factorization' to verify the factors 2 and 3. Enable 'List Coprime Numbers' to display all 12 integers explicitly (e.g., 1, 5, 7, 11, 13, …).
Frequently asked questions
What is Euler's totient function used for in real life?
Euler's totient function is central to public-key cryptography, especially RSA encryption. When generating RSA keys, the modulus n = p × q uses φ(n) = (p−1)(q−1) to compute the private key exponent. It also appears in primality testing and the analysis of cyclic groups in abstract algebra.
How do you calculate φ(n) when n is a prime number?
For any prime p, every integer from 1 to p−1 is coprime to p, so φ(p) = p − 1. This is the simplest case of the totient formula: φ(p) = p × (1 − 1/p) = p − 1. For instance, φ(13) = 12. This also means the multiplicative group modulo a prime is always cyclic of order p−1.
Why does φ(n) matter for modular exponentiation and RSA?
Euler's theorem guarantees that a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1. RSA exploits this by choosing encryption exponent e and decryption exponent d such that e × d ≡ 1 (mod φ(n)). Knowing φ(n) allows efficient inversion of exponentiation, which is computationally infeasible without knowing the prime factorization of n.