Euler's Totient Function Calculator

Euler’s Totient Function Written as φ(n), and sometimes as ϕ(n), Euler’s totient function counts how many integers from 1 to n are relatively prime (coprime) to n, meaning they share no common factors other than 1. The Swiss mathematician Leonhard Euler introduced it in 1763, in a paper written for the St Petersburg Academy while he was working in Berlin. The φ notation came later, from Gauss in 1801.

Examples phi(1) = 1 (just 1 itself). phi(6) = 2 (only 1 and 5 are coprime to 6). phi(7) = 6 (all of 1,2,3,4,5,6, because 7 is prime). phi(12) = 4 (only 1, 5, 7, 11 are coprime to 12).

Key Properties For any prime p: phi(p) = p - 1. For a prime power: phi(p^k) = p^k - p^(k-1) = p^(k-1)(p-1). For coprime m and n: phi(m*n) = phi(m) * phi(n) (multiplicative property). The general formula uses the prime factorization: phi(n) = n * product of (1 - 1/p) for each distinct prime factor p of n.

Connection to RSA Cryptography RSA encryption (invented in 1977 at MIT in the United States) relies directly on the totient function. The public key uses two large primes p and q, with n = p*q. The totient phi(n) = (p-1)(q-1) is used to compute the private key. The security of RSA depends on the difficulty of factoring n to find phi(n). Without knowing phi(n), computing the private key from the public key is computationally infeasible.

Euler’s Theorem If gcd(a, n) = 1, then a^phi(n) is congruent to 1 (mod n). This is a generalization of Fermat’s Little Theorem and is the mathematical foundation of RSA decryption.

A worked case: n = 60 Factor it as 2² × 3 × 5, then apply the product formula to the distinct primes only, ignoring the exponent on the 2. So φ(60) = 60 × (1 − 1/2) × (1 − 1/3) × (1 − 1/5) = 60 × ½ × ⅔ × ⅘ = 16. Those sixteen numbers are 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53 and 59. Notice 49 is in the list even though it is composite: coprimality is about shared factors with 60, not about being prime, and 49 = 7² shares nothing with 60.

Two edge cases worth knowing. φ(1) = 1, by the convention that the empty product is 1 and that 1 is coprime to itself. And φ(n) is even for every n above 2, which follows from the fact that coprime residues pair up as k and n − k. If a calculation ever hands you an odd totient for a large n, it is wrong.