Euler's Totient Function Calculator
Calculate Euler's totient function phi(n) — the count of integers from 1 to n that are coprime to n.
Essential for RSA cryptography and number theory.
Euler’s Totient Function Written as phi(n) or phi(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. It was introduced by Leonhard Euler in 1763 in Switzerland.
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.