Euler’s totient function φ(n) counts how many numbers from 1 to n are coprime with n, that is, have no prime factor in common with it. It is a basic tool in number theory and the engine of RSA encryption. Enter the prime factorization of n (up to three distinct primes with exponents) and the calculator returns φ(n), the share of coprime numbers and the product formula.
How the calculation works
For n = p₁^a₁ × p₂^a₂ × p₃^a₃, with distinct primes:
- φ(n) = Π p^(a−1) × (p − 1) over the prime factors
- Equivalently φ(n) = n × Π (1 − 1/p)
- Share coprime = φ(n) ÷ n
- Numbers with a common factor = n − φ(n)
A factor with exponent 0 is left out. The calculator does not test whether your factors are prime.
Example
Take n = 2³ × 3² × 5 = 360. The factors give (2² × 1) × (3 × 2) × (1 × 4) = 4 × 6 × 4 = 96. So φ(360) = 96: there are 96 numbers from 1 to 360 that are coprime to 360, which is 26.67 % of them, and 264 share a factor with it. The product (1 − ½)(1 − ⅓)(1 − ⅕) is 0.2667.
Why it matters
In RSA, a modulus n = p × q is the product of two large primes, and φ(n) = (p − 1)(q − 1) is needed to find the private key. Euler’s theorem uses φ(n) to compute powers modulo n, and the totient also tells you the number of generators of a cyclic group and the number of fractions in lowest terms with denominator n.
Good to know
φ(n) is always even for n greater than 2. For a power of a prime, φ(pᵃ) = pᵃ − pᵃ⁻¹. For two coprime numbers, φ(mn) = φ(m) × φ(n). The input factors need to be distinct primes: using a composite or repeating a prime gives a wrong result. This tool is for education.
Related tools
The GCD and LCM calculator relates two numbers, the quadratic equation calculator solves degree two, and the cubic equation calculator finds the roots of a degree-three polynomial.