Euler's Totient Calculator

Enter n to find how many numbers up to n are coprime to it.

A whole number from 1 to 10^15.

Try

Result

You enteredn=36n = 36

12\displaystyle 12

Prime factorisation

22×32\displaystyle 2^{2} \times 3^{2}

Numbers from 1 to n sharing a factor with n

24\displaystyle 24
Show the work
  1. Prime factorisation

    The totient depends only on the distinct primes that divide n=36n = 36, so factor it first.

    36=22×3236 = 2^{2} \times 3^{2}
  2. Euler's product formula

    Each prime pp dividing nn removes the fraction 1/p1/p of the numbers, those that are multiples of pp, and the primes act independently.

    Using φ(n)=n∏p∣n(1−1p)\varphi(n) = n \prod_{p \mid n} \left(1 - \dfrac{1}{p}\right)

    φ(36)=36(1−12)(1−13)=36×12×23=12\begin{aligned} \varphi(36) &= 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) \\ &= 36 \times \frac{1}{2} \times \frac{2}{3} \\ &= 12 \end{aligned}
  3. Result

    So φ(36)=12\varphi(36) = 12.

Worked examples