Introduction
Euler's totient function phi(n) counts how many integers from 1 to n are coprime to n. It shows up in RSA key generation, primitive root calculations, and Euler's theorem. This calculator computes phi(n) for any positive integer using the multiplicative formula: factor n into primes, then apply phi(n) = n * product(1 - 1/p) over the distinct prime factors. It shows the factorization and the step-by-step computation so you can see exactly where the number comes from. Paste an integer and the result appears instantly, all in your browser.
What this tool does
- Compute Euler's totient phi(n) for any positive integer n using BigInt arithmetic, with no practical upper bound on input size
- Factor n into its prime components using trial division with a Miller-Rabin bail-out, so semiprimes with one large prime factor are handled efficiently
- Display the full prime factorization of n, showing each prime and its exponent
- Show the multiplicative formula applied step by step: phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... with the final numeric result
- Detect when n is prime and report phi(n) = n - 1 immediately, since every smaller positive integer is coprime to a prime
- Run entirely client-side with no server communication, so your inputs never leave the browser
How this tool works
The tool takes a single input: a positive integer n. It factors n by trial division, testing divisors up to sqrt(n). For each prime factor p found, it records p and its exponent (how many times p divides n). If the remaining cofactor after trial division is large, the tool applies the Miller-Rabin primality test to check whether the cofactor is itself prime; if it is, the factorization is complete without needing to continue trial division. This makes the tool practical for semiprimes like n = p * q where one factor is small and the other is large.
Once the factorization n = p1^a1 * p2^a2 * ... * pk^ak is known, the tool applies the multiplicative formula. Euler's totient is multiplicative: if gcd(m, n) = 1, then phi(mn) = phi(m) * phi(n). For a prime power p^a, phi(p^a) = p^a - p^(a-1) = p^(a-1) * (p - 1). Combining these, phi(n) = n * product over distinct primes p dividing n of (1 - 1/p).
The tool displays the factorization as a product of prime powers, then shows the formula with the actual numbers substituted in. For example, with n = 360: the factorization is 2^3 * 3^2 * 5. The formula becomes phi(360) = 360 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) = 360 * 1/2 * 2/3 * 4/5 = 96. The tool shows this computation so you can verify each step.
If n is prime, the tool skips factorization and reports phi(n) = n - 1 directly, since every integer from 1 to n-1 is coprime to n.
How Euler's totient function works
Euler's totient function, also called the phi function, was introduced by Leonhard Euler in 1763. It counts the integers k in [1, n] such that gcd(k, n) = 1. For a prime p, every integer from 1 to p-1 is coprime to p, so phi(p) = p - 1. For a prime power p^a, the only integers not coprime to p^a are the multiples of p, of which there are p^(a-1) in [1, p^a], so phi(p^a) = p^a - p^(a-1).
The function is multiplicative: if gcd(m, n) = 1, then phi(mn) = phi(m) * phi(n). This follows from the Chinese Remainder Theorem, which establishes a bijection between residues coprime to mn and pairs of residues coprime to m and n respectively. Combining multiplicativity with the prime power formula gives the general formula: if n = p1^a1 * p2^a2 * ... * pk^ak, then phi(n) = n * product(1 - 1/pi) over the distinct primes pi dividing n.
Euler's theorem states that for any integer a coprime to n, a^phi(n) = 1 (mod n). This generalizes Fermat's little theorem (where phi(p) = p - 1 gives a^(p-1) = 1 mod p). Euler's theorem is the mathematical foundation of RSA: if n = pq and ed = 1 mod phi(n), then m^(ed) = m mod n for any message m coprime to n. The private exponent d is computed as the modular inverse of e modulo phi(n), so computing phi(n) is equivalent to breaking RSA.
This equivalence is why RSA security depends on the hardness of factoring. If you can factor n = pq, you can compute phi(n) = (p-1)(q-1) and derive d from e. Conversely, if you can compute phi(n) without factoring, you can factor n by solving the system phi(n) = (p-1)(q-1) and n = pq. The two problems are polynomially equivalent. For a thorough treatment, see Hardy and Wright's *An Introduction to the Theory of Numbers* (Chapter V, Theorem 58 and following) or Gauss's *Disquisitiones Arithmeticae* (articles 38-39).
How to use this tool
- Enter a positive integer n in the input field. The tool accepts decimal digits only
- The tool factors n into primes using trial division, with a Miller-Rabin check on any large remaining cofactor
- Read the result badge: phi(n) = [value]. If n is prime, the tool notes that phi(n) = n - 1
- Check the prime factorization panel to see n written as a product of prime powers
- Check the multiplicative formula panel to see phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... = [result], with the actual numbers substituted in
- Try entering a prime to see the shortcut phi(p) = p - 1, or a composite like 360 to see the full factorization and formula
Real-world examples
Computing phi(360)
Input: n = 360. Factorization: 360 = 2^3 * 3^2 * 5. The tool applies the formula: phi(360) = 360 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) = 360 * 1/2 * 2/3 * 4/5 = 96. So there are 96 integers between 1 and 360 that are coprime to 360. This is the kind of computation needed when working with primitive roots or RSA with a composite modulus.
A prime number: phi(97)
Input: n = 97. Since 97 is prime, the tool detects this via Miller-Rabin and reports phi(97) = 96 immediately, without needing to factor. Every integer from 1 to 96 is coprime to 97. This is why phi(p) = p - 1 for any prime p, and it is the basis of Fermat's little theorem: a^(p-1) = 1 mod p.
An RSA modulus: phi(3233)
Input: n = 3233. Factorization: 3233 = 61 * 53. The tool computes phi(3233) = 3233 * (1 - 1/61) * (1 - 1/53) = 3233 * 60/61 * 52/53 = 60 * 52 = 3120. In RSA, if the public exponent is e = 17, the private exponent is d = 17^(-1) mod 3120 = 2753. This is exactly how RSA key generation works: factor n, compute phi(n), then invert e modulo phi(n).
A prime power: phi(49)
Input: n = 49 = 7^2. The tool computes phi(49) = 49 * (1 - 1/7) = 49 * 6/7 = 42. Equivalently, phi(7^2) = 7^2 - 7^1 = 49 - 7 = 42. The 7 integers in [1, 49] that are not coprime to 49 are the multiples of 7: 7, 14, 21, 28, 35, 42, 49. So 49 - 7 = 42 integers are coprime to 49.
A semiprime with a large factor
Input: n = 2 * 1000000007 (where 1000000007 is prime). Trial division finds the factor 2 quickly, then the Miller-Rabin test confirms the cofactor 1000000007 is prime. The tool computes phi(n) = n * (1 - 1/2) * (1 - 1/1000000007) = 1000000006. Without the Miller-Rabin bail-out, trial division would need to test divisors up to sqrt(1000000007) ~ 31623 to confirm the cofactor is prime.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Trial division + multiplicative formula | O(sqrt(n)) for factoring | This tool, general-purpose for moderate n |
| Trial division + Miller-Rabin bail-out | O(sqrt(p_min)) for semiprimes | This tool, fast when smallest factor is small |
| Pollard's rho factorization | O(p_min^(1/2)) expected | Large semiprimes where smallest factor is moderate |
| Quadratic sieve | Sub-exponential, L_n[1/2, c] | Factoring integers up to ~100 digits |
| General number field sieve | Sub-exponential, L_n[1/3, c] | Factoring RSA-size integers (200+ digits) |
Limitations or considerations
The tool factors n by trial division, which runs in O(sqrt(n)) time. For n with 18 to 20 digits, this takes a few seconds. For n with 30+ digits where both factors are large, trial division will not finish in any reasonable time. The Miller-Rabin bail-out helps when n has one small factor and one large prime factor, but it does not help when n is a product of two large primes (as in real RSA keys).
Computing phi(n) for an RSA modulus n = pq without knowing p and q is equivalent to factoring n, which is the hard problem that RSA security relies on. No known polynomial-time algorithm exists for factoring large integers on classical computers. If this tool could compute phi(n) for a 2048-bit RSA modulus quickly, RSA would be broken.
The tool uses BigInt arithmetic, which is slower than native big-integer libraries. For numbers with hundreds of digits, expect long run times. For production RSA key generation, use a library like OpenSSL that implements the general number field sieve for factoring (though even GNFS is infeasible for well-chosen 2048-bit moduli).
For computing gcd (which is related to coprimality and the totient), use the GCD / LCM Calculator. For factoring numbers as a standalone operation, see the Prime Factorization tool.
Frequently asked questions
What is Euler's totient function?
phi(n) is the count of integers k in [1, n] such that gcd(k, n) = 1. For a prime p, phi(p) = p - 1. For a prime power p^a, phi(p^a) = p^a - p^(a-1). For a general n = p1^a1 * ... * pk^ak, phi(n) = n * product(1 - 1/pi). The function is multiplicative: if gcd(m, n) = 1, then phi(mn) = phi(m) * phi(n).
How is Euler's totient related to RSA?
In RSA, the modulus is n = pq for two large primes. The private exponent d is computed as d = e^(-1) mod phi(n), where phi(n) = (p-1)(q-1). If an attacker can compute phi(n), they can derive d and decrypt messages. Computing phi(n) without knowing p and q requires factoring n, which is believed to be hard. This equivalence is why RSA security reduces to the factoring problem.
What is Euler's theorem?
Euler's theorem states that for any integer a coprime to n, a^phi(n) = 1 (mod n). It generalizes Fermat's little theorem, which is the special case where n is prime (phi(p) = p - 1, giving a^(p-1) = 1 mod p). Euler's theorem is the basis of RSA decryption: since ed = 1 mod phi(n), we have m^(ed) = m * (m^phi(n))^k = m * 1^k = m mod n.
Why does the tool use trial division instead of a faster factoring algorithm?
Trial division is simple and works well for numbers up to about 10^18, which covers most educational use cases. For larger numbers, algorithms like Pollard's rho, the quadratic sieve, or the general number field sieve are faster, but they are also more complex to implement in TypeScript and run in a browser. The Miller-Rabin bail-out handles the common case of semiprimes with one small factor efficiently.
Can this tool break RSA?
No. Real RSA uses 2048-bit or larger moduli, which are products of two 1024-bit primes. Trial division cannot factor such numbers in any reasonable time. The best known algorithm (the general number field sieve) is also infeasible for well-chosen 2048-bit moduli. This tool is for understanding the mathematics of phi(n), not for attacking real cryptosystems. See the RSA Encrypt / Decrypt tool for how RSA works in practice.
What is the difference between phi(n) and the Carmichael function lambda(n)?
phi(n) counts the numbers coprime to n. The Carmichael function lambda(n) is the exponent of the multiplicative group modulo n: the smallest positive m such that a^m = 1 mod n for all a coprime to n. lambda(n) always divides phi(n). For n = pq (RSA), lambda(n) = lcm(p-1, q-1), while phi(n) = (p-1)(q-1). Some RSA implementations use lambda(n) instead of phi(n) when computing d, which produces a slightly smaller (but equivalent) private exponent.
Conclusion
Euler's totient function is a bridge between number theory and cryptography. It counts the units modulo n, it underlies Euler's theorem, and it is the quantity you must compute to derive an RSA private key from a public one. This calculator shows the factorization and the multiplicative formula step by step, making the computation transparent. To factor numbers as a standalone operation, use the Prime Factorization tool. To see where phi(n) matters in practice, try the RSA Encrypt / Decrypt tool. To test whether a factor is prime, use the Miller-Rabin Primality Test. For computing gcd and lcm (which appear in the Carmichael function), see the GCD / LCM Calculator.