φ(n)
Prime factors
Coprime share
Divisors

          Show

          More about Euler's totient function

          Euler's totient calculator

          Of the numbers from 1 to 12, only 1, 5, 7 and 11 have no common factor with 12, so φ(12) = 4. Euler's totient function counts these coprime numbers for any n. Enter a number up to 10^18 to get φ(n) with its prime factors and the product formula written out, see the numbers 1 to n with the coprime ones highlighted, check Euler's theorem, plot φ(k) for up to 100,000 numbers at once, or find every n with a given φ(n). Enter a whole number n up to 10^18, or choose a worked example. The tiles show φ(n), the prime factors of n, the share of the numbers 1 to n that are coprime to n and the number of divisors, and the steps write out the product formula with your numbers. Up to n = 500 the numbers 1 to n are drawn: the coprime ones are filled in, the others are coloured by the smallest prime they share with n. Point at a number to see its gcd with n, and click it to use it as a in Euler's theorem. Plot shows φ(k) for every k up to a limit; click a dot to open that number. Inverse lists every n with φ(n) = m; click one to open it.

          How it works

          1. Enter a whole number n up to 10^18, or pick a worked example such as φ(60), an RSA modulus or the Carmichael number 561.
          2. Read φ(n), the prime factors and the product formula with your numbers. Up to 500, point at the numbers 1 to n to see their gcd with n, and click one to check Euler's theorem with it.
          3. Switch to Plot to see φ(k) for every k up to 100,000, or to Inverse to list every n with φ(n) = m.

          How φ(n) is calculated

          Factor n into primes and multiply n by (1 − 1/p) for each prime p that divides it. For 60 = 2² × 3 × 5 that gives 60 × 1/2 × 2/3 × 4/5 = 16. Crossing out gives the same count: of the 60 numbers, 30 are even; of the 30 odd ones, 10 are multiples of 3; of the 20 left, 4 are multiples of 5, which leaves 16. Per prime power the formula is φ(p^k) = p^(k−1)(p − 1), and the values multiply: φ(60) = 2 × 2 × 4. The hard part is the factoring. The calculator uses trial division, a Miller–Rabin primality test and Pollard's rho method, so even an 18-digit product of two 9-digit primes takes a fraction of a second.

          Where the totient is used

          φ(n) counts the fractions k/n between 0 and 1 that are already in lowest terms, the step sizes that take a hand round an n-hour clock through every hour (1, 5, 7 and 11 on a 12-hour clock), and the numbers that have an inverse mod n. Euler proved that a^φ(n) ≡ 1 (mod n) for every a coprime to n, and RSA encryption relies on it: with n = 3233 = 61 × 53, φ(n) = 60 × 52 = 3,120, and the public exponent 17 has the private partner 2,753, because 17 × 2,753 = 15 × 3,120 + 1.

          Frequently asked questions

          What is Euler's totient function?

          φ(n) is the number of whole numbers from 1 to n that have no common factor with n other than 1. φ(9) = 6, because 1, 2, 4, 5, 7 and 8 are coprime to 9, while 3, 6 and 9 share the factor 3. By convention φ(1) = 1. Euler studied the function in the 1760s; Gauss gave it the symbol φ in 1801, and James Joseph Sylvester the name totient in 1879.

          What is φ of a prime number?

          p − 1, because every number from 1 to p − 1 is coprime to a prime p, so φ(97) = 96. For a power of a prime, φ(p^k) = p^k − p^(k−1), because only the multiples of p share a factor with it: φ(81) = 81 − 27 = 54.

          What does Euler's theorem say?

          If a and n are coprime, then a^φ(n) leaves the remainder 1 when divided by n. For n = 60 and a = 7: φ(60) = 16, and 7^16 ≡ 1 (mod 60). Fermat's little theorem is the case of a prime n. Often a smaller exponent already works: 7^4 = 2,401 = 40 × 60 + 1. The smallest exponent that works for every a coprime to n is Carmichael's function λ(n), which for 60 is 4.

          Can two numbers have the same totient?

          Yes, and usually several do: φ(n) = 24 for n = 35, 39, 45, 52, 56, 70, 72, 78, 84 and 90. Some even numbers are never a totient, 14 being the smallest, and no odd number above 1 is one, because φ(n) is even from n = 3 on. Robert Carmichael claimed in 1907 that no value is taken exactly once. That is still unproved, and Kevin Ford showed in 1998 that an exception would have to be larger than 10^(10^10).

          How large a number can I enter?

          Any whole number up to 10^18. The calculator factors it with exact whole-number arithmetic in your browser, so φ(10^18) = 4 × 10^17 and φ(999,999,866,000,004,473) = 999,999,864,000,004,608 come out to the last digit. The numbers 1 to n are drawn up to 500, the plot goes up to 100,000 and the inverse works for values up to 10^10.

          Ready to try it?

          Open PictorX in your browser — no install, no credit card required to start.

          Go to Editor