# Proof: 624 BC

• Let $n$ be a natural number with the factorization $\prod_{k=1}^r p_k^{e^k}.$
• With the elementary symmetric functions, we have $$\begin{array}{rcll}\prod_{k=1}^r\left(1-\frac 1{p_k}\right)&=&1^r+(-1)^1\Sigma_11^{r-1}+(-1)^2\Sigma_21^{r-2}+\ldots+(-1)^{r-1}\Sigma_{r-1}1+(-1)^{r}\Sigma_r\\ &=&1-\Sigma_1+\Sigma_2-\ldots+(-1)^{r-1}\Sigma_{r-1}+(-1)^{r}\Sigma_r&( * ) \end{array}$$
• The coefficients $\Sigma_1,\ldots,\Sigma_r$ are given by the sums. $$\begin{array}{rcl} \Sigma_1(a_1,\ldots,a_r)&:=&\sum_{1\le k\le r}\frac {1}{p_k}\\\ \Sigma_2(a_1,\ldots,a_r)&:=&\sum_{1\le k < l\le r}\frac {1}{p_kp_l}\\ \Sigma_3(a_1,\ldots,a_r)&:=&\sum_{1\le k < l < m\le r}\frac {1}{p_kp_lp_m}\\ \vdots&&\\ \Sigma_r(a_1,\ldots,a_r)&:=&\frac {1}{p_1\cdots p_r}\\ \end{array}$$
• The number $1$ in the sum $( * )$ and the nominators of the summands $\Sigma_1,\ldots,\Sigma_r$ correspond exactly to the square-free divisors $d\mid p_1\cdots p_r$ with $d \ge 1,$ grouped by the increasing number $\rho$ of primes dividing $d$, i.e. $\rho=0,1,2,\ldots,r.$
• The signs of the summands in $( * )$ correspond exactly to the values of the Möbius function for these square-free divisors, which only depend on the number of distinct prime factors $\rho$ and equals $\mu(d)=(-1)^\rho.$
• Therefore, we have $$\prod_{k=1}^r\left(1-\frac 1{p_k}\right)=\sum_{d\mid p_1\cdots p_r}\frac{\mu(d)}{d}.$$
• Since, by definition, $\mu(d)=0$ for all non-square-free $d$, we can complement the sum by those divisors and get the required result $$\prod_{k=1}^r\left(1-\frac 1{p_k}\right)=\sum_{d\mid n}\frac{\mu(d)}{d}.$$

Thank you to the contributors under CC BY-SA 4.0!

Github: