Prove that $\phi(n) \geq \sqrt{n}/2$

Solution 1:

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}} $$

Solution 2:

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}$$