4
$\begingroup$

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

1 Answers 1

10

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.

  • 0
    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 ?2012-02-02
  • 0
    @pedja: Sorry, I misread the even and odd part. However, the lower bound of $\frac{m}{3}+O(1)$ cannot hold.2012-02-02
  • 0
    ,I wrote small Maple program that examines this conjecture...I cannot find counterexample for the second part of the statement..2012-02-02
  • 2
    @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.2012-02-02
  • 0
    ,You are correct,that is counterexample...2012-02-02
  • 0
    The upper limit of part 2 is just $\phi(p) = p - 1$ if $p$ is (an odd) prime. No multiplicativity involved.2014-03-04
  • 0
    @vonbrand: I said "by multplicativity" to mean that the bound holding for primes as you mention implies that it holds for arbitrary $n$. Probably the easiest way to see why $\phi(n)\leq n-1$ is that $0$ is never in the multiplicative group modulo $n$.2014-03-09