Euler's Totient Function Calculator – Compute φ(n) Online

Calculate Euler's totient function φ(n) for any integer with our free online calculator. Find the count of integers up to n that share no common factor with n, with step-by-step solutions and coprime listings.

Enter a positive integer (n):

Supports numbers up to 100,000

Understanding Euler's Totient Function

Euler's totient function, written as φ(n) (phi of n), counts how many positive integers up to n are coprime to n. Two numbers are coprime if their greatest common divisor (GCD) is 1 – meaning they share no common factors other than 1.

For example, φ(12) = 4 because among the numbers 1 through 12, only four are coprime to 12: namely 1, 5, 7, and 11. The others (2, 3, 4, 6, 8, 9, 10, 12) all share a common factor with 12.

The Totient Formula

φ(n) = n × ∏(1 - 1/p) for each distinct prime p dividing n

How to Calculate

1. Find the prime factorization of n
2. List each distinct prime factor (ignore repeats)
3. For each prime p, multiply by (1 - 1/p)
4. Simplify to get φ(n)

Special Cases

• φ(1) = 1 (by definition)
• φ(p) = p - 1 for any prime p
• φ(p^k) = p^k - p^(k-1) for prime powers
• φ(mn) = φ(m) × φ(n) when gcd(m,n) = 1

Worked Examples

Example 1: φ(12)

Prime factorization: 12 = 2 × 2 × 3 = 2² × 3

Distinct primes: 2, 3

φ(12) = 12 × (1 - 1/2) × (1 - 1/3)

φ(12) = 12 × 1/2 × 2/3 = 4

Coprimes: 1, 5, 7, 11

Four numbers from 1 to 12 share no common factor with 12.

Example 2: φ(36)

Prime factorization: 36 = 2² × 3²

Distinct primes: 2, 3

φ(36) = 36 × (1 - 1/2) × (1 - 1/3)

φ(36) = 36 × 1/2 × 2/3 = 12

Coprimes: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35

Twelve numbers are coprime to 36. Notice the pattern – they avoid multiples of 2 and 3.

Example 3: φ(100)

Prime factorization: 100 = 2² × 5²

Distinct primes: 2, 5

φ(100) = 100 × (1 - 1/2) × (1 - 1/5)

φ(100) = 100 × 1/2 × 4/5 = 40

40% of numbers up to 100 are coprime to 100. These are numbers not divisible by 2 or 5.

Example 4: φ(17)

Prime factorization: 17 is prime

For any prime p: φ(p) = p - 1

φ(17) = 17 - 1 = 16

Coprimes: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Every number less than a prime is coprime to it. That's why φ(p) = p - 1.

Example 5: φ(60)

Prime factorization: 60 = 2² × 3 × 5

Distinct primes: 2, 3, 5

φ(60) = 60 × (1 - 1/2) × (1 - 1/3) × (1 - 1/5)

φ(60) = 60 × 1/2 × 2/3 × 4/5 = 16

Coprimes: 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59

Only 16 of 60 numbers are coprime to 60. Numbers must avoid factors 2, 3, and 5.

Example 6: φ(97)

Prime factorization: 97 is prime

φ(97) = 97 - 1 = 96

97 is prime, so all 96 numbers from 1 to 96 are coprime to it. Prime numbers maximize the totient ratio.

Example 7: φ(1000)

Prime factorization: 1000 = 2³ × 5³

Distinct primes: 2, 5

φ(1000) = 1000 × (1 - 1/2) × (1 - 1/5)

φ(1000) = 1000 × 1/2 × 4/5 = 400

400 numbers up to 1000 are coprime to 1000. These are numbers not divisible by 2 or 5.

Quick Fact

Euler's totient function is essential for RSA encryption. The security of RSA depends on the difficulty of computing φ(n) for large n without knowing its prime factors. Your online banking, secure messaging, and digital signatures all rely on this mathematical function discovered by Leonhard Euler in 1763.

Frequently Asked Questions

What does φ(n) tell us?

φ(n) counts how many numbers from 1 to n are coprime to n. It also equals the size of the multiplicative group of integers modulo n – important in abstract algebra and cryptography.

Why is φ(p) = p - 1 for primes?

A prime p has no factors other than 1 and itself. So every number from 1 to p-1 shares no common factor with p (except 1). All p-1 numbers are coprime to p.

What's the maximum value of φ(n)?

For any n, φ(n) ≤ n - 1, with equality only when n is prime. The ratio φ(n)/n is highest for primes (approaching 1) and lowest for products of many small primes.

Is φ(n) always even?

φ(n) is even for all n > 2. The only odd values are φ(1) = 1 and φ(2) = 1. This is because coprime numbers come in pairs: if k is coprime to n, so is n - k.

How is the totient function used in RSA?

RSA uses φ(n) where n = p × q (two large primes). The public and private keys are chosen using φ(n) = (p-1)(q-1). Factoring n to find φ(n) is computationally hard, which makes RSA secure.

What is Euler's theorem?

Euler's theorem states: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). This generalizes Fermat's little theorem and is fundamental to modular arithmetic and cryptography.

Other Free Tools

Search tools