Euler's Totient Function

A Swiss mathematician from 18th century, called Leonhard Euler formulated the following proposition:

If n is a positive integer, than totient function of n gives the amount of integers, that are less than n and relatively prime to n .

This post is dedicated to express the formula and elaborate the proof of it.

Totient function is also called as phi function \phi(n) . For example, for n=9, \phi(n) = 6, since we have 6 numbers - 1, 2, 4, 5, 7 and 8 - that are relatively prime to 9 and less than 9 .

Formula states that, if we factorize our number to it's prime divisors n = p_{1}^{n_1} ...p_{k}^{n_k} then we can calculate totient function of our number n as following:

\phi(n) = \prod\limits_{i} p_{i}^{n_i} (1 - \frac{1}{p_{i}}) = n \prod\limits_{i}(1 - \frac{1}{p_i})

Let's try this one, when n = 12. We can factorize 12 = 2^2 \times 3 and totient function:

\phi(12) = 12 . (1 - \frac{1}{3}) . (1 - \frac{1}{2}) = 12 . \frac{2}{3} . \frac{1}{2} = 4

Since we only have four numbers - 1, 5, 7, 11- that are relatively prime to 12 and less than 12; formula is valid so far.

In order to generalize it -after those example based explanations- let the proof begins...


Step 1:
We would prove that \phi(p) function is multiplicative where, if p = m \times n and if m and n are relatively prime to each other, \phi(p) = \phi(m) \times \phi(n)

Step 2:
We would make the conclusion, which surely takes less effort.

First, let's write all the numbers in between 1 and m \times n in a matrix, such as:

\begin{bmatrix} 1 & 2 & 3 & \cdots & r & \cdots & m \\ m + 1 & m + 2 & m + 3 & \cdots & m + r & \cdots & 2m \\ \vdots & \vdots & \vdots & \ddots & \cdots & \ddots & \vdots \\ (n - 1)m + 1 & (n - 1)m + 2 & (n - 1)m + 3 & \cdots & (n - 1)m + r & \cdots & mn \end{bmatrix}

An element in this matrix should be relatively prime to both m and n, in order to be relatively prime to p. In the first row, we have \phi(m) amount of elements, that are relatively prime to m. This hold for other rows as well, since gcd(r, m) = gcd(r + m, m)

Therefore, we can say that gcd(r,m) = 1 \rightarrow gcd(r+km, 1) = 1, if r is relatively prime with m all elements in the column of r is relatively prime with m as well.

Now, let's concentrate to find out elements, which are relatively prime to n. If we can find out them and if they are in the same column with elements, that are relatively prime to m, then we can be sure that this element is relatively prime to p as well.

This time, we would go into our matrix column by column. Vertically consecutive elements in each column has difference of m. Since m and n are relatively prime numbers, gcd(m,n) = 1 which is quite critical for explanations below.

From this point of view, we know that

\bmod (r, n) = \bmod(r + mn, n)

\rightarrow \bmod(r + 2mn, n)

\rightarrow \bmod(r + kmn, n)

Since the greatest common divisor of m and n is equal to 1, each element in a rows of column would have unique remainders for modulo n. In order to have same remainder of modulo n in different rows of particular column, we need to satisfy:

\bmod(r + km, n) = \bmod(r, n) \text{ where } 0 < k < n.

However, adding multiples of relatively prime number, like m, on top of any r, does not give the same remainder for modulo n. So modulo n of all elements in each column is equal to set of numbers from 0 to n-1. Consequently, in each column we have \phi(n) amount of numbers, that are relatively prime to n.

As a conclusion for this step, we have \phi(m) amount of numbers in each row, that are relatively prime to m and \phi(n) amount of numbers in each column, that are relatively prime to n and finally we can say that, this matrix has \phi(m) \times \phi(n) amount of elements, that are relatively prime to p.

You can check and visualize the proposition above with following matrix, where m = 9, n = 4.

\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 \\ 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 \end{bmatrix}

Now, we are quite close to complete the proof, before that we would have small theorem and proof.

Small Theorem: If p is a prime number, and k > 0, then

\phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p})

Small Proof: Since p is a prime number, the numbers that are not relatively prime with p^{k} has to be divisible with p and we have p^{k-1} amount of them. For example, let p = 7 and k = 2. We are seeking amount of numbers that are relatively prime with

p^{k} = 7^2 = 49

A number has to be divisible with 7 in order to not be relatively prime with ` 49 and we have \frac{p^k}{p^{k-1}} = \frac{7^2}{7^1} = 7 of them, which are 1, 7, 14, 21, 28, 35, 42.
By using multiplicative property of \phi function and this small theoem, here we accomplish the proof.

\phi(n) = \phi (p_1^{k_1}) \phi (p_2^{k_2}) \text{ . . . } \phi (p_n^{k_n})

\rightarrow p_1^{k_1}p_2^{k_2} \text{ . . . } p_n^{k_n} (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \text{ . . . } (1 - \frac{1}{p_n})

\rightarrow n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) \text{ . . . }(1 - \frac{1}{p_n})

References:

1. http://www.math.wisc.edu/~josizemore/Notes11(phi).pdf