Eulers Totient Function Calculator
Calculate eulers totient function instantly with our math tool. Shows detailed work, formulas used, and multiple solution methods.
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.
What is the relationship between the totient function and the Mobius function?
The totient function and the Mobius function mu(n) are connected through the fundamental identity phi(n) = sum of mu(d) * n/d for all divisors d of n. This is a Mobius inversion of the identity sum of phi(d) for d dividing n = n. The Mobius function is defined as mu(1) = 1, mu(n) = (-1)^k if n is a product of k distinct primes, and mu(n) = 0 if n has a squared prime factor. Using Dirichlet series, these relationships become elegant algebraic identities: the Dirichlet series for phi(n)/n^s equals zeta(s-1)/zeta(s), where zeta is the Riemann zeta function. The Mobius inversion formula is a powerful technique in number theory that converts summatory relations into explicit formulas. Many other multiplicative functions have similar connections: sigma_k(n) = sum of d^k for divisors d can be inverted to recover individual terms. These relationships form the foundation of multiplicative number theory and analytic number theory.
What is the Carmichael function and how does it relate to the totient?
The Carmichael function lambda(n), also called the reduced totient function, is the smallest positive integer m such that a^m is congruent to 1 modulo n for all integers a coprime to n. It always divides phi(n) and may be strictly smaller. For a prime p, lambda(p) = p-1 = phi(p). For an odd prime power p^k, lambda(p^k) = p^(k-1)*(p-1) = phi(p^k). For powers of 2, lambda(2) = 1, lambda(4) = 2, and lambda(2^k) = 2^(k-2) for k >= 3, which is half of phi(2^k). For composite n = p1^a1 * p2^a2 * ..., lambda(n) = lcm of lambda(pi^ai). The Carmichael function is useful in RSA implementations because using lambda(n) instead of phi(n) can yield a smaller private key d while maintaining correctness. The ratio phi(n)/lambda(n) measures how much the totient overestimates the minimum exponent needed. Understanding the Carmichael function is important for analyzing the multiplicative structure of integers modulo n.