# Bounds of Euler's totient function?

Conjecture :

Let $\phi(m)$ be Euler's totient function

$1 \leq \phi(m) \leq \lceil \frac{m-1}{2} \rceil ~~$ if $~~m~~$ is even

$\lceil \frac{m+1}{3} \rceil \leq\phi(m) \leq m-1 ~~$ if $~~m~~$ is odd

Proof :

Case when $m$ is an even number :

Let us make substitution : $m=n-1$ , so:

$n=2^r \cdot q_1^{r_1} \cdot q_2^{r_2} \cdots q_k^{r_k}+1 \Rightarrow$

$\Rightarrow \phi(n-1)=\phi(2^r) \cdot \phi(q_1^{r_1})\cdots \phi(q_k^{r_k})=\phi(2^r) \cdot q_1^{r_1-1}(q_1-1)\cdots q_k^{r_k-1}(q_k-1)=$

$=\phi(2^r) \cdot q_1^{r_1} \frac{(q_1-1)}{q_1} \cdots q_k^{r_k} \frac{(q_k-1)}{q_k} < \phi(2^r) \cdot \frac{n-1}{2^r}=2^{r-1}\cdot \phi(2) \cdot \frac{n-1}{2^r}=\frac{n-1}{2}= \lceil \frac{n}{2}-1 \rceil \Rightarrow$

$\Rightarrow \phi(m) < \lceil \frac{m-1}{2} \rceil$

Question : How to prove the second part of the statement, (case when $m$ is an odd number) ?

Statement 2: The upper bound does hold by the multiplicative property of $\phi(n)$, however the lower bound is not true. In fact for any fixed integer $k$, $\frac{m}{k} \leq \phi(m)$ cannot hold for all $m$. A counter example is given by considering the integer $$M_x:=\prod_{p\leq x,\ p\neq 2} p.$$
As $x$ grows $\frac{\phi(M_x)}{M_x}$ becomes arbitrarily small.

The exact lower growth rate is given precisely by the following theorem:

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.

For more details, and a proof of the above, see this answer.

• for the firs part $m$ cannot be prime since it is an even number...you didn't read statement well..Can you give me one counterexample for the second part of the statement ? – Peđa Terzić Feb 2 '12 at 14:28
• @pedja: Sorry, I misread the even and odd part. However, the lower bound of $\frac{m}{3}+O(1)$ cannot hold. – Eric Naslund Feb 2 '12 at 14:32
• ,I wrote small Maple program that examines this conjecture...I cannot find counterexample for the second part of the statement.. – Peđa Terzić Feb 2 '12 at 14:35
• @pedja: Try $$m=3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot29= 3 234 846 615.$$ Then by multiplicativity $$\phi(3 234 846 615)=2\cdot4\cdot6\cdot10\cdot12\cdot16\cdot18\cdot22\cdot28=1 021 870 080.$$ Here $\phi(m)<\frac{m}{3}-1$. Searching numerically will be very very difficult since $\log \log n$ grows extremely slowly. If you changed the $3$ to a $100$, I would not be able to find a counter example, as it would have to be of size $$e^{e^{100}},$$ which has roughly $e^{99}$ digits. – Eric Naslund Feb 2 '12 at 14:40
• ,You are correct,that is counterexample... – Peđa Terzić Feb 2 '12 at 14:48