Euler's Totient Function
Euler's totient function φ(n) counts how many integers from 1 to n are coprime to n. This function is central to understanding RSA encryption.
φ(n) = count of integers k where 1 ≤ k ≤ n and GCD(k, n) = 1
Visualize the Totient
See which numbers are coprime to n:
Click "Visualize" to see coprime numbers...
Computing φ(n)
There are formulas for computing the totient without checking every number:
For Primes
φ(p) = p - 1
All numbers less than a prime are coprime to it.
For Prime Powers
φ(p^k) = p^k - p^(k-1)
Only multiples of p share a factor with p^k.
For Products
φ(mn) = φ(m)φ(n)
When GCD(m,n) = 1, totient is multiplicative.
Totient Calculator
Enter a value to calculate its totient...
Euler's Theorem
Euler discovered a remarkable property: if GCD(a, n) = 1, then:
a^φ(n) ≡ 1 (mod n)
This is a generalization of Fermat's Little Theorem and is the foundation of RSA's correctness!
Verify Euler's Theorem
Enter values to verify Euler's theorem...
RSA Connection
In RSA: For n = pq (product of two primes), we have φ(n) = (p-1)(q-1). This value is used to find the decryption exponent d. Euler's theorem guarantees that decryption correctly recovers the original message!
Example: RSA with Small Primes
- p = 5, q = 7
- n = 5 × 7 = 35
- φ(n) = (5-1)(7-1) = 4 × 6 = 24
- Choose e = 5 (coprime to 24)
- Find d where 5d ≡ 1 (mod 24) → d = 5