Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}?$$

share|cite|improve this question
Why do you think this is true? – Thomas Andrews Nov 26 '12 at 15:39
up vote 0 down vote accepted

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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.