Euler's Totient Function Calculator

Calculate Fast Fourier Transform (FFT) with window functions, complex number support, and advanced visualization options.

Euler's Totient Function: φ(n) = n × ∏(1 - 1/p) for all distinct prime factors p of n

Where: φ(n) counts the positive integers up to n that are relatively prime to n

n =
Enter any positive integer up to 1,000,000. For n = 1, φ(1) = 1 by definition.
12
30
100
210
1000
9973 (prime)
1
Calculating...

Understanding Euler's Totient Function

Euler's totient function φ(n) (also called Euler's phi function) counts the positive integers up to a given integer n that are relatively prime to n (i.e., numbers whose greatest common divisor with n is 1).

Euler's Totient Theorem

If n is a positive integer and a is an integer coprime to n (i.e., gcd(a, n) = 1), then:

aφ(n) ≡ 1 (mod n)

This theorem is a generalization of Fermat's Little Theorem and is fundamental in number theory and cryptography (particularly RSA encryption).

Properties of φ(n)

Property Formula Example
Prime p φ(p) = p - 1 φ(7) = 6
Prime power pk φ(pk) = pk - pk-1 φ(8) = φ(2³) = 8 - 4 = 4
Multiplicative (gcd(m,n)=1) φ(m·n) = φ(m)·φ(n) φ(6) = φ(2)·φ(3) = 1·2 = 2
General formula φ(n) = n·∏(1 - 1/p) φ(12) = 12·(1-1/2)·(1-1/3) = 4
Sum over divisors ∑ φ(d) = n for all d|n φ(1)+φ(2)+φ(3)+φ(6) = 1+1+2+2 = 6
Even for n > 2 φ(n) is even for n > 2 φ(15) = 8 (even)
Prime factorization If n = ∏ piai, then φ(n) = ∏ piai-1(pi - 1) φ(100) = φ(2²·5²) = 2·1·5·4 = 40

Calculation Methods

1

Prime Factorization Method: Factor n into prime powers: n = p₁a₁·p₂a₂·...·pₖaₖ. Then φ(n) = n·(1 - 1/p₁)·(1 - 1/p₂)·...·(1 - 1/pₖ).

2

Multiplicative Property: If n = ab where gcd(a,b) = 1, then φ(n) = φ(a)·φ(b). This allows breaking down the calculation for composite numbers.

3

Direct Enumeration: For small n, count the numbers from 1 to n that are coprime to n by checking gcd(k, n) = 1 for each k.

Applications of Euler's Totient Function

  • Cryptography: RSA encryption relies on φ(n) for key generation and security
  • Modular Arithmetic: Determining the order of elements modulo n
  • Group Theory: Counting generators of cyclic groups
  • Number Theory: Analyzing the distribution of prime numbers
  • Combinatorics: Counting reduced fractions with denominator n

Calculator Features:

  • Computes φ(n) using prime factorization method
  • Shows step-by-step calculation with formula application
  • Visualizes coprime numbers up to n with color coding
  • Provides number theory insights and properties
  • Handles numbers up to 1,000,000 efficiently

Frequently Asked Questions

Two integers a and b are coprime (or relatively prime) if their greatest common divisor (gcd) is 1. For example, 8 and 15 are coprime because gcd(8,15) = 1, even though neither is prime.

By definition, φ(1) counts the positive integers up to 1 that are coprime to 1. The only positive integer ≤ 1 is 1 itself, and gcd(1,1) = 1, so φ(1) = 1. This also makes the multiplicative property work correctly.

In RSA, two large primes p and q are chosen, and n = p·q is made public. The totient φ(n) = (p-1)(q-1) is kept secret. The encryption and decryption keys are chosen based on φ(n). The security of RSA relies on the difficulty of factoring n to find p and q, which would reveal φ(n).

For prime numbers, φ(p)/p = (p-1)/p which approaches 1 as p increases. The maximum occurs for n = 1 where φ(1)/1 = 1. For n > 1, the maximum is φ(2)/2 = 1/2, φ(6)/6 = 1/3, etc. The ratio decreases as n has more prime factors.

For small n, you can compute φ(n) by counting. For larger n, prime factorization is the most efficient method. There's also a recursive formula: φ(n) = n - Σ φ(d) for all proper divisors d of n, but this requires knowing φ(d) for all divisors.