Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

3 Answers

up vote 14 down vote accepted

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

share|improve this answer
    
You are right . Can you find counterexample for : $\phi(n) > \frac{n}{6}$ ? –  pedja Jan 23 '12 at 14:41
6  
Yes, for example $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23$ :) –  Sp3000 Jan 23 '12 at 14:44
add comment

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

share|improve this answer
1  
+1 for giving a proper, easy to understand explanation for the general case –  Sp3000 Jan 23 '12 at 14:48
    
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.$ –  Geoff Robinson Jan 23 '12 at 15:00
2  
Geoff: Yes, this is what I meant. The terminology is that infinite products diverge to 0. –  sdcvvc Jan 23 '12 at 15:06
    
No, it's a the related sum $\sum\frac{1}{p}$ that diverges. The terminology is the same for products. –  bgins Jan 23 '12 at 15:12
    
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$. –  sdcvvc Jan 23 '12 at 15:20
add comment

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.

share|improve this answer
    
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))$? –  Antonio Vargas Nov 21 '13 at 15:03
add comment

Your Answer

 
discard

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.