Let $n=am+r$ with $m \ge a>5$ and $r \ge 0$. Prove that $\phi(n) \ge m$

65 Views Asked by At

I understand that for all $n>6$, we have $\phi(n) \ \ge \ \sqrt n $. This fact however is not getting me anywhere towards the proof of the claim in question. ($a, m, r$ are all integers)

1

There are 1 best solutions below

6
On BEST ANSWER

This is false (for $a>4$ as in the original post, but also for $a>5$ with a different example). Take for example $a=5$ and $m=6006$, $r=0$. Then $$ \phi(30030)=\phi(5\cdot 6006)=\phi(5)\cdot \phi(6006)=4\cdot 1440=5760, $$ which is not bigger or equal to $m=6006$. In fact, we have $$ \lim \inf \frac{\phi(n)}{n}=0. $$