Welcome to MathOverflow

Question

0

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?

flag	asked Feb 2 at 14:37 Kevin Smith 553●2●8

	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 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 at 10:13

quid · Accepted Answer · 2013-02-02 14:45:03Z UTC

2

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).$$

answered Feb 2 at 14:45

quid
13k●31●51

	Thanks Quid, I had hoped there was an easy way. – Kevin Smith Feb 2 at 14:52
	@Kevin Smith: you are welcome! – quid Feb 2 at 15:37

Is Euler’s totient sub-homogeneous of degree 1?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.