Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
Why do you think this is true? –  Thomas Andrews Nov 26 '12 at 15:39
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.