I have come across the statement that $$ \sum_{n\leq x}\sum_{d\mid(n,P_z)}\mu(d) = \sum_{d\mid P_z}\mu(d) \left[\frac{x}{d}\right], $$ where $P_z=\prod_{p\leq z}p$ where $p$ is prime, $\mu(d)$ is the Mobius function, and $[x]$ denotes the greatest integer less than or equal to $x$. I would appreicate some help in seeing the above. (Both of the above are equal to $\pi(x,z)$, the number of (positive) integers less than or equal to $x$ which are prime to all primes less than or equal to $z$.)

I am aware of the property that $\sum_{d\mid n}\mu(d)=0$ unless $n=1$ in which case, the sum is equal to $1$. I can see how for a given $d$, there are $[x/d]$ integers less than or equal to $x$ with this divisor.

Thank you!


For every $d$, count how often $\mu(d)$ occurs in the sum on the left.

If it occurs at all, there is an $n\leqslant x$ with $d\mid (n,P_z)$. Since $(n,P_z) \leqslant n \leqslant x$, it follows that $d\leqslant x$. Also, since $d$ divides $(n,P_z)$, it divides $P_z$.

Now, if $d \leqslant x$ and $d\mid P_z$, it occurs once in the inner sum for every $n \leqslant x$ such that $d \mid n$. There are exactly $\left[\frac{x}{d}\right]$ such $n$. For the divisors of $P_z$ that are greater than $x$, we have $\left[\frac{x}{d}\right] = 0$, and above we saw that $\mu(d)$ does not occur in the sum on the left for these $d$, so $\mu(d)$ occurs $\left[\frac{x}{d}\right]$ times in the sum on the left for all divisors of $P_z$, whether $\leqslant x$ or $> x$, i.e.

$$\sum_{n\leqslant x} \sum_{d\mid (n,P_z)} \mu(d) = \sum_{d\mid P_z} \mu(d)\left[\frac{x}{d}\right].$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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