Eulers Totient Function Calculator
Calculate eulers totient function instantly with our math tool. Shows detailed work, formulas used, and multiple solution methods.
Reviewed by Manoj Kumar, Mathematics Educator
Formula
phi(n) = n * Product of (1 - 1/p) for each prime factor p of n
Eulers totient function phi(n) counts integers from 1 to n that are coprime to n. The product formula multiplies n by (1 - 1/p) for each distinct prime factor p of n. For prime p, phi(p) = p-1. The function is multiplicative: phi(mn) = phi(m)*phi(n) when gcd(m,n) = 1.
Worked Examples
Example 1: Computing phi(36) Using the Product Formula
Problem:Calculate Eulers totient function phi(36).
Solution:Step 1: Factor 36 = 2^2 * 3^2\nStep 2: Apply product formula:\nphi(36) = 36 * (1 - 1/2) * (1 - 1/3)\nphi(36) = 36 * 1/2 * 2/3\nphi(36) = 36 * 1/3 = 12\n\nVerification: The 12 numbers from 1 to 36 coprime to 36 are:\n1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35
Result:phi(36) = 12 | 12 integers from 1 to 36 are coprime to 36 | Totient ratio: 1/3
Example 2: RSA Key Generation Example
Problem:Generate RSA keys with primes p=11, q=13, and public exponent e=7.
Solution:n = p * q = 11 * 13 = 143\nphi(n) = (p-1)(q-1) = 10 * 12 = 120\n\nPublic key: (e, n) = (7, 143)\nFind d: e*d mod phi(n) = 1\n7*d mod 120 = 1\nUsing Extended Euclidean: d = 103\nVerify: 7 * 103 = 721 = 6*120 + 1\n\nEncrypt m=9: c = 9^7 mod 143 = 48\nDecrypt: m = 48^103 mod 143 = 9
Result:phi(143) = 120 | Private key d = 103 | Encryption/decryption verified for message m = 9
Frequently Asked Questions
What is Eulers totient function and what does it compute?
Eulers totient function, denoted phi(n) or sometimes written as the Greek letter phi, counts the number of positive integers from 1 to n that are coprime to n (share no common factor greater than 1 with n). For example, phi(12) = 4 because exactly four numbers from 1 to 12 are coprime to 12: 1, 5, 7, and 11. The function was introduced by Leonhard Euler in 1763 and is one of the most important functions in number theory. For a prime p, phi(p) = p-1 since every number from 1 to p-1 is coprime to a prime. For a prime power p^k, phi(p^k) = p^(k-1)*(p-1). The totient function is multiplicative, meaning phi(mn) = phi(m)*phi(n) when gcd(m,n) = 1. This multiplicativity, combined with the prime power formula, allows efficient computation from the prime factorization of n.
How is Eulers totient function calculated using the product formula?
The product formula provides the most efficient way to compute phi(n): phi(n) = n * product of (1 - 1/p) for each distinct prime factor p of n. For example, 60 = 2^2 * 3 * 5, so phi(60) = 60 * (1-1/2) * (1-1/3) * (1-1/5) = 60 * 1/2 * 2/3 * 4/5 = 16. To avoid floating-point issues, compute integer-by-integer: start with phi = n, then for each prime factor p, update phi = phi/p * (p-1). This formula derives from the inclusion-exclusion principle applied to counting numbers not divisible by any prime factor of n. The beauty of this formula is that only the distinct prime factors matter, not their exponents. Computing phi(n) thus reduces to finding the prime factorization, which for typical numbers encountered in practice takes negligible time. For numbers up to 10^18, trial division up to the cube root combined with Pollards rho algorithm handles the factorization efficiently.
What is Eulers theorem and how does it use the totient function?
Eulers theorem states that for any integer a coprime to n, a^phi(n) is congruent to 1 modulo n. In other words, a^phi(n) mod n = 1 whenever gcd(a,n) = 1. This is a generalization of Fermats Little Theorem, which states a^(p-1) mod p = 1 for prime p (since phi(p) = p-1). Eulers theorem is fundamental in modular arithmetic and has numerous applications. In RSA cryptography, it ensures that the decryption operation correctly recovers the original message: m^(ed) mod n = m because ed = 1 mod phi(n). In computing modular powers efficiently, Eulers theorem allows reducing large exponents: a^k mod n = a^(k mod phi(n)) mod n. It also provides a method for computing modular inverses: a^(-1) mod n = a^(phi(n)-1) mod n. The theorem can be proved using group theory by considering the multiplicative group of integers modulo n, which has exactly phi(n) elements.
How is the totient function used in RSA encryption?
RSA encryption relies fundamentally on Eulers totient function. The key generation process works as follows: choose two large primes p and q, compute n = p*q, and calculate phi(n) = (p-1)*(q-1). Choose a public exponent e coprime to phi(n) (commonly e = 65537). The private key d is the modular inverse of e modulo phi(n), found using the Extended Euclidean Algorithm: e*d mod phi(n) = 1. Encryption computes c = m^e mod n, and decryption recovers m = c^d mod n. This works because c^d = m^(ed) = m^(1 + k*phi(n)) = m * (m^phi(n))^k = m * 1^k = m (mod n), by Eulers theorem. The security of RSA depends on the difficulty of computing phi(n) without knowing the factorization of n. In modern implementations, the Carmichael function lambda(n) = lcm(p-1, q-1) is often used instead of phi(n) for potentially smaller private keys, but the mathematical principle remains the same.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy