Prove that $\varphi(n) = n \cdot \prod\limits_{i=1}^l \frac{p_i - 1}{p_i}$

Question

In a course on cryptography we should prove that if $n$ is of the form $p_1^{k_1} \cdot \ldots \cdot p_l^{k_l}$ and $p_1, \ldots, p_l$ are all distinct prime numbers then $$ \varphi \left(\prod\limits_{i=1}^{l} p_i^{k_i}\right) = \prod\limits_{i=1}^lp_i^{k_i-1} \cdot (p_i - 1) = n \cdot \prod\limits_{i=1}^l \frac{p_i - 1}{p_i}$$ holds.

We got the hint that if $n$ is a prime number, then $\varphi(n) = n - 1$, but still I'm stuck on this. First of all, I'm not even sure how to interpret $\prod\limits_{i=1}^lp_i^{k_i-1}$: As an example, take 330, which is composed of $\{2, 3, 5, 11\}$. Then $p_1 = 2, p_2 = 3, \ldots$, but what is $p_1^{k_1}$ and $p_1^{k_1-1}$ in this context?

Next, I'm not sure how to prove this. Can someone give me a push in the right direction?

Answer 1

It's straightforward to see that for a prime number $p$ and a natural number $n$, we have $\varphi(p^n)=p^n{p-1\over p}$. You said you already know the following property: if $\gcd(a,b)=1$, then $\varphi(ab)=\varphi(a)\varphi(b)$. It can be extended for any finite product of coprime natural numbers. So, suppose $n$ is a natural number. By the unique factorization theorem, there exist prime numbers $p_1,\dots,p_l$ and natural numbers $k_1,\dots,k_l$ such that $$n = p_1^{k_1}p_2^{k_2}\dots p_l^{k_l}.$$ The factors $p_1^{k_1},\dots,p_l^{k_l}$ are all relatively prime. So $$\varphi(n) = \varphi(p_1^{k_1}p_2^{k_2}\dots p_l^{k_l})= \varphi(p_1^{k_1})\varphi(p_2^{k_2})\dots\varphi(p_l^{k_l}) = p_1^{k_1}{p_1-1\over p_1}p_2^{k_2}{p_2 -1\over p_2}\dots p_l^{k_l}{p_l-1\over p_l}.$$

The last term is easily seen to be equal to $\displaystyle n \prod_{i=1}^l {p_i-1\over p_i}$, the result we were seeking.

Answer 2

Let $1<n = p_1^{k_1}p_2^{k_2}\dots p_l^{k_l}$ be the canonical decomposition of to prime numbers. We prove by induction on $l$, the distinct numbers of primes, that

$$(1) \ \ \ \ \ \phi(\prod\limits_{i=1}^{l} p_i^{k_i}) = n \cdot \prod\limits_{i=1}^l(p_i - 1) / p_i$$

For $l=1$: It is clear from the fact that $\phi$ multiplicative function if $\gcd(a,b)=1$, then $\phi(ab)=\phi(a)\phi(b)$.

Suppose that $(1)$ is true for $l=i$.

$$\gcd(p_1^{k_1},p_2^{k_2},\dots ,p_i^{k_i},p_{i+1}^{k_{i+1}})=1$$

Using again the fact that $\phi$ multiplicative function, we will have:

$$ (2) \ \ \ \ \ \phi((p_1^{k_1}p_2^{k_2}\dots p_i^{k_i})p_{i+1}^{k_{i+1}})=\phi(p_1^{k_1}p_2^{k_2}\dots p_i^{k_i})\phi(p_{i+1}^{k_{i+1}}) $$

But, we know that if $p$ is a prime number and $s>0$, then

$$\phi(p^s)=p^s-p^{s-1}$$

Therefore, $(2)$ becomes to be

$$(3) \ \ \ \ \ \phi(p_1^{k_1}p_2^{k_2}\dots p_i^{k_i})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1})$$

And now, by the induction hypothesis, we can substitute:

$$\phi(p_1^{k_1}p_2^{k_2}\dots p_i^{k_i})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})\cdots (p_i^{k_i}-p_i^{k_i-1})$$

into $(3)$, to get

$$ \phi(p_1^{k_1}p_2^{k_2}\dots p_i^{k_i}p_{i+1}^{k_{i+1}})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})\cdots (p_i^{k_i}-p_i^{k_i-1})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1}) $$

And we are done.

Notice that you can factor out $p_1^{k_1}p_2^{k_2}\dots p_{i+1}^{k_{i+1}}$.