Euler's Totient Function Calculator
Compute Euler's totient φ(n), the count of integers from 1 to n that share no common factor with n. Essential for RSA key generation, modular arithmetic, and exploring multiplicative number theory.
About this calculator
Euler's totient function φ(n) counts positive integers up to n that are coprime to n, i.e., gcd(k, n) = 1. Using the prime factorization n = p₁^a₁ × p₂^a₂ × …, the formula is φ(n) = n × ∏(1 − 1/pᵢ) over all distinct prime factors pᵢ. For a prime p, φ(p) = p − 1 because every integer from 1 to p−1 is coprime to p. The function is multiplicative: if gcd(m, n) = 1 then φ(mn) = φ(m)φ(n). Euler's theorem states that for any a coprime to n, a^φ(n) ≡ 1 (mod n), which is the foundation of RSA encryption. The calculator finds prime factors via trial division, applying the product formula to obtain the exact integer result.
How to use
Calculate φ(36). Factor 36 = 2² × 3². The distinct prime factors are 2 and 3. Apply the formula: φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 0.5 × 0.667 = 12. Enter 36 as the input number; the calculator confirms φ(36) = 12. The 12 integers coprime to 36 in [1, 36] are 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35. Enable 'Show Coprime Numbers' to display the full list.
Frequently asked questions
How is Euler's totient function used in RSA encryption?
RSA key generation selects two large primes p and q, then computes n = p × q and φ(n) = (p−1)(q−1). The public exponent e is chosen so that gcd(e, φ(n)) = 1, and the private exponent d satisfies d × e ≡ 1 (mod φ(n)). Encryption raises a message m to the power e modulo n; decryption raises the ciphertext to d modulo n. Security rests on the difficulty of computing φ(n) without knowing p and q, which requires factoring n — a computationally intractable problem for large n.
What is the relationship between Euler's totient function and prime numbers?
For any prime p, φ(p) = p − 1 because every integer from 1 to p−1 is coprime to p. For a prime power p^k, φ(p^k) = p^k − p^(k−1) = p^(k−1)(p−1), since only multiples of p share a factor with p^k. The multiplicative property φ(mn) = φ(m)φ(n) when gcd(m,n)=1 means totients of composite numbers can always be computed from their prime factorizations. This tight connection to primes makes φ central to analytic number theory, including the distribution of prime numbers.
Why does Euler's theorem state that a^φ(n) ≡ 1 (mod n) when gcd(a,n) = 1?
Euler's theorem is a generalization of Fermat's Little Theorem. It arises because the φ(n) integers coprime to n form a multiplicative group under modular multiplication. Multiplying every element of this group by a (also coprime to n) merely permutes the group. The product of all group elements taken both ways must be equal mod n, and cancelling those elements yields a^φ(n) ≡ 1 (mod n). This result is used not only in cryptography but also in simplifying large modular exponentiations in competitive mathematics.