Proof: 800 BC
(related to Proposition: Explicit Formula for the Euler Function)
- By sum of Euler function, we have $\sum_{d\mid n}\phi(d)=n.$
- By Möbius inversion, we have
$$\phi(n)=\sum_{d\mid n}\mu(d)\frac nd=n\sum_{d\mid n}\frac{\mu(d)}d.$$
- By sum of Möbius function over divisors with division,
$$\phi(n)=n\prod_{k=1}^r\left(1-\frac1{p_k}\right),$$
where $n=\prod_{k=1}^r p_k^{e_k}$ is the factorization of $n.$
- This is equivalent to
$$\begin{array}{rcl}\phi(n)&=&\prod_{k=1}^rp_k^{e_k}\left(1-\frac1{p_k}\right)\\
&=&\prod_{k=1}^r\left(p_k^{e_k}-p_k^{e_k-1}\right)\\
&=&\prod_{k=1}^r p_k^{e_k-1}(p_k-1),\end{array}$$ as required.
∎
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
