Euler Totient Function- proof of $\phi(n) = n(1-1/p_1)(1-1/p_2)...(1-1/p_k)$

2.8k Views Asked by At

Now I have come across a proof of the function using the inclusion-exclusion principle however it isn't so clear how they easily have factorized in the end to get $m(1-\frac{1}{p_1})(1-\frac{1}{p_2})$... etc. where the input of the function is $m$. I have done this for actual numbers and can see how it all fits into place nicely but the factorization doesn't seem so obvious to me for a general number.

Sorry if I'm slightly vague.

1

There are 1 best solutions below

0
On

First If you want to talk about a particular proof I think that it'll be wiser to post a link here to the proof or at least try to copy it and then ask about the part that's unclear to you.

I don't know much about the inclusion-exclusion way to prove, but you can look at this proof.

First of all I want you to understand what's Euler Totient function is all about. Euler Totient function is an arithmetic function that will count the number of totatives of a given number $n$. To make it more clear, totatives of $n$ are numbers that are coprime to $n$ and are smaller than or equal to $n$

Before you can continue the proof you need to prove that $\phi(n)$ is a multiplicative function, i.e. if $gcd(a,b) = 1$, the $\phi(ab) = \phi(a) \cdot \phi(b)$. I'll leave this part to you

Now to make it clearer how it works let $p_k$ be a prime number of $n$, then there are $\frac {p_k}{p_k}$ numbers that have $p_k$ as a factor, so those number aren't coprime to $p_k$, so we need to subtract them.

We know that there are $p_k$ integers smaller that or equal to $p_k$, so we have:

$$p_k - \frac {p_k}{p_k} = p_k\left(1-\frac{1}{p_k}\right)$$

So after this move we excluded all numbers that have $p_k$ as as factor. Note that this works for every number, because this will lead that there are $p_k - 1$ totatives to $p_k$, which is obviously true.

If we have a prime power, then there are obviously $\frac{p_k^{a_k}}{p_k}$ integers that aren't comprime to $p_k$. So after subtracting we have:

$$p_k^{a_k} - \frac{p_k^{a_k}}{p_k} = p_k^{a_k}\left(1-\frac{1}{p_k}\right)$$

Now assuming that you proved that $\phi(n)$ is multiplicative we can make the final step:

Let $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, beacuse $\phi(n)$ is multiplicative we can rewrite it using this property, beacuse $p_1, p_2...p_k$ are all prime numbers, so it implies that they are compime:

$$\phi(n) = \phi(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = \phi(p_1^{a_1})\phi(p_2^{a_2})...\phi(p_k^{a_k})$$

Using the property for prime powers we proved before we have:

$$\phi(n) = p_1^{a_1}\left(1-\frac{1}{p_1}\right) p_2^{a_2}\left(1-\frac{1}{p_2}\right)...p_k^{a_k}\left(1-\frac{1}{p_k}\right)$$

$$\phi(n) = p_1^{a_1}p_2^{a_2}...p_k^{a_k}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_k}\right)$$

$$\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_k}\right)$$

And finally we reached the wanted form of the Euler Totient function.