Let \(p\) be a prime and let \(a\) be some positive integer. According to this lemma, the formula for \(\phi(p^a)\) is \(p^a-p^{a-1}\). We can rewrite this as:
\[ \phi(p^a) = p^a \left( 1 - \frac{1}{p^a} \right) \]
Let \(n\) be some positive integer. We need to find \(\phi(n)\). According to the fundamental theorem of arithemtic:
\[\begin{gather} n = {p_1}^{b_1} \ {p_2}^{b_2} \ {p_3}^{b_3} \cdots {p_k}^{b_k} \\ b \in \mathbb{Z}^+, \ k \in \mathbb{Z}^+ \end{gather}\]
This means:
\[\phi(n) = \phi({p_1}^{b_1} \ {p_2}^{b_2} \ {p_3}^{b_3} \cdots {p_k}^{b_k})\]
Since \(\phi\) is multiplicative:
\[\begin{align} \phi(n) &= \phi({p_1}^{b_1}) \ \phi({p_2}^{b_2}) \ \phi({p_3}^{b_3}) \cdots \phi({p_k}^{b_k}) \\ &= {p_1}^{b_1} \left( 1 - \frac{1}{{p_1}^{b_1}} \right) \ {p_2}^{b_2} \left( 1 - \frac{1}{{p_2}^{b_2}} \right) \cdots {p_k}^{b_k} \left( 1 - \frac{1}{{p_k}^{b_k}} \right) \end{align}\]
We can group this another way:
\[\begin{align} \phi(n) &= {p_1}^{b_1}{p_2}^{b_2} \cdots {p_k}^{b_k} \ \left( 1 - \frac{1}{{p_1}^{b_1}} \right) \left( 1 - \frac{1}{{p_2}^{b_2}} \right) \cdots \left( 1 - \frac{1}{{p_k}^{b_k}} \right) \\ &= n \ \left( 1 - \frac{1}{{p_1}^{b_1}} \right) \left( 1 - \frac{1}{{p_2}^{b_2}} \right) \cdots \left( 1 - \frac{1}{{p_k}^{b_k}} \right) \end{align}\]
Another way of writing the above is:
\[ \phi(n) =n \prod_{p|n, \ p \text{ is prime}} \left( 1 - \frac{1}{p} \right) \]