Eulers Totient Function Calculator
Calculate eulers totient function instantly with our math tool. Shows detailed work, formulas used, and multiple solution methods.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Eulers Totient Function Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: phi(n) = n * Product of (1 - 1/p) for each prime factor p of n
Worked example — phi(36) = 12 | 12 integers from 1 to 36 are coprime to 36 | Totient ratio: 1/3
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 Step 2: Apply product formula: phi(36) = 36 * (1 - 1/2) * (1 - 1/3) phi(36) = 36 * 1/2 * 2/3 phi(36) = 36 * 1/3 = 12 Verification: The 12 numbers from 1 to 36 coprime to 36 are: 1, 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 phi(n) = (p-1)(q-1) = 10 * 12 = 120 Public key: (e, n) = (7, 143) Find d: e*d mod phi(n) = 1 7*d mod 120 = 1 Using Extended Euclidean: d = 103 Verify: 7 * 103 = 721 = 6*120 + 1 Encrypt m=9: c = 9^7 mod 143 = 48 Decrypt: 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.
What is the totient sum identity and what does it mean?
The totient sum identity states that the sum of phi(d) over all positive divisors d of n equals n itself: sum of phi(d) for d dividing n = n. This is one of the most beautiful and useful identities in number theory. The proof uses a counting argument: partition the integers from 1 to n based on their GCD with n. For each divisor d of n, there are exactly phi(n/d) integers k in {1,...,n} with gcd(k,n) = d. Since every integer from 1 to n has some GCD with n, the partitions are exhaustive, and their sizes sum to n. Alternatively, it can be proved using Mobius inversion: starting from the identity function f(n) = n, the Mobius inversion gives phi(n) = sum of mu(d)*n/d. The totient sum identity has applications in counting lattice points, analyzing the structure of cyclic groups (where phi(d) counts elements of order d), and proving other number-theoretic identities. It is also used in efficient algorithms for computing totient values over ranges of numbers.
How does the totient function behave for special classes of numbers?
Different classes of numbers have distinctive totient function behavior. For primes p: phi(p) = p-1, which is the maximum possible value relative to p. For prime powers p^k: phi(p^k) = p^(k-1)*(p-1), growing as a geometric sequence. For powers of 2: phi(2^k) = 2^(k-1), exactly half of the input. For products of the first k primes (primorials): phi(2*3*5*...*p_k) = product of (p_i - 1), which gives relatively small totient values. Highly totient numbers are those n where phi(n) = m has more solutions than phi(n) = m for any smaller m. The totient ratio phi(n)/n varies between 0 and 1 (exclusive): it equals (p-1)/p for primes, approaching 1 for large primes. The infimum of phi(n)/n over all n > 1 is 0, achieved by numbers with many small prime factors. Specifically, phi(n)/n can be made arbitrarily small by taking n as the product of the first k primes. For the Euler-Mascheroni constant gamma, the density of the totient values relates to e^(-gamma).
Can the totient function be used to solve congruence equations?
Yes, the totient function is essential for solving various types of congruence equations. To solve a^x mod n = 1 (finding the order of a modulo n), Eulers theorem guarantees that phi(n) is always a solution, though the minimal solution (the multiplicative order) divides phi(n). To solve a*x mod n = b when gcd(a,n) = 1, the solution is x = a^(phi(n)-1) * b mod n. For systems of congruences x mod n_i = a_i, the Chinese Remainder Theorem provides solutions modulo the product of n_i values, and the totient function determines how many units exist in each modular ring. In polynomial congruences like x^k mod p = a, the number of solutions relates to gcd(k, p-1) = gcd(k, phi(p)). The discrete logarithm problem (finding x given g^x mod p = h) involves the structure of the multiplicative group modulo p, which has phi(p) = p-1 elements. These applications make the totient function indispensable in computational number theory, cryptographic protocol design, and algebraic coding theory.
What are the computational methods for finding totient values over a range?
Computing phi(n) for all n from 1 to N can be done efficiently using a sieve method analogous to the Sieve of Eratosthenes. Initialize an array phi[1..N] with phi[i] = i. For each prime p (found by checking if phi[p] still equals p), multiply phi[kp] by (p-1)/p for all multiples kp of p up to N. This runs in O(N log log N) time, the same complexity as the prime sieve, and computes all totient values simultaneously. For a single large n, the bottleneck is factorization: once the prime factorization is known, phi(n) follows immediately from the product formula. Pollards rho algorithm and the quadratic sieve can factor numbers up to about 10^20 and 10^50 respectively. For computing phi(n) modulo some value m without full factorization, specialized algorithms exist but are generally hard. The totient summatory function (sum of phi(k) for k=1 to n) equals 3n^2/pi^2 + O(n log n), and can be computed in sub-linear time O(n^(2/3)) using techniques from analytic number theory involving the Stern-Brocot tree and hyperbola method.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Euler Totient Calculator
Calculate Euler totient function for any positive integer with prime factorization.
🧮Bessel Function Calculator
Calculate bessel function with inputs, formulas, and instant results.
🧮Composite Function Calculator
Calculate composite function with inputs, formulas, and instant results.
🧮Error Function Calculator
Calculate error function with inputs, formulas, and instant results.
🧮Function Domain Calculator
Calculate function domain with inputs, formulas, and instant results.
🧮Function Range Calculator
Calculate function range with inputs, formulas, and instant results.
🧮Gamma Function Calculator
Calculate gamma function with inputs, formulas, and instant results.
🧮Inverse Function Calculator
Calculate inverse function with inputs, formulas, and instant results.