Euler's Totient Function

Finding large prime numbers is an essential part of the mechanisms involved in Internet security and privacy. And not just prime numbers, sometimes you need to perform various calculations on numbers that are specifically not prime. There are also uses of methods you have familiarized yourself with during your childhood, such as greatest common divisor (GCD) and least common multiple (LCM).

Based on these, in 1763 Carl Friedrich Gauss solved this interesting problem:

If you are given a number N, you have to determine how many integers between 1 and N have a GCD of 1 with N.

Later in this tutorial we will see that the solution of this problem can be written as $\phi(N)$ . Knowing how Sieve of Eratosthenes works and this tutorial we will solve this about 250 years old problem.

Co-prime Numbers

If you are given two numbers x and y, then their common divisor is a number z such that x and y are both divisible by z. And GCD is the largest number among all of the common divisors of x and y.

If you are given 8 and 12, the common divisors of these two numbers are 1, 2 and 4. Here, 4 is the largest and so 4 is the greatest common divisor of 8 and 12.

Now if the GCD of x and y is 1, then x and y are co-prime numbers. For example, 9 and 14, and 21 and 52 are some examples of co-prime numbers.

Then in Gauss' problem, if N is a prime number, how many of the numbers between 1 and N are co-prime? Suppose N is 7, which is a prime number; then if you think about it, all of the numbers between from 1 to 6 are co-prime with 7. This is true for all prime numbers.

Therefore, if N is a prime number, then:

$\phi(N) = N-1$

Prime Power

What about prime powers? Let's say N is 125 which is a prime power of 5 (53). Determining the number of co-primes for 125 is a bit tricky. But may be it would be easier to answer which numbers are not co-prime with 125.

A few of such numbers would be 5, 10, 15, 20, 25, etc. These numbers are not co-prime with 125 because the GCD of these numbers with 125 are greater than 1. And this can only happen when there exists common prime factors of both numbers. For example, here is the prime factorization of 125 and 50 (and they are co-prime with each other):

$125 = 5 \times 5 \times 5$

$50 = 2 \times 5 \times 5$

Here you can see both of these numbers have 5 as their prime factor. And so their GCD will be greater than 1. Any prime power, when factorized, will always yield one prime number as its prime factor.

Therefore, for any number to have GCD with 125 greater than 1 it must have 5 among its prime factors. In other words, if N = P^x and P is a prime number, then P must be a prime factor of all numbers for which the GCD with N is greater than 1.

Now to determine how many whole numbers from 1 to 125 are not co-prime with 125, we need to determine how many numbers in that range are divisible by 5. And, to do that, we need to divide 125 by 5. There are 25 numbers from 1 to 125 that are divisible by 5, and that means there are 25 numbers in that range that are not co-prime with 125.

Then how many numbers are co-prime with 125? Easy: 125 - 25 = 100.

Totient Function

Euler's Totient function (also known as Phi Function) gives us the number of co-primes of N that are smaller than N. Here are some examples:

$\phi(2) = 1$

$\phi(71) = 70$

$\phi(125) = 100$

Based on the discussion from the last section, we can say that for a number N such that N = P^x, the Totient function would be as follows:

$\phi(N) = P^x - \frac{P^x}{P}$

$= P^x - P^{x-1}$

$= P^x \times (1 - \frac{1}{P})$

$= P^x \times (\frac{P - 1}{P})$

Let's break this down.

There are P^x whole numbers between 1 and P^x. Of which, there $\frac{P^x}{P}$ numbers that have a GCD with N greater than 1. Therefore, we can just subtract this number from the total number of whole numbers in the range to find the value of $\phi$ .

But, not all numbers are prime powers. What can we do about those numbers? Let's take a number that is a product of two prime numbers. For example, 35 and 55.

$\phi(5 \times 7) = 24$

$\phi(5 \times 11) = 55$

How did we find the value of $\phi$ for these numbers?

Let's say that we have two prime numbers, p and q. And, we want to find the value of $\phi(p \times q)$ . Now, for any number x to have GCD with $p \times q$ greater than 1, there must be either p or q in the prime factorization of x.

Now, if x is smaller than $p \times q$ there x can never have both p and q in its prime factorization.

Therefore we can say the following things with certainty:

