Euler’s Totient Function Calculator
Enter a positive integer n to compute φ(n), the count of integers from 1 to n that are relatively prime to n.
What is Euler’s phi (totient) function?
Euler’s phi function, written as φ(n), gives the number of integers between 1 and n that share no common factor with n other than 1. In other words, it counts how many numbers are coprime to n.
For example, if n = 9, the numbers from 1 to 9 that are coprime with 9 are 1, 2, 4, 5, 7, and 8. So, φ(9) = 6.
How this Euler phi calculator works
This calculator uses prime factorization and Euler’s product formula. Instead of checking every integer one-by-one (which can be slow for large values), it factors n and applies:
φ(n) = n × ∏(1 - 1/p), where p runs over the distinct prime factors of n.
- Step 1: Factor n into primes.
- Step 2: Keep only the distinct prime factors.
- Step 3: Apply the product formula above.
- Step 4: Return an exact integer result.
Quick examples
- n = 36 → prime factors are 2 and 3, so φ(36) = 36(1 - 1/2)(1 - 1/3) = 12
- n = 97 (prime) → φ(97) = 96
- n = 1 → by definition, φ(1) = 1
Why Euler’s totient matters
1) Cryptography (RSA)
The RSA algorithm depends on totients. In classic textbook form, for two primes p and q, the modulus is n = pq and φ(n) = (p - 1)(q - 1). This value helps define the private exponent.
2) Modular arithmetic
Euler’s theorem says if gcd(a, n) = 1, then aφ(n) ≡ 1 (mod n). This result is a cornerstone in number theory and computational mathematics.
3) Structure of multiplicative groups
φ(n) is also the size of the multiplicative group of integers modulo n. That makes it important in abstract algebra and algorithm design.
Tips for using this calculator
- Use whole numbers only (no decimals, negatives, or symbols).
- For small n, the calculator also shows all coprime numbers for intuition.
- Large inputs are supported with exact integer arithmetic.
FAQ
Is φ(n) always even?
For n > 2, yes, φ(n) is always even.
What if n is prime?
If n is prime p, then every number from 1 to p-1 is coprime to p, so φ(p) = p - 1.
Can I use this for teaching or homework checks?
Absolutely. The factorization and formula lines help show how the answer is produced, not just the final result.
Final thoughts
If you are studying number theory, preparing for cryptography coursework, or just exploring mathematical functions, Euler’s totient is one of the most useful arithmetic functions to master. Try a few values above and notice how prime factors directly shape the output of φ(n).