An inequality on Euler totient function

Question

Let n be a natural number and $\phi$ be the Euler-totient function. Can we say that $4 \phi(n) \geq n?$

When $n$ is a prime, it is obviously true. I have checked for some composite numbers also and it is coming out to be true.

Any insight will be highly appreciated.

Answer 1

We can't say that, 210 is a counter example: 4 * ϕ(210) = 192 < 210. I have found plenty of other counter examples up to 10000.

Answer 2

$\textbf{No! it is not true ingeneral}$

If $n = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}} \cdots p_{r}^{\alpha_{r}}$ then $\phi(n) = n (1 - \frac{1}{p_{1}})(1 - \frac{1}{p_{2}}) \cdots (1 - \frac{1}{p_{r}})$. If $n$ is composite then $(1 - \frac{1}{p_{i}}) \geq \frac{1}{p_{i}} \implies \phi(n) \geq \frac{n}{p_{1}p_{2}\cdots p_{r}} \implies (p_{1}p_{2}\cdots p_{r})n \geq n$. But your hypothesis is not always true. It is true, for example if $r=2$ and $p_{1}=p_{2} = 2$. And $(p_{1}p_{2}\cdots p_{r}) \geq 4$ as for composite $n$, we have at least two $p_{i}$'s.

Answer 3

To show your observation is wrong in general, we need to show that $\exists n \in\mathbb{N,}$ such that $4<\frac{n}{\phi(n)}$, as per your observation, such a $n$ cannot be a prime,

So, n is a compostite number, therefore $n=p_1^{k_1}p_2^{k_2}...p_m^{k^m}$, where $p_i\neq p_j,$ for $i \neq j$

then $\phi(n)=(p_1-1)p_1^{k_1 -1}...(p_m-1)p_m^{k_m -1}$

therefore $\frac{n}{\phi(n)}=\frac{p_1p_2...p_m}{(p_1-1)...(p_m-1)}$

now take all the odd primes which are less than 100, product them and fix that as our n,

i.e fix $n=3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97$

then by the above expression

$\frac{n}{\phi(n)}=\frac{3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97}{2*4*6*10*12*16*18*22*28*30*36*40*42*46*52*58*60*66*70*72*78*82*88*96}$

Check this is in a calculator, the value is 4.15567 (approx.)

Therefore we found a $n$, such that $n/\phi(n)>4 \implies n>4 \phi(n)$ and hence your observation is wrong

Answer 4

Consider the expression of $\phi(n)=\sum_{d|n}\mu(d) \frac{n}{d}$ where $\mu(d)$ is the arithmetic Möbius function. Hence, $$\frac{\phi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}$$ $\mu(1)=1$, so $$\frac{\phi(n)}{n}=1+\sum_{d|n, d > 1} \frac{\mu(d)}{d}$$

We want the expression on the right to become less than 0.25. Consider a number that has first $m$ primes $p_{1}=2, ..., p_{m}$ as prime factors. The sum on the right is then $$1-\sum_{k=1}^{m} \frac{1}{p_k}+\sum_{k_{1}<k_{2}<m}\frac{1}{p_{k_{1}}p_{k_{2}}}-\sum_{k_{1}<k_{2}<k_{3}\le m}\frac{1}{p_{1}p_{2}p_{3}}+...+(-1)^{m}\frac{1}{p_{1}p_{2}\cdots p_{m}}$$

It is not hard to see that for $2\cdot 3 \cdot 5 \cdot 7=210$, this sum yields $8/35$, which is smaller than $1/4$. I think, this will be true for every primorial number greater than 210, but I don't know how to prove it at the moment.