There are $ \frac{p \times q}{p} = q $numbers from 1 to `$ p \times q $` that are divisible by p.
There are $ \frac{p \times q}{q} = p $numbers from 1 to `$ p \times q $` that are divisible by q.
There is exactly 1 number from 1 to $p \times q$ that are divisible by both p and q.
There are a total of $p \times q$ numbers in this range.
There are $p + q - 1$ numbers in this range that are divisible by p or q. The minus 1 adjusts the double counting of $p \times q$ since this number is divisible by both p and q.

Therefore,

$\phi(p \times q) = (p \times q) - p - q + 1$

$= p(q-1)-1(q-1)$

$= (p-1)(q-1)$

Since we already know that,

$\phi(p) = p - 1$

$\phi(q) = q - 1$

Therefore,

$\phi(p \times q) = (p-1)(q-1) = \phi(p) \times \phi(q)$

Notice that if two numbers are prime, they will definitely be co-prime. But if one of them is not prime, then $\phi(p \times q) = \phi(p) \times \phi(q)$ . We will discuss why this is true in a later tutorial. Now we have what we need to find the $\phi$ of any number.

Final Step

Any whole number, except 1, can be written as a product of prime powers. This done through prime factorization of the number. For example, the prime factorization of 720 is:

$720 = 2^4 + 3^2 + 5^1$

Generally, prime factorization of a number has the following form:

$N = P_1^{x_1} \times P_2^{x_2} \times P_3^{x_3} \times ... \times P_n^{x_n}$

Here each P is a prime number, and each x is its power.

Suppose $S = P_1^{x_1}$ and $T = P_2^{x_2} \times P_3^{x_3} \times ... \times P_n^{x_n}$

Then, N can be written as $S \times T$ . Notice that there are no common prime numbers in S and T. Therefore, the GCD of S and T is 1 and they are co-prime. Which means:

$\phi(N) = \phi(S \times T)$

$= \phi(S) \times \phi(T)$

As S is a prime power of $P_1$ , we can write $Q(S) = P_1^{x_1} \times (1 - \frac{1}{P_1})$ .

Therefore,

$\phi(N) = P_1^{x_1} \times (1 - \frac{1}{P_1}) \times \phi(T)$

Similarly, we can break T into the form of $U \times V$ , where $U = P_2^{x_2}$ and $V = P_3^{x_3} \times ... \times P_n^{x_n}$

Here, U and V are co-prime and so,

$\phi(T) = \phi(U) \times \phi(V)$

$= P_2^{x_2} \times (1 - \frac{1}{P_2}) \times \phi(V)$

Which makes

$\phi(N) = P_1^{x_1} \times (1 - \frac{1}{P_1}) \times P_2^{x_2} \times (1 - \frac{1}{P_2}) \times \phi(V)$

We can now generalize $\phi(N)$ to:

$\phi(N) = P_1^{x_1} \times (1 - \frac{1}{P_1}) \times P_2^{x_2} \times (1 - \frac{1}{P_2}) \times P_3^{x_3} \times (1 - \frac{1}{P_3}) \times ... \times P_n^{x_n} \times (1 - \frac{1}{P_n})$

$= P_1^{x_1} \times P_2^{x_2} \times P_3^{x_3} \times ... \times P_n^{x_n} \times (1 - \frac{1}{P_1}) \times (1 - \frac{1}{P_2}) \times (1 - \frac{1}{P_3}) \times ... \times P_n^{x_n} \times (1 - \frac{1}{P_n})$

Since we know $N = P_1^{x_1} \times P_2^{x_2} \times P_3^{x_3} \times ... \times P_n^{x_n}$ , then:

$\phi(N) = N \times (1 - \frac{1}{P_1}) \times (1 - \frac{1}{P_2}) \times (1 - \frac{1}{P_3}) \times ... \times P_n^{x_n} \times (1 - \frac{1}{P_n})$

By figuring out the prime factorization of a number, we can follow this formula to easily determine the value of $\phi$ for that number.

If you know how to use Sieve of Eratosthenes to find prime numbers, then you can use a very similar method to determine the value of $\phi$ for all numbers between 1 and N.

Here is the pseudo code that calculates the value of $phi$ for all whole numbers between 1 and N:

function totient(n)
  let phi = array of length n
	for i = 0 to n
	  phi[i] = i
  for h = 2 to n
    if phi[h] == h
      for x = multiples of h up to n (i.e. 2*h, 3*h, 4*h, ....)
        phi[x] = (phi[x] / h) * (h - 1)

Euler's Totient Function

Co-prime Numbers

Prime Power

Totient Function

Final Step

Related Problems

Discussion

Related Tutorials

Sieve of Eratosthenes