7
$\begingroup$

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?

  • 0
    Put it this way: can you prove it if $m$ is a prime or a prime power? Plus, where did you find it?2012-11-27

1 Answers 1

1

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.