Is it true that :

$\frac {n}{5} < \phi (n) < n$ for all $n > 1$

where $\phi (n)$ is Euler's totient function .

Since $\phi(n)$ has maximum value when $n$ is a prime it follows that maximum value of $\phi(n)$ in term of $n$ is $n-1$ , therefore $\phi(n)< n$ for all $n$.

What is the best lower bound for $\phi(n)$?

  • $\begingroup$ It can't be true because $\lim\inf\frac{\varphi(n)}{n}= 0$. See en.wikipedia.org/wiki/… for estimates of how $\varphi$ grows. $\endgroup$ – lhf Jan 23 '12 at 15:11

The statement is false, with the first counterexample being 30030, for which $\phi(30030) = 5760 < \frac{30030}{5} = 6006$.

Also, if it's of any interest, all counterexamples below 10 million have at least 6 distinct prime divisors. For example, $30030 = 2 \times 3 \times 5 \times 7 \times 11 \times 13$.

  • $\begingroup$ You are right . Can you find counterexample for : $\phi(n) > \frac{n}{6}$ ? $\endgroup$ – Peđa Terzić Jan 23 '12 at 14:41
  • 6
    $\begingroup$ Yes, for example $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23$ :) $\endgroup$ – Sp3000 Jan 23 '12 at 14:44

Since $\phi(n)=n (1-\frac{1}{p_1}) \dots (1-\frac{1}{p_k})$ (where $n=p_1^{a_1} \dots p_k^{a_k}$), it is equivalent to asking if $(1-\frac{1}{p_1}) \dots (1-\frac{1}{p_k}) > \frac{1}{5}$, the minimal counterexample must be a product of first $k$ primes (because taking a smaller prime decreases the product); by direct calculation $2 \cdot 3 \cdot \dots \cdot 13 = 30030$ gives about 0.192. In general the product diverges to 0, which follows from this proof. So your inequality is not true even if you replace 5 with a larger, fixed number, and the smallest counterexample will be the product of $k$ first primes for some $k$.

  • 1
    $\begingroup$ +1 for giving a proper, easy to understand explanation for the general case $\endgroup$ – Sp3000 Jan 23 '12 at 14:48
  • $\begingroup$ I think you mean the product $\prod_{k=1}^{\infty}( 1 - \frac{1}{p_k} )$ is $0$, that is the sequence of partial products converges to $0.$ $\endgroup$ – Geoff Robinson Jan 23 '12 at 15:00
  • 2
    $\begingroup$ Geoff: Yes, this is what I meant. The terminology is that infinite products diverge to 0. $\endgroup$ – sdcvvc Jan 23 '12 at 15:06
  • $\begingroup$ No, it's a the related sum $\sum\frac{1}{p}$ that diverges. The terminology is the same for products. $\endgroup$ – bgins Jan 23 '12 at 15:12
  • $\begingroup$ bgins: See lead of Wikipedia on infinite product. The proof that $\sum \frac{1}{p}$ diverges uses that product (precisely, its inverse $\prod_p \frac{1}{1-p^{-1}}$), you can also show it via $\prod_{k=1}^{n} (1-\frac{1}{p_k}) \leq \prod_{k=1}^{n} \exp(-1/p_k)=\exp(-\sum_{k=1}^{n} 1/p_k) \to 0$. $\endgroup$ – sdcvvc Jan 23 '12 at 15:20

As the other answers have pointed out, the answer is no, and this remains true if we replace $5$ with any larger integer. This raises the question, what is the optimal lower bound? The following theorem completely answers this:

Theorem: For all $n\geq 3$ we have $$\phi(n)\geq \frac{n}{e^{\gamma}\log \log n}+O\left(\frac{n}{(\log \log n)^2}\right),$$ where $\gamma$ is the Euler-Mascheroni Constant, and the above holds with equality infinitely often.

Remark: Note in particular that since $\log \log n\rightarrow \infty$ as $n$ grows large, we see that the result $\frac{n}{m}<\phi(n)$ cannot hold for any fixed integer $m$.

