Eulers Totient Function Calculator
Calculate eulers totient function instantly with our math tool. Shows detailed work, formulas used, and multiple solution methods.
Calculator
Adjust values & calculateProduct Formula Breakdown
phi(36) = 36 * (1 - 1/2) * (1 - 1/3)
Integers Coprime to 36
Totient Sum Identity: Sum of phi(d) = 36
Totient Sequence
Formula
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.
Last reviewed: December 2025
Worked Examples
Example 1: Computing phi(36) Using the Product Formula
Example 2: RSA Key Generation Example
Background & Theory
The Eulers Totient Function Calculator applies the following established principles and formulas. Mathematics rests on a hierarchy of number systems, each extending the previous. The natural numbers (1, 2, 3, ...) support counting and ordering. The integers add negative values and zero, enabling subtraction without restriction. The rational numbers, expressible as p/q where p and q are integers and q is nonzero, close the system under division. The real numbers fill the gaps left by irrationals such as the square root of 2 or pi, forming a complete ordered field. The complex numbers, written as a + bi where i is the square root of negative one, complete the algebraic closure of the reals and allow every polynomial to have a root. Prime factorization states that every integer greater than one is uniquely expressible as a product of primes, a result known as the Fundamental Theorem of Arithmetic. Computing the greatest common divisor (GCD) of two integers relies most efficiently on the Euclidean algorithm: repeatedly replace the larger number with the remainder when it is divided by the smaller, until the remainder is zero. The last nonzero remainder is the GCD. The least common multiple (LCM) follows from the identity LCM(a, b) = |a * b| / GCD(a, b). Modular arithmetic defines equivalence classes of integers that share the same remainder under division by a modulus n. Fermat's Little Theorem and Euler's Theorem arise from this structure and underpin modern cryptography. Logarithms are the inverses of exponential functions. If b raised to the power x equals y, then the logarithm base b of y equals x. The natural logarithm uses base e, approximately 2.71828. Combinatorics counts arrangements and selections. The number of ordered arrangements (permutations) of r objects from n distinct objects is nPr = n! / (n - r)!. The number of unordered selections (combinations) is nCr = n! / (r! * (n - r)!). Pascal's triangle arranges these binomial coefficients so that each entry equals the sum of the two entries directly above it. The Fibonacci sequence, defined by F(1) = 1, F(2) = 1, and F(n) = F(n-1) + F(n-2), appears throughout nature and connects deeply to the golden ratio via Binet's formula.
History
The history behind the Eulers Totient Function Calculator traces back through the following developments. Mathematics as a systematic discipline traces to ancient Mesopotamia. Babylonian clay tablets dating to around 1800 BCE demonstrate knowledge of quadratic equations, Pythagorean triples, and base-60 arithmetic, suggesting a practical mathematical tradition far preceding Greek formalism. Euclid of Alexandria compiled the Elements around 300 BCE, establishing the axiomatic method that would define rigorous mathematics for over two thousand years. His work organized plane geometry, number theory, and proportion into logically chained propositions derived from a small set of postulates. The algorithm bearing his name for computing GCDs appears in Book VII and remains in use today. In the 9th century, the Persian scholar Muhammad ibn Musa Al-Khwarizmi wrote Al-Kitab al-mukhtasar fi hisab al-jabr wal-muqabala, the treatise whose title gave algebra its name. He systematized the solution of linear and quadratic equations and described procedures that operated on unknowns as objects, a conceptual leap away from purely numerical calculation. Rene Descartes introduced coordinate geometry in 1637 by uniting algebra and Euclidean geometry, allowing curves to be studied through equations. This synthesis set the stage for calculus. Isaac Newton and Gottfried Wilhelm Leibniz independently developed calculus during the 1660s and 1670s, triggering a priority dispute that lasted decades and divided British and Continental mathematicians. Carl Friedrich Gauss proved the Fundamental Theorem of Algebra in 1799, showing that every nonconstant polynomial has at least one complex root. His Disquisitiones Arithmeticae of 1801 established modern number theory. David Hilbert's formalist program at the turn of the 20th century sought to place all of mathematics on an explicit axiomatic foundation, a project that Kurt Godel's incompleteness theorems of 1931 showed to be fundamentally limited. Alan Turing's work in the 1930s on computability introduced the theoretical model of the stored-program computer and linked mathematical logic directly to the limits of algorithmic calculation. His proof that no algorithm can decide in general whether an arbitrary program will halt or run forever placed fundamental boundaries on what mathematics can mechanically determine, and it opened the discipline now known as theoretical computer science.
Frequently Asked Questions
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.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy