Ayuda para utilizar el principio de inclusión-exclusión para demostrar $\sum_{n|d}\mu(d)\frac{n}{d}=\varphi(n)$

Question

$(1)$ Utilizando el teorema de convolución de Dirichlet, $$\sum_{n|d}\mu(d)\frac{n}{d}=\sum_{ab=n}\mu(a)b$$ Dejemos que $n=p_1\cdot p_2\cdots p_n\cdot k$ , donde $k$ contiene la factorización primaria de $p_k$ sólo si $ k\in\{1,2,...,n\}$ . Obsérvese que, para los casos de $\mu(a)$ , $k|b$ , si no $a$ no estaría libre de cuadratura. $(2)$ Por lo tanto, existe una biyección entre todos los $a$ tal que $k|b$ y todos los subconjuntos ( $S$ ) de $\{p_1,p_2,...,p_n\}$ . Si $|S|$ es impar, $\mu(a)=-1$ Si es que lo es, $\mu(a)=1$ . Por lo tanto, la suma original es igual a, $$\displaystyle (-1)^nk\left(1+\sum_{\begin{matrix} 1\le a,b \le n\\ a<b \end{matrix} }p_ap_b+\sum_{\begin{matrix} 1\le a,b,c,d \le n\\ a<b<c<d \end{matrix}}p_ap_bp_cp_d+\cdots\right)$$ $$\displaystyle (-1)^{n+1}k\left(\sum_{ 1\le a \le n}p_a+\sum_{\begin{matrix} 1\le a,b,c \le n\\ a<b<c \end{matrix} }p_ap_bp_c+\cdots\right)$$ $$=\displaystyle (-1)^nk\left(1-\sum_{ 1\le a \le n}p_a+\sum_{\begin{matrix} 1\le a,b \le n\\ a<b \end{matrix} }p_ap_b-\sum_{\begin{matrix} 1\le a,b,c \le n\\ a<b<c \end{matrix} }p_ap_bp_c+\sum_{\begin{matrix} 1\le a,b,c,d \le n\\ a<b<c<d \end{matrix}}p_ap_bp_cp_d-\cdots\right)$$

$$=\displaystyle (-1)^nn\left(\frac{1}{p_1\cdots p_n}-\sum_{ 1\le a \le n}\frac{p_a}{p_1\cdots p_n}+\sum_{\begin{matrix} 1\le a,b \le n\\ a<b \end{matrix} }\frac{p_ap_b}{p_1\cdots p_n}-\sum_{\begin{matrix} 1\le a,b,c \le n\\ a<b<c \end{matrix} }\frac{p_ap_bp_c}{p_1\cdots p_n}+\cdots\right)$$

Esto se parece bastante al principio de inclusión-exclusión podría funcionar bien aquí para demostrar que $\sum_{ab=n}\mu(a)b=\varphi(n)$ pero no estoy lo suficientemente versado en el principio para hacerlo. ¿Podría alguien utilizar el principio de aquí para demostrar el teorema? Algebraicamente, es posible demostrar el teorema inicial algebraicamente usando

$$\displaystyle(-1)^n\left(\frac{1}{p_1\cdots p_n}-\sum_{ 1\le a \le n}\frac{p_a}{p_1\cdots p_n}+\sum_{\begin{matrix} 1\le a,b \le n\\ a<b \end{matrix} }\frac{p_ap_b}{p_1\cdots p_n}-\sum_{\begin{matrix} 1\le a,b,c \le n\\ a<b<c \end{matrix} }\frac{p_ap_bp_c}{p_1\cdots p_n}+\cdots\right)=\prod_{k=1}^n\left(1-\frac{1}{p_k}\right), $$

pero sería bueno tener un argumento de inclusión-exclusión (creo que esto es combinatorio).

Answer 1

Déjalo, $n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ . Ahora, por definición, $$\varphi(n)=\#\{m:m\le n, (m,n)=1\}.$$ Ahora si, $m<n$ tal que $(m,n)=1$ entonces, $p_i\nmid m$ para cualquier $i\le k.$ Por lo tanto, el número de tales $m$ sería, por principio de inclusión-exclusión , $$n-\sum_iA_{p_i}+\sum_{i<j}A_{p_ip_j}-\sum_{i<j<k}A_{p_ip_jp_k}...$$ donde $A_d=\#\{m:m\le n,d|m\}=\frac nd$ así que.., $$\varphi(n)=n-\sum_i\frac n{p_i}+\sum_{i<j}\frac n{p_ip_j}...=\sum_{d|n}\mu(d)\frac n d.$$