1. ## Euler Totient

Prove that

$\frac{n}{\phi(n)}=\sum_{d|n}\frac{\mu^2(d)}{\phi(d )}$

2. Let $n=p_1^{\alpha_1}\hdots p_k^{\alpha_k}$

Then $\frac{n}{\phi(n)} = \left(\frac{p_1}{p_1-1}\right)\hdots \left(\frac{p_k}{p_k-1}\right) = \left(1+\frac{1}{p_1-1}\right)\hdots \left(1+\frac{1}{p_k-1}\right) = \sum_{d|n} \frac{\mu^2(d)}{\phi(d)}$

as you can see by expanding the product into a sum of $2^k$ terms.

3. i don't understand why $\left(1+\frac{1}{p_1-1}\right)\hdots \left(1+\frac{1}{p_k-1}\right) = \sum_{d|n} \frac{\mu^2(d)}{\phi(d)}$

4. For every subset $S$ of $\{p_1, \hdots, p_k\}$, the sum will contain a term of the form $\prod_{p \in S}\frac{1}{p-1} = \frac{1}{\phi\left(\prod_{p \in S}p\right)}$.

Moreover $\sum_{d | n}\frac{\mu(d)^2}{\phi(d)} = \sum_{q_1\hdots q_t | n}\frac{1}{\phi(q_1\hdots q_t)}$, where $q_1,\hdots, q_t$ are distinct primes. Another way of writing this is $\sum_{S \subset \{p_1,\hdots, p_k\}}\frac{1}{\phi\left(\prod_{p \in S}p\right)}$.