Skip to content
Omnikalc

Euler's totient calculator: how many numbers are coprime to n?

Enter the prime factors of n and their exponents to get Euler's totient φ(n), the share of numbers coprime to n and the product formula.

Updated on
Your inputs

Value out of range

Value out of range

Value out of range

Value out of range

Value out of range

Value out of range

Results

Euler's totient φ(n)

96

The number n
360
Share of 1 to n that is coprime to n
26.67%
Numbers from 1 to n that share a factor with n
264
Product of (1 − 1/p) over the prime factors
0.2667

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.

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.

Frequently asked questions

What is Euler's totient function?

φ(n) counts the integers from 1 to n that are coprime to n, meaning they share no prime factor with it. For a prime p, every smaller number is coprime, so φ(p) = p − 1. For n = 12, the numbers 1, 5, 7 and 11 are coprime, so φ(12) = 4.

How do I compute it from the prime factors?

If n = p₁^a₁ × p₂^a₂ × …, then φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …, which is the same as the product of p^(a−1)(p−1) over the prime factors. You need the prime factorization of n first.

Why does it matter?

The totient is at the heart of RSA encryption, where the public and private keys are linked through φ(n) = (p − 1)(q − 1) for two primes, and of Euler's theorem, which says that a^φ(n) ≡ 1 (mod n) when a and n are coprime.

Does the calculator check that my factors are prime?

No. You enter the prime factors yourself, and the result is only valid if they really are prime and different. Factor the number first, by hand or with a factoring tool.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.