Proof $\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$

Question

I try to show that Euler's totient function is a multiplicative function. $$\varphi(nm)=\varphi(n)*\varphi(m)$$ with gcd(m,n)=1,But I don't understand why this happens

$$n = \prod_{k=1}^{z}p_{k}^{e_{k}}$$ $$\iff \varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$

especially, why does this happen? $\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$

Answer 1

Hint: Start by thinking about $\varphi$ of a prime power. Can you show that $\varphi(p^e)=p^{e-1}(p-1)$ ?

Now use the fact that $\varphi$ is multiplicative.

Answer 2

That formula can be thought of using a divisibility argument. If n is a product of primes and powers of primes, a number will be relatively prime to n iff it is not a multiple of any prime. The number of numbers less than n which are not a multiple of a prime is 1-1/p. Do this for all divisor of n, multiply, and multiply by the total numbers in our range, n, to get the final formula.

Answer 3

If we put $N$ back in the product, we get: $$\prod _{p\mid N} (N-{N\over p})$$ but if $p$ divides $N$, for each term, this is the number of values less than $N$ that don't have a factor of all $p$ in them. We are simply weighting each value by the number of values that don't have a previous prime divisor of $N$ in them.

Answer 4

given a integer n, we know that n is a factor of primes such that $$n = p_{1}^{\alpha_{1}}...p_{z}^{\alpha_{z}} = \prod_{k=1}^{z}p_{k}^{\alpha_{k}}$$ then $$n \cdot m = p_{1}^{\alpha_{1}}...p_{z}^{\alpha_{z}} \cdot q_{1}^{\beta{1}}...q_{m}^{\beta{m}}$$ can be rearranged into a single prime factorization, because $n \cdot m \in \mathbb{Z} $

So i'll just call $n=nm = \prod_{k=1}^{z}p_{k}^{\alpha_{k}}$

We also know, that given any prime p, $$\varphi(p^{k}) = (p-1)p^{k-1}$$

Then, assuming $\varphi(n)$ is multiplicative, we get $$ \varphi(n) = \varphi(\prod_{k=1}^{z}p_{k}^{\alpha_{k}}) = \prod_{k=1}^{z}\varphi(p_{k}^{\alpha_{k}}) $$

Then, $$ \varphi(n \cdot m) = \varphi(\prod_{k=1}^{z}p_{k}^{\alpha_{k}}) \cdot \varphi(\prod_{k=1}^{m}q_{k}^{\beta{k}}) = \prod_{k=1}^{z}\varphi(p_{k}^{\alpha_{k}}) \cdot \prod_{k=1}^{m}\varphi(q_{k}^{\beta{k}}) $$

because $p_{k}$ is a prime for all k between 1 and z, $$ \prod_{k=1}^{z}\varphi(p_{k}^{\alpha_{k}}) = \prod_{k=1}^{z}(p_{k}-1)p_{k}^{\alpha_{k}-1} = \prod_{k=1}^{z}(1-\dfrac{1}{p_{k}})p_{k}^{\alpha_{k}}$$

$$\prod_{k=1}^{z}(1-\dfrac{1}{p_{k}})p_{k}^{\alpha_{k}} = \prod_{k=1}^{z}p_{k}^{\alpha_{k}} \prod_{k=1}^{z}(1-\dfrac{1}{p_{k}})$$

And recalling our definition of n = $\prod_{k=1}^{z}p_{k}^{\alpha_{k}}$, $$\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}}) $$

Thus $\varphi(n*m) = \varphi(n) * \varphi(m) \implies \varphi(n) = n\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$

If you assume the fact that $\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$ is true, you can do the opposite procedure and arrive in the conclussion that $\varphi(n)$ is multiplicative

Thus, $$\varphi(n \cdot m) = \varphi(n) \cdot \varphi(m) \iff \varphi(n) = n\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$