Euler Totient (φ) Calculator
Enter a positive integer to compute Euler’s phi (totient) function, φ(n): the number of integers from 1 to n that are coprime with n.
Tip: Press Enter to calculate quickly.
What is Euler’s phi function?
Euler’s phi function (also called the totient function) is written as φ(n). It counts how many numbers between 1 and n are relatively prime to n. Two numbers are relatively prime if their greatest common divisor is 1.
For example, φ(9) = 6 because these values are coprime with 9:
- 1, 2, 4, 5, 7, 8
Key formula behind this calculator
The fastest practical way to compute φ(n) is by prime factorization:
If n has prime factors p1, p2, ..., then we multiply n by a correction factor for each distinct prime. This avoids checking every number from 1 to n one by one.
Examples
- φ(13) = 12 because 13 is prime, and for any prime p, φ(p) = p - 1.
- φ(12) = 4 because 12 = 22 × 3, so φ(12) = 12(1 - 1/2)(1 - 1/3) = 4.
- φ(36) = 12 because 36 = 22 × 32, so φ(36) = 36(1 - 1/2)(1 - 1/3) = 12.
Why Euler phi matters
The totient function appears throughout number theory and cryptography.
- RSA encryption: Security and key generation rely on properties involving φ(n).
- Modular arithmetic: Used in Euler’s theorem: aφ(n) ≡ 1 (mod n) when gcd(a, n) = 1.
- Mathematical problem solving: Common in olympiad and algorithmic coding tasks.
How this tool calculates φ(n)
1) Prime factorization
The calculator breaks n into prime factors and records the distinct primes.
2) Totient update rule
Starting with result = n, for each distinct prime p dividing n, it applies:
This is mathematically equivalent to multiplying by (1 - 1/p) and produces an exact integer answer.
Common mistakes
- Using non-integer or negative values (the standard totient is for positive integers).
- Confusing φ(n) with the count of primes up to n (that is a different function).
- Forgetting that only distinct prime factors matter in the product formula.
Quick reference values
- φ(1) = 1
- φ(2) = 1
- φ(8) = 4
- φ(10) = 4
- φ(15) = 8
- φ(25) = 20
Final note
If you are learning number theory, try several inputs and compare results for prime numbers, prime powers, and highly composite numbers. Seeing those patterns is one of the best ways to build intuition for Euler’s totient function.