Observations needed to justify an algebraic passage in proof of a property of $\varphi$ (Totient function)

Question

Let $\varphi$ be the Euler's totient function and let $n\in \mathbb{N}$ be factorized in primes as $n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_l^{\alpha_l}$.

I was looking for alternative methods to calculate the value of $\phi$ which didn't require the Chinese Remainder Theorem.

I found a very nice proof in "Ireland, Rosen - A Classical Introduction to Modern Number Theory" which use the Moebius function $\mu$ and the Moebius Inversion Formula

I've already proved that $$n= \sum_{d\mid n} \phi(d)$$

and this is the proof I'm speaking about.

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $

the "problem" is the equality $$ n-\sum_i \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_ip_j} \cdots = n(1-(1/p_1))\cdots(1-(1/p_l))$$

I can't handle it very well and so I can't provide a formal proof of its correctness. I tried to reverse the reasoning and to show that the right side is equal to the left side and then reverse again the reasoning, but I'm submersed with products…

PLEASE NOTE I need a proof / reasoning which doesn't use the right side of the equality, in other words I need something which start with something like this $$ n-\sum_i \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_ip_j} \cdots = \ ? $$ ("?" indicates that I don't know what could be the result) and shows how to manipulate the factors to obtain the right side

Answer 1

Hint: Think of Vieta formulas (sums), where $\frac{1}{p_i}$ are the "roots". Then set $X=1$.

Vieta: $$X^m - \left(\sum_{i=1}^mx_i\right)X^{m-1} + \left(\sum_{1\leq i<j\leq m}x_ix_j\right)X^{m-2}-\ldots = (X-x_1)(X-x_2)\ldots (X-x_m).$$

Answer 2

You can show it using a combinatorial argument: the nasty sums come from the inclusion-exclusion principle and the product comes from the multiplication principle.

Consider the set $S=\{1,2,\ldots, n\}$ and $n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$. Let $A_{r}\subset S$ be the set of numbers $\in S$ divisible by at least $r$ primes in the factorization of $n$. Note (show) that $$|A_{r}|=\sum_{i_1\lt i_2 \lt \ldots \lt i_r}\left\lfloor\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_r}}\right\rfloor=\sum_{i_1\lt i_2 \lt \ldots \lt i_r}\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_r}}.$$

How many numbers are coprime to $n$? We will find it using two ways. First, compute all numbers with some common factor to $n$. By the inclusion-exclusion principle, there are exactly

$$n-\varphi(n)=|A_{1}|-|A_{2}|\pm\cdots=\sum_i\frac{n}{p_i}-\sum_{i\lt j}\frac{n}{p_ip_j}\pm\cdots$$

On the other hand, we can compute it in other way. There are $n/p_1$ numbers divisible by $p_1$ and thus $n(1-p_1^{-1})$ numbers coprime to $p_1$. By a similar argument, there are $n(1-p_1^{-1})(1-p_2^{-1})$ numbers coprime to both $p_1$ and $p_2$. Repeating this yields $$\varphi(n)=n-\sum_i\frac{n}{p_i}+\sum_{i\lt j}\frac{n}{p_ip_j}\mp\cdots=n(1-p_1^{-1})(1-p_2^{-1})\cdots$$