$\sum_{p\leq n}\sum_{q\leq N}\sum_{n\leq N;p|n,q|n}1=^? \sum_{pq \leq N}\big( \frac N{pq}+O(1)\big)+\sum_{p \leq N}\big( \frac N{p}-\frac N{p^2}\big)$

Question

I was studying Marius Overholt 'A course in Analytic Number Theory'. There in the section of "Normal order method". The proposition he is going to prove is

$Var[w]=O(loglog(N))$ where $w(n)$ is the no of prime divisors of $n$.

pf: We have $\sum_{n\leq N}w^2(n)=\sum_{n\leq N}\big(\sum_{p| n}1\big)\big(\sum_{q| n}1\big)=\color{red}{\sum_{p\leq N}\sum_{q\leq N}\sum_{n\leq N;p|n,q|n}1=^? \sum_{pq \leq N}\big( \frac N{pq}+O(1)\big)+\sum_{p \leq N}\big( \frac N{p}-\frac N{p^2}\big)}$

I am not getting how to get the red lined equality. Please help.

Answer 1

Split into two cases: $p \neq q$ and $p = q$.

If $p \neq q$, $p|N$, $q|N$ give you $\lfloor \frac N{pq}\rfloor = \frac N{pq} + O(1)$ numbers satisfying the condition $n \leq N$, $p | n$, $q | n$. As long as $pq \leq N$ you will get at least one number and thus should be included in your summand. Note that $pq$ and $qp$ will be counted twice if $p \neq q$.

If $p = q$ things are different. If $p \leq N$ you will have $\lfloor \frac N{p}\rfloor = \frac N{p} + O(1)$ numbers satisfying the condition $n \leq N$, $p | n$, $q | n$. But the first summand this is already counted as $\lfloor \frac N{p^2}\rfloor$ so you should compensate it with a $\frac Np - \frac N{p^2}$.