Is there a "nice" formula for $\sum_{d|n}\mu(d)\phi(d)$?

Solution 1:

Note that the terms $\mu(d) \phi(d)$, $\mu(d)^2 \phi(d)^2$, and $\mu(d)/ \phi(d)$ are all multiplicative. It therefore suffices to evaluate the sum for powers of a prime.

For example, for the first one,

$$ \sum_{d|p^\alpha} \mu(d) \phi(d) = \mu(1)\phi(1) + \mu(p) \phi(p) = 1-(p-1)=2-p. $$

Thus, writing $n = p_1^{\alpha_1} \dots p_k^{\alpha_k}$ gives

$$ \sum_{d|n} \mu(d) \phi(d) = \prod_{j=1}^k (2-p_j). $$

Solution 2:

A big hint for the first formula: keep in mind that $\phi(d)$ is multiplicative, so $\phi(p_1p_2)=\phi(p_1)\phi(p_2)$ for any two primes $p_1,p_2$; now consider the Inclusion-Exclusion theorem (or, equivalently, the expansion of the product $\Pi_i(1-x_i)$. A similar approach should work for the second formula, but you'll want to start with a different product since all the terms are positive...

Solution 3:

For the sake of having a complete answer:

For the second sum, $\displaystyle \sum_{d|p^\alpha}\mu(d)^2\phi(d)^2=1+(p-1)^2$ and so $$ \sum_{d|n}\mu(d)^2\phi(d)^2=\prod_{j=1}^k(1+(p_j-1)^2). $$ For the third, $\displaystyle \sum_{d|p^\alpha}\mu(d)/\phi(d)=1-\frac{1}{p-1}$, so $$ \sum_{d|n}\mu(d)/\phi(d)=\prod_{j=1}^k(1-1/(p_j-1)) $$ where the sums range over all primes in the factorization of $n$.