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.

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

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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.

share|improve 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 ? –  pedja 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.. –  pedja Feb 2 '12 at 14:35
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. –  Eric Naslund Feb 2 '12 at 14:40
    
,You are correct,that is counterexample... –  pedja Feb 2 '12 at 14:48

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.