Euler's Totient Function Calculator

Euler's Totient Function Calculator

Growing AI Skill PRO

Enter Calculation

Formula

φ(n)=n∏p|n(1−1p)\varphi\!\left(\text{n}\right) = \text{n} \prod_{p \mid \text{n}} \left(1 - \frac{1}{p}\right)
Usage stats

Advertisement

Results

Euler's Totient φ(15)
8
integers coprime to 15 in [1, n]
Input n 15
Distinct prime factors 3, 5

Report an error on this page

What is Euler's Totient Function?

Euler's totient function, written \(\varphi(n)\), counts how many positive integers from 1 up to n share no common factor with n other than 1 — that is, the integers that are coprime to n. For example, \(\varphi(9) = 6\) because 1, 2, 4, 5, 7 and 8 are all coprime to 9. The function is fundamental in number theory and appears throughout cryptography, most famously in the RSA algorithm where \(\varphi(n)\) determines the modular inverse used to generate keys.

Grid of integers 1 to 12 with those coprime to 12 highlighted
Euler's totient counts integers up to n that share no common factor with n.

How to use this calculator

Enter any positive integer n and press calculate. The tool factors n into its distinct prime divisors and applies the product formula to return \(\varphi(n)\) instantly, along with the list of distinct primes it found. It works for both small numbers and very large ones up to a billion.

The formula explained

The efficient way to compute the totient is the product formula:

$$\varphi(n) = n \cdot \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

taken over every distinct prime \(p\) that divides n.

You only need the distinct primes, not their multiplicities. Each factor \(\left(1 - \frac{1}{p}\right)\) trims away the fraction of numbers divisible by that prime.

Advertisement
Diagram showing n broken into prime factors then multiplied by (1 minus 1 over p) terms
The product formula multiplies n by a (1 - 1/p) factor for each distinct prime divisor p.

Worked example

Take \(n = 36\). Its prime factorization is \(2^2 \times 3^2\), so the distinct primes are 2 and 3. Then:

$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$

So exactly 12 integers between 1 and 36 are coprime to 36.

More Worked Examples

Example 1: a prime, φ(13)

13 is prime, so its only prime factor is 13 itself:

\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. This matches the prime shortcut \(\varphi(p) = p-1\).

Example 2: a prime power, φ(32)

Factor: \(32 = 2^5\). The only distinct prime is 2.

\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.

Equivalent prime-power form: \(\varphi(p^k) = p^k - p^{k-1}\), so \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). These are exactly the odd numbers from 1 to 31.

Example 3: three or more distinct primes, φ(210)

Factor: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).

  1. Start with \(210\).
  2. Multiply by \(1-\frac{1}{2} = \frac{1}{2}\): \(210 \cdot \frac{1}{2} = 105\).
  3. Multiply by \(1-\frac{1}{3} = \frac{2}{3}\): \(105 \cdot \frac{2}{3} = 70\).
  4. Multiply by \(1-\frac{1}{5} = \frac{4}{5}\): \(70 \cdot \frac{4}{5} = 56\).
  5. Multiply by \(1-\frac{1}{7} = \frac{6}{7}\): \(56 \cdot \frac{6}{7} = 48\).

So \(\varphi(210) = \)48. Note that the product rule only uses each distinct prime once. For example, \(60 = 2^2 \cdot 3 \cdot 5\) gives \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\).

Advertisement

Interpreting φ(n) and Its Uses

  • Primality link: for \(n \ge 2\), \(\varphi(n) = n-1\) if and only if \(n\) is prime. Every number below a prime is coprime to it. If \(n\) is composite, at least one number below it shares a factor, so \(\varphi(n) < n-1\).
  • Group of units: \(\varphi(n)\) is the number of elements in the group of units modulo \(n\), i.e. the residues that have a multiplicative inverse mod \(n\). For \(n = 15\) these are 1, 2, 4, 7, 8, 11, 13, 14, which gives 8 elements.
  • Euler's theorem: if \(\gcd(a, n) = 1\), then \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Example: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, and \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). Fermat's little theorem is the special case \(n = p\) prime.
  • RSA: when \(n = pq\) for distinct primes \(p\) and \(q\), \(\varphi(n) = (p-1)(q-1)\). With \(n = 15 = 3 \cdot 5\): \(\varphi(15) = 2 \cdot 4 = 8\). The public exponent \(e\) must be coprime to \(\varphi(n)\), and the private exponent \(d\) satisfies \(ed \equiv 1 \pmod{\varphi(n)}\). Real RSA uses primes hundreds of digits long. Anyone who can factor \(n\) can compute \(\varphi(n)\), which is why security rests on factoring being hard.
  • The ratio depends only on distinct primes: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). Exponents do not matter. For example, 6 and 12 both have prime set {2, 3}, so \(\varphi(6)/6 = 2/6 = 1/3\) and \(\varphi(12)/12 = 4/12 = 1/3\).

FAQ

What is \(\varphi(1)\)? By convention \(\varphi(1) = 1\), since 1 is coprime to itself.

What is \(\varphi\) of a prime p? For any prime p, \(\varphi(p) = p - 1\), because every integer from 1 to \(p-1\) is coprime to p.

Is \(\varphi\) multiplicative? Yes. If \(\gcd(a, b) = 1\) then \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\), which is exactly why the product over distinct primes works.

Last updated:

Most popular in Math and Statistics

View all Math and Statistics calculators