# Arithmetic function inequality

Fix integers $n$ and $k$. Why is $$\sum_{\substack{d < n\\(d, k) = 1}} \frac{\mu(d)^{2}}{\varphi(d)} \geq \sum_{\substack{d < n\\(d, k) = 1}}\frac{1}{d}?$$

-
Why do you think this is true? – Thomas Andrews Nov 26 '12 at 15:39

2nd try. I hope this works well.

Collect $d$'s that have prime divisors $\left\{p_1 , \cdots , p_k\right\}$.

Note that because $\mu$ is zero for non-square-free, the only surviving term on the LHS is $\frac{1}{\phi(p_1 \cdots p_k)}=\frac{1}{(p_1-1)\cdots (p_k-1)}$.

For RHS, the sum is less than $\frac{1}{p_1\cdots p_k}(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_k})$.

Because $\frac{p}{p-1}>1>1-\frac{1}{p}$, we know that $LHS > RHS$ for any collection of primes $\left\{p_1 , \cdots , p_k\right\}$.

Well, now sum over the collection $\left\{p_1 , \cdots , p_k\right\}$.

Then there are many repeated terms on the RHS when we sum over $\left\{p_1 , \cdots , p_k\right\}$, of course, but that's irrelevant because each terms are positive.

Hence LHS $\geq$ RHS and equality holds only when $d=1$(i.e, there is no prime that divide some d's).

-