Mathematics · Number Theory
Euler's Totient Function Calculator
Computes Euler's totient function φ(n), the count of integers from 1 to n that are coprime to n.
Calculator
Formula
φ(n) is Euler's totient of n. The product runs over all distinct prime factors p of n. For each prime p dividing n, a factor of (1 − 1/p) is applied. The result equals the count of integers k with 1 ≤ k ≤ n such that gcd(k, n) = 1. For a prime p, φ(p) = p − 1. For a prime power p^k, φ(p^k) = p^(k−1)(p − 1). The function is multiplicative: if gcd(a, b) = 1, then φ(ab) = φ(a)φ(b).
Source: Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers, 6th ed., Oxford University Press (2008), Chapter 5.
How it works
The totient function φ(n) is defined for every positive integer n as the count of integers k in the range 1 ≤ k ≤ n satisfying gcd(k, n) = 1. For example, φ(1) = 1 by convention, since gcd(1, 1) = 1. For a prime number p, every integer from 1 to p − 1 is coprime to p, so φ(p) = p − 1. This makes the totient immediately useful for verifying primality and for working within prime moduli.
The general formula uses the prime factorization of n. If n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ, then φ(n) = n · ∏(1 − 1/pᵢ) over all distinct prime factors pᵢ. This is computed efficiently by iterating over trial divisors up to √n, dividing out each prime factor as it is found, and multiplying n by (1 − 1/p) for each. The function is multiplicative: when gcd(a, b) = 1, φ(ab) = φ(a)φ(b). This property allows fast computation via factorization. For prime powers, φ(p^k) = p^(k−1)(p − 1).
The most prominent application of φ(n) is in Euler's theorem: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). The RSA cryptosystem exploits this directly — the public and private keys are defined in terms of φ(pq) = (p−1)(q−1) for two large primes p and q. Beyond cryptography, the totient appears in the analysis of cyclic groups, primitive roots, Dirichlet series, the distribution of reduced residues, and the calculation of necklace combinatorics (Burnside's lemma).
Worked example
Let's compute φ(36) step by step.
Step 1 — Factorize n: 36 = 2² × 3². The distinct prime factors are 2 and 3.
Step 2 — Apply the formula: φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 36 × 1/3 = 12.
Step 3 — Verify directly: The integers from 1 to 36 that are coprime to 36 are those sharing no factor of 2 or 3. These are: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 — exactly 12 integers. ✓
Cryptographic example: In RSA, choose primes p = 61 and q = 53. Then n = pq = 3233 and φ(3233) = (61 − 1)(53 − 1) = 60 × 52 = 3120. The public exponent e must satisfy gcd(e, 3120) = 1; choosing e = 17 works. The private exponent d satisfies d × 17 ≡ 1 (mod 3120), giving d = 2753.
Limitations & notes
This calculator uses trial division up to √n for factorization, which is efficient for moderate values of n (up to roughly 10¹² in a reasonable time) but slows significantly for very large integers with no small prime factors. For cryptographic-scale numbers (hundreds of digits), specialized algorithms such as Pollard's rho, the elliptic curve method, or the general number field sieve are required. Additionally, n must be a positive integer — the standard totient is undefined for non-integers, zero, and negative numbers. Note that φ(n) = n − 1 if and only if n is prime, so this tool can serve as a primality check for small values, but dedicated primality tests (Miller–Rabin, AKS) are more appropriate for large inputs. Floating-point precision limits in JavaScript may cause incorrect results for integers beyond 2^53 − 1 (approximately 9 × 10¹⁵); use with caution for very large inputs.
Frequently asked questions
What does Euler's totient function φ(n) actually measure?
φ(n) counts the positive integers up to n that are coprime to n — meaning their greatest common divisor with n is exactly 1. For example, φ(10) = 4 because only 1, 3, 7, and 9 among {1, …, 10} share no common factor with 10. It is a measure of how many residues form a multiplicative group modulo n.
Why is φ(n) so important in RSA encryption?
RSA relies on Euler's theorem: a^φ(n) ≡ 1 (mod n) for gcd(a, n) = 1. When n = pq is a product of two large primes, φ(n) = (p−1)(q−1). The encryption and decryption exponents e and d are chosen so that ed ≡ 1 (mod φ(n)), making encryption reversible. The security comes from the fact that computing φ(n) without knowing p and q requires factoring n, which is computationally hard at large scales.
What is φ(n) for a prime number?
For any prime p, φ(p) = p − 1. This is because every integer from 1 to p − 1 has no common factor with p (since p has no divisors other than 1 and itself). Conversely, if φ(n) = n − 1, then n must be prime — this provides a simple primality test.
Is Euler's totient function multiplicative?
Yes. If gcd(a, b) = 1, then φ(ab) = φ(a) × φ(b). This multiplicativity is what allows the product formula over prime factors to work. However, it is not completely multiplicative — for example, φ(4) = 2 but φ(2) × φ(2) = 1 × 1 = 1 ≠ 2 because gcd(2, 2) ≠ 1.
What values of n give the smallest φ(n) relative to n?
Highly composite numbers (those with many small prime factors) give the smallest ratio φ(n)/n. Numbers of the form 2 × 3 × 5 × 7 × … (primorials) minimize φ(n)/n up to a given size. For instance, φ(30) = 8, so only 8/30 ≈ 26.7% of integers up to 30 are coprime to 30. Prime numbers, at the other extreme, have φ(p)/p = (p−1)/p → 1 as p → ∞.
Last updated: 2025-01-15 · Formula verified against primary sources.