Summation over relatively prime numbers Why is it true that
$$\frac{\varphi(m)}{m}\sum_{n \leq x}\frac{1}{n} \leq \sum_{n \leq x, (n, m) = 1}\frac{1}{n}?$$
Intuitively to see this, one can think of that from 1 up to $m$, there are $\varphi(m)$ integers which are relative prime to $m$, so one can expect this to be the proportion, but how does one show this explicitly?
 A: We proceed by induction on $k$, the number of distinct prime factors of $m$. 
When $k=0$, we have $m=1$, and $$\frac{\varphi(1)}{1}\sum_{n \leq x}\frac{1}{n}=\sum_{n \leq x}\frac{1}{n}=\sum_{n \leq x, (n, 1) = 1}\frac{1}{n}$$
Suppose that the statement holds for $k=i \geq 0$. Consider $m$ with $i+1$ distinct prime factors, and let $m=p^ab, a \geq 1$, where $b$ has $i$ distinct prime factors, and $p \nmid b$.
Then by the induction hypothesis, 
$$\frac{\varphi(p^ab)}{p^ab}\sum_{n \leq x}\frac{1}{n}=\frac{\varphi(p^a)}{p^a}\frac{\varphi(b)}{b}\sum_{n \leq x}\frac{1}{n} \leq \frac{p-1}{p}\sum_{n \leq x, (n, b) = 1}\frac{1}{n}$$
We have 
\begin{align}
\sum_{n \leq x, (n, p^ab) = 1}\frac{1}{n}=\sum_{n \leq x, (n, b) = 1}\frac{1}{n}-\sum_{n \leq x, (n, b) = 1, p \mid n}\frac{1}{n} &=\sum_{n \leq x, (n, b) = 1}\frac{1}{n}-\frac{1}{p}\sum_{n \leq \lfloor \frac{x}{p} \rfloor, (n, b) = 1}\frac{1}{n} \\
& \geq \sum_{n \leq x, (n, b) = 1}\frac{1}{n}-\frac{1}{p}\sum_{n \leq x, (n, b) = 1}\frac{1}{n} \\
& =\frac{p-1}{p}\sum_{n \leq x, (n, b) = 1}\frac{1}{n} \\
& \geq \frac{\varphi(p^ab)}{p^ab}\sum_{n \leq x}\frac{1}{n}
\end{align}
We are thus done by induction.
