On page 40, exercise 44 of Introduction to Analytic and Probabilistic Number Theory by Tenenbaum:
- Show that any integer $n\ge1$ can be uniquely decomposed as $n = qm^2$ , where $q$ is squarefree. Denote by $Q(x)$ the number of squarefree integers $q$ not exceeding $x$. Establish the formula: $$ \lfloor x\rfloor=\sum_{m\leq\sqrt{x}}Q\left(\frac{x}{m^2}\right),\hspace{20pt} (1) $$ We know that $$ Q(x)=\sum_{q\leq x}|\mu(q)|,\hspace{20pt} (2) $$ How can we prove the above formula using
I found heuristically that $$ Q(x)=\sum_{d\leq\sqrt{x}}\mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor\hspace{20pt} (3) $$
My question is
- How can we prove (1), (3)?
- How can we prove (1) $\Leftrightarrow$ (3)?
For every $x$ let $S(x)$ be the set of positive square-free integers not exceding $x$. Every positive integer $n\leq x$ can be written uniquely as $m^2q$ where $m\leq\sqrt n\leq\sqrt x$ and $q$ is square-free and not exceding $x/m^2$, that's: $$\{n:1\leq n\leq x\}=\bigcup_{m\leq\sqrt x}\left\{m^2q:q\in S\left(\frac x{m^2}\right)\right\}$$ Consequently: \begin{align} \lfloor x\rfloor &=|\{n:1\leq n\leq x\}|\\ &=\left|\bigcup_{m\leq\sqrt x}\left\{m^2q:q\in S\left(\frac x{m^2}\right)\right\}\right|\\ &=\sum_{m\leq\sqrt x}\left|\left\{m^2q:q\in S\left(\frac x{m^2}\right)\right\}\right|\\ &=\sum_{m\leq\sqrt x}\left|S\left(\frac x{m^2}\right)\right|\\ &=\sum_{m\leq\sqrt x}Q\left(\frac x{m^2}\right)\\ \end{align} which proves $(1)$. To prove $(1\implies 3)$: \begin{align} \sum_{d\leq\sqrt n}\mu(d)\left\lfloor\frac x{d^2}\right\rfloor &=\sum_{d\leq\sqrt n}\mu(d)\sum_{m\leq\sqrt{x/d^2}}Q\left(\frac{x/d^2}{m^2}\right)\\ &=\sum_{d\leq\sqrt n}\sum_{md\leq\sqrt x}\mu(d)Q\left(\frac{x}{(md)^2}\right)\\ &=\sum_{n\leq\sqrt x}\sum_{d|n}\mu(d)Q\left(\frac{x}{n^2}\right)\\ &=\sum_{n\leq\sqrt x}Q\left(\frac{x}{n^2}\right)\sum_{d|n}\mu(d)\\ &=Q(x) \end{align}