MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

That is, is it true that the bound $$\phi(mn)\leq m\phi(n)$$ holds for all pairs of natural numbers $m$ and $n$?

It is true on average, in the sense that $$\sum_{mn=k}m\phi(mn)\leq\sum_{mn=k}mn\phi(n),$$ and it holds for every pair I have computed. If it does not hold, what is the smallest counter example?

share|cite|improve this question
Another way of seeing this: $\phi(mn)$ is the number of integers in $[1,mn]$ coprime to $mn$, while $m\phi(n)$ is the number of integers in $[1,mn]$ coprime to $n$. – Anonymous Feb 5 '13 at 1:50
Thanks, Anonymous. You can also use Euler's product to get it directly, which provides the exact ratio. This I noticed following Quid's answer below. I'd like to point out that my interest was in the not-so-obvious corollary, that $$\sup_{d|n}\frac{d}{\phi(d)}=\frac{n}{\phi(n).$$ – Kevin Smith Feb 6 '13 at 10:13
up vote 2 down vote accepted

First note that, since $\phi$ is a multiplicative arithmetic function, i.e. $\phi(ab)=\phi(a)\phi(b)$ for coprime $a,b$, and since $\phi(a) \le a$ for every $a$, it suffices to consider the problem for prime powers.

And $$\phi(p^k p^t) = p^{k+t-1}(p-1) = p^k (p^{t-1}(p-1))= p^k\phi(p^t).$$

share|cite|improve this answer
Thanks Quid, I had hoped there was an easy way. – Kevin Smith Feb 2 '13 at 14:52
@Kevin Smith: you are welcome! – user9072 Feb 2 '13 at 15:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.