# 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?

-
Why do you believe this is true? Where does it come from? –  David Speyer Nov 26 '12 at 20:31
Put it this way: can you prove it if $m$ is a prime or a prime power? Plus, where did you find it? –  Will Jagy Nov 27 '12 at 0:13

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.

-