Proof: Consider $\mathcal{R}$, the set of all $n$ such that $m<n$ implies $\frac{\phi(n)}{n}<\frac {\phi(m)}{m}$. This set is then all of the "record breaking" $n$. If $n\in\mathcal{R}$ has $k$ prime factors, let $n^*$ be the product of the first $k$ prime factors. If $n\neq n^*$, then $n^*<n$ and $\frac{\phi(n^*)}{n^*}\leq \frac{\phi(n)}{n}$, which is impossible. Hence $\mathcal{R}$ consist entirely of $n$ of the form $n=\prod_{p\leq y}p$ for some $y$.

Now for $n\in \mathcal{R}$, we can choose $y$ so that $\log n=\sum_{p\leq y} \log p=\theta (y)$. Then using one of Mertens estimates we see that $$\frac{\phi(n)}{n}=\prod_{p\leq y}\left(1-\frac{1}{p}\right)=\frac{e^{-\gamma}}{\log y}+O\left(\frac{1}{(\log y)^2}\right).$$ Since $\log \log n =\log (\theta(y))=\log y+O(1)$ by Mertens estimates again, we have for $n\in\mathcal{R}$ $$\phi(n)=\frac{ne^{-\gamma}}{\log\log n}+O\left(\frac{1}{(\log \log n)^2}\right).$$ This along with the definition of $\mathcal{R}$ implies the desired result.

Edit: Added in the proof. This proof and statement of the result is Theorem 2.9 in Montgomery and Vaughn's multiplicative number theory.

  • $\begingroup$ Hi Eric. I know this is a very old answer, so please forgive me for asking a question on it. But I was wondering about some of the notation here, which I've noticed is very common in number theory. Firstly, what does the statement $f(n) \geq g(n) + O(h(n))$ mean? Is it the same as "$f(n) \geq k(n)$ for some function $k$ which has the property that $k(n) = g(n) + O(h(n))$"? In that case do we have enough information to determine whether $f(n) \geq g(n)$ or $f(n) \leq g(n)$? Secondly, what does it mean for equality to hold in an asymptotic inequality like $f(n) \geq g(n) + O(h(n))$? $\endgroup$ – Antonio Vargas Nov 21 '13 at 15:03
  • 1
    $\begingroup$ @AntonioVargas Yes to your first question, and no, it is not quite strong enough to imply that $f(n) \ge g(n)$. For the last question, it means (in the context of the statement) that there is an infinite sequence of integers $n$ such that $f(n) = g(n) + O(h(n))$ for $n$ restricted to that sequence. You're right that equality at a particular integer doesn't hold much meaning for an asymptotic. $\endgroup$ – Erick Wong May 14 '15 at 23:19
  • $\begingroup$ Sorry to bump an old topic, but I think something doesn't add up (though by my lack of experience, I might be mistaken). The inequality $\varphi(n)\geq \frac{n}{e^{\gamma}\log \log n}$ follows from the theorem you stated, assuming $O(\cdot)$ is positive. But Nicolas proved that this inequality does not hold for infinitely many $n$'s. The correct form of the theorem seems to be $\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$, see en.wikipedia.org/wiki/Euler%27s_totient_function#Growth_rate. $\endgroup$ – M.S. Dousti Mar 19 '16 at 19:49
  • $\begingroup$ @M.S.Dousti: That's capture by the big-$O$ term in the expression I give above. $\endgroup$ – Eric Naslund Mar 20 '16 at 14:53
  • $\begingroup$ @EricNaslund: Thanks for the response. As I wrote in my comment, I built up my argument around the assumption that "$O(\cdot)$ is positive." If $O\left(\frac{n}{(\log \log n)^2}\right)$ is meant to capture a negative quantity (which is allowed under the definition of big-$O$), then everything adds up. $\endgroup$ – M.S. Dousti Mar 20 '16 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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