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.

  • $\begingroup$ 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 ? $\endgroup$ – Peđa Terzić Feb 2 '12 at 14:28
  • $\begingroup$ @pedja: Sorry, I misread the even and odd part. However, the lower bound of $\frac{m}{3}+O(1)$ cannot hold. $\endgroup$ – Eric Naslund Feb 2 '12 at 14:32
  • $\begingroup$ ,I wrote small Maple program that examines this conjecture...I cannot find counterexample for the second part of the statement.. $\endgroup$ – Peđa Terzić Feb 2 '12 at 14:35
  • 2
    $\begingroup$ @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. $\endgroup$ – Eric Naslund Feb 2 '12 at 14:40
  • $\begingroup$ ,You are correct,that is counterexample... $\endgroup$ – Peđa Terzić Feb 2 '12 at 14:48

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.