0

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.

math seeker
  • 301
  • 1
    $\varphi (n)=n\prod_{p\mid n}\left(1-{\frac {1}{p}}\right)$ is well-known, do you are asking if $\prod_{p\mid n}\left(1-{\frac {1}{p}}\right) \ge \frac 14$. – Martin R Jan 15 '24 at 12:37
  • A quick way to generate a lot of counterexamples is to let $n=#[k]$, the $k^{th}$ primorial. That's usually the way to get unexpectedly small values for $\varphi(n)$. For example, with $k=50$, the ratio $\frac {\varphi(#[50])}{#[50]}$ is about $.1$, where you are guessing it should be over $.25$ – lulu Jan 15 '24 at 12:38

4 Answers4

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.

Afntu
  • 676
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.

Pielcq
  • 27
1

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

Praveen Kumaran P
  • 642
  • @Pielcq gave a counter example which is simpler than this... I don't had any idea about the question, and then I attempted and came up with a counter example.. I explained it because, the author of this question will get to know how I came up with this counter example... sorry if this example is annoying.. :) – Praveen Kumaran P Jan 15 '24 at 13:14
0

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.

Daigaku no Baku
  • 1,148
  • Ok. Thank you very much for the examples. I was thinking under what condition on $n$, it would be true . – math seeker Jan 15 '24 at 13:44
  • As mentioned by you that will be true for every primorial number greater than 210, can we think a bit about its proof. – math seeker Jan 15 '24 at 13:45
  • As I said, I am not sure this will be true for every primorial number greater than 210, that's just my hypothesis based on how this sum looks and the fact mentioned by the guy above, that all numbers he checked that fail to satisfy your conditions seem to be multipliers of 10. You may try to prove or disprove this hypothesis. I might think about it again when I have more time. – Daigaku no Baku Jan 15 '24 at 13:59
  • 1
    An easy induction shows what you want. If $\frac {\varphi(#n)}{#n}<.25$ then we note that $#(n+1)=#n\times p_{n+1}$ so $\frac {\varphi(#(n+1))}{#(n+1)}=\frac {\varphi(#n)}{#n}\times \frac {p_{n+1}-1}{p_{n+1}}$ so the ratio gets smaller with each new prime. – lulu Jan 15 '24 at 14:12
  • @lulu, have not you forgot an additional $\frac{n+1}{n}$ factor? – Daigaku no Baku Jan 15 '24 at 15:16
  • 1
    No....I don't think so. The ratio we want, for a given $k$, is $\frac {\varphi(k)}{k}$ The OP claims, incorrectly, that this is always $>.25$ I am looking at $k=#n$. the $n^{th}$ primorial. Of course $#(n+1)=#n\times p_{n+1}$ by definition. That gets my denominator, and I get the numerator from the arithmetic nature of the totient function. – lulu Jan 15 '24 at 15:29
  • I thought $\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)=n\prod_{p|n}\left( \frac{p-1}{p} \right)$? P.S. Oh, sorry, it cancels out with the denominator, got it. – Daigaku no Baku Jan 15 '24 at 15:33