1. ## Euler Totient

Prove that

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

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

Then $\displaystyle \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 $\displaystyle 2^k$ terms.

3. i don't understand why $\displaystyle \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 $\displaystyle S$ of $\displaystyle \{p_1, \hdots, p_k\}$, the sum will contain a term of the form $\displaystyle \prod_{p \in S}\frac{1}{p-1} = \frac{1}{\phi\left(\prod_{p \in S}p\right)}$.

Moreover $\displaystyle \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 $\displaystyle q_1,\hdots, q_t$ are distinct primes. Another way of writing this is $\displaystyle \sum_{S \subset \{p_1,\hdots, p_k\}}\frac{1}{\phi\left(\prod_{p \in S}p\right)}$.