Euler's Totient Function
Calculate φ(n) - the count of integers from 1 to n that are coprime to n.
Enter a positive integer (max 1,000,000)
Euler's totient function φ(n), also called Euler's phi function, counts the number of integers from 1 to n that are relatively prime (coprime) to n. Two numbers are coprime if their greatest common divisor (GCD) is 1.
Formula: For n with prime factorization n = p₁^k₁ × p₂^k₂ × ... × pₘ^kₘ, the totient is calculated as:
φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₘ)
Or equivalently:
φ(n) = p₁^(k₁-1) × (p₁-1) × p₂^(k₂-1) × (p₂-1) × ...
Special Cases:
- φ(1) = 1 (by convention)
- φ(p) = p - 1 for any prime p
- φ(p^k) = p^(k-1) × (p - 1) for prime powers
Applications: Euler's totient function is fundamental in number theory and cryptography. It's used in RSA encryption, where the security relies on the difficulty of computing φ(n) for large n without knowing its prime factorization.
Euler's Theorem: For any integer a coprime to n: a^φ(n) ≡ 1 (mod n). This generalizes Fermat's Little Theorem and is the mathematical foundation of RSA.
What does Euler's totient function count?
Euler's totient function phi(n) counts how many integers from 1 to n are coprime to n (share no common factors with n except 1). For example, phi(12) = 4 because 1, 5, 7, and 11 are the only numbers from 1-12 that share no factors with 12.
Why is Euler's totient function important in cryptography?
The totient function is crucial for RSA encryption. To encrypt and decrypt messages, RSA uses the fact that a^phi(n) = 1 (mod n) when a and n are coprime. Computing phi(n) is easy if you know n's prime factors but very hard otherwise - this asymmetry is what makes RSA secure.
What is the formula for Euler's totient function?
For n with prime factorization n = p1^k1 * p2^k2 * ... * pm^km, phi(n) = n * (1-1/p1) * (1-1/p2) * ... * (1-1/pm). Equivalently, phi(n) = n * product of (1 - 1/p) for each prime p dividing n.
What is Euler's theorem?
Euler's theorem states that if a and n are coprime, then a^phi(n) = 1 (mod n). This generalizes Fermat's Little Theorem (where n is prime). It's fundamental in modular arithmetic and is used to find modular inverses and solve congruence equations.