Euler's Totient Calculator | φ(n), Coprimes & Euler's Theorem
Compute Euler's totient function φ(n) — the count of integers from 1 to n that are coprime with n. Shows the prime factorization method, lists all coprimes for n ≤ 500, demonstrates multiplicativity φ(mn) = φ(m)φ(n), and verifies Euler's theorem aᵠ⁽ⁿ⁾ ≡ 1 (mod n) for any chosen a.
What Is the Euler's Totient Calculator | φ(n), Coprimes & Euler's Theorem?
Euler's totient φ(n) counts the positive integers up to n that are coprime with n (share no common factor other than 1). It is multiplicative: φ(mn) = φ(m)φ(n) when gcd(m,n) = 1, and satisfies the divisor sum ∑_{d|n} φ(d) = n. Euler's theorem states that aᵠ⁽ⁿ⁾ ≡ 1 (mod n) for any a coprime to n.
Formula
φ(n) = n × ∏(1 − 1/p) for all primes p dividing n
How to Use
- 1
Enter a positive integer n in the top input field (supports up to 10,000,000).
- 2
Optionally enter a base a (default 5) for the Euler's theorem verification panel.
- 3
Optionally enter m to check multiplicativity: φ(mn) = φ(m)·φ(n) when gcd(m,n) = 1.
- 4
Click "Compute φ(n)" or press Enter.
- 5
Read φ(n) from the large result tile along with the prime factorization formula.
- 6
For n ≤ 500, view or expand the full list of integers coprime with n.
- 7
Review the divisor sum table confirming ∑_{d|n} φ(d) = n.
Enter any positive integer n (up to 10,000,000) to compute φ(n). Optionally enter a base a to verify Euler's theorem, and a value m to check multiplicativity φ(mn) = φ(m)φ(n). For n ≤ 500 the full list of coprime integers is displayed. The divisor sum property is shown for n ≤ 5,000.
Example Calculation
For n = 12: prime factorization is 2² × 3, so φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4. The four coprimes are {1, 5, 7, 11}. Euler's theorem: 5⁴ = 625 = 52 × 12 + 1, so 5⁴ mod 12 = 1 ✓. Divisor sum: φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) = 1+1+2+2+2+4 = 12 ✓.
Understanding Euler's Totient | φ(n), Coprimes & Euler's Theorem
Values of φ(n) for n = 1 to 20
| n | φ(n) | Coprime integers | Note |
|---|---|---|---|
| 1 | 1 | {1} | φ(1) = 1 by convention |
| 2 | 1 | {1} | First prime, φ(p)=p−1=1 |
| 3 | 2 | {1,2} | Prime |
| 4 | 2 | {1,3} | φ(4)=φ(2²)=2¹(2−1)=2 |
| 5 | 4 | {1,2,3,4} | Prime |
| 6 | 2 | {1,5} | φ(6)=φ(2)×φ(3)=1×2=2 |
| 7 | 6 | {1,2,3,4,5,6} | Prime |
| 8 | 4 | {1,3,5,7} | φ(2³)=2²(2−1)=4 |
| 9 | 6 | {1,2,4,5,7,8} | φ(3²)=3(3−1)=6 |
| 10 | 4 | {1,3,7,9} | φ(10)=φ(2)×φ(5)=4 |
| 12 | 4 | {1,5,7,11} | φ(12)=φ(4)×φ(3)=2×2=4 |
| 16 | 8 | {1,3,5,7,9,11,13,15} | φ(2⁴)=2³(2−1)=8 |
| 18 | 6 | {1,5,7,11,13,17} | φ(2)×φ(3²)=1×6=6 |
| 20 | 8 | {1,3,7,9,11,13,17,19} | φ(4)×φ(5)=2×4=8 |
Special cases and key formulas
| Case | Formula | Example |
|---|---|---|
| Prime p | φ(p) = p − 1 | φ(7) = 6 |
| Prime power p^k | φ(pᵏ) = pᵏ⁻¹(p − 1) | φ(8) = φ(2³) = 4 |
| Coprime m, n | φ(mn) = φ(m)·φ(n) | φ(12) = φ(4)·φ(3) = 4 |
| General n | φ(n) = n ∏(1 − 1/p) over primes p|n | φ(30) = 30·(1−½)·(1−⅓)·(1−⅕) = 8 |
| Divisor sum | ∑_{d|n} φ(d) = n | ∑_{d|12} φ(d) = 1+1+2+2+4+2 = 12 |
| Euler's theorem | aᵠ⁽ⁿ⁾ ≡ 1 (mod n) when gcd(a,n)=1 | 5⁴ = 625 ≡ 1 (mod 12) |
| Fermat small thm | aᵖ⁻¹ ≡ 1 (mod p) for prime p∤a | 2⁶ = 64 ≡ 1 (mod 7) |
Applications of Euler's totient function
- ›RSA cryptography: The RSA key generation computes φ(n) = φ(p)·φ(q) = (p−1)(q−1) for large primes p, q. The private exponent d satisfies e·d ≡ 1 (mod φ(n)).
- ›Primitive roots: An integer g is a primitive root mod n if its order equals φ(n), i.e., g^φ(n) ≡ 1 but no smaller power works. Used in Diffie-Hellman key exchange.
- ›Order of elements: The order of any a coprime to n divides φ(n) (Lagrange). This bounds modular exponentiation cycle lengths.
- ›Counting necklaces: Burnside's lemma uses Euler's totient to count equivalence classes of cyclic patterns (necklaces, bracelets).
- ›Cyclotomic polynomials: The n-th cyclotomic polynomial Φₙ(x) has degree φ(n) and its roots are the primitive n-th roots of unity.
- ›Modular inverses: When gcd(a,n)=1, the inverse of a mod n is a^(φ(n)−1) mod n, computable efficiently with fast exponentiation.
Frequently Asked Questions
What does Euler's totient function φ(n) calculate?
φ(n) counts how many integers from 1 to n are coprime with n — they share no common factor other than 1. For example φ(12) = 4 because only 1, 5, 7, 11 are coprime with 12. It equals n multiplied by (1 − 1/p) for every distinct prime p dividing n.
What is the formula for φ(n) using prime factorization?
If n = p₁^k₁ × p₂^k₂ × … × pₘ^kₘ, then φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × … × (1 − 1/pₘ). For a prime p: φ(p) = p − 1. For a prime power: φ(pᵏ) = pᵏ⁻¹(p − 1). The function is completely multiplicative on coprime inputs.
What is Euler's theorem and why does it matter?
Euler's theorem states that if gcd(a, n) = 1, then aᵠ⁽ⁿ⁾ ≡ 1 (mod n). It generalizes Fermat's little theorem (which requires n to be prime). The theorem underlies RSA encryption: given e·d ≡ 1 (mod φ(n)), decrypting (mᵉ)ᵈ = m^(ed) ≡ m (mod n) follows directly from Euler's theorem.
Why is φ multiplicative and what does that mean?
φ is a multiplicative function: φ(mn) = φ(m)·φ(n) whenever gcd(m, n) = 1. This allows computing φ(n) by factoring n and applying the formula prime factor by prime factor. It does NOT hold when m and n share factors — for example φ(4) = 2 but φ(2)·φ(2) = 1, since gcd(2,2) ≠ 1.
What is the divisor sum property of φ?
For any positive integer n, the sum of φ(d) over all divisors d of n equals n: ∑_{d|n} φ(d) = n. For n = 12 with divisors {1,2,3,4,6,12}: φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) = 1+1+2+2+2+4 = 12. This identity has a combinatorial proof: every integer from 1 to n belongs to exactly one equivalence class defined by gcd(k,n) = d.
You Might Also Like
Explore 360+ Free Calculators
From math and science to finance and everyday life — all free, no account needed.