10
$\begingroup$

So I'm trying to prove the following two inequalities: $$\frac{\sqrt{n}}{2} \leq \phi(n) \leq n.$$ The upper bound we get from simply noting that $\phi(n) = n \prod_{p | n}\left( 1 - \frac{1}{p}\right)$ and the fact that $(1 - \frac{1}{p}) \leq 1$. But how can we get the lower bound? I tried using the same expression for $\phi(n)$ but it seems to not really give me the inequality. Can you help?

$\endgroup$
  • 2
    $\begingroup$ The upper bound is trivial by definition. $\endgroup$ – lhf Oct 16 '13 at 3:06
  • $\begingroup$ Right since of course there can be at most $n$ relatively prime integers less than or equal to $n$. But what about the lower bound? $\endgroup$ – Numbersandsoon Oct 16 '13 at 3:15
  • $\begingroup$ see math.stackexchange.com/questions/301837/… $\endgroup$ – Will Jagy Oct 16 '13 at 3:45
10
$\begingroup$

We have

$$ \frac{\phi(n)^2}{n}= \prod_{p|n \ \text{prime}} \frac{(p^{a_p-1}(p-1))^2}{p^{a_p}} = \prod_{p|n \ \text{prime}} p^{a_p-2} (p-1)^2 \geq \prod_{p|n \ \text{prime}} \frac{(p-1)^2}{p} $$

Now for $p\geq 3$ we have $p^2-3p+1=1+p(p-3)\geq 0$ so $p^2-2p+1 \geq p$ and hence $\frac{(p-1)^2}{p} \geq 1$.

So

$$ \frac{\phi(n)^2}{n} \geq \prod_{p|n \ p=2} \frac{(p-1)^2}{p} $$

When $2$ does not divide $n$, this gives a lower bound of $1$. When $2$ divides $n$, this gives a lower bound of $\frac{1}{2}$. In any case, we always have $\frac{\phi(n)^2}{n} \geq \frac{1}{2}$. We deduce the stronger inequality

$$ \phi(n) \geq \sqrt{\frac{n}{2}} $$

$\endgroup$
  • $\begingroup$ Nice! Great proof. $\endgroup$ – Numbersandsoon Oct 16 '13 at 4:46
7
$\begingroup$

Let $n = p_1 p_2 \cdots p_k q_1^{a_1} q_2^{a_2} \cdots q_l^{a_l}$, where $a_r \geq 2$. Let $m = p_1 p_2 \cdots p_k$, while $s = q_1^{a_1} q_2^{a_2} \cdots q_l^{a_l}$.

We then have $\phi(n) = \phi(m) \phi(s)$. Hence, $\dfrac{\phi(n)}{\sqrt{n}} = \dfrac{\phi(m)}{\sqrt{m}} \dfrac{\phi(s)}{\sqrt{s}}$. $$\dfrac{\phi(m)}{\sqrt{m}} = \prod_{i=1}^{k} \dfrac{p_i-1}{\sqrt{p_i}}$$ Now note that $\dfrac{x-1}{\sqrt{x}} > 1$ for $x > 3$. For $p_i=2$, we have $\dfrac{p_i-1}{\sqrt{p_i}} = \dfrac1{\sqrt2}$. Hence, $\dfrac{\phi(m)}{\sqrt{m}} \geq \dfrac1{\sqrt2}$.

$$\dfrac{\phi(s)}{\sqrt{s}} = \prod_{i=1}^{l} q_i^{a_i-1}(q_i-1) \geq 1$$ We hence have $$\dfrac{\phi(n)}{\sqrt{n}} \geq \dfrac1{\sqrt2}$$

$\endgroup$
  • $\begingroup$ I like your proof equally as much. Thank you for contributing!! I learned a lot. $\endgroup$ – Numbersandsoon Oct 16 '13 at 4: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.