Prove that $\phi(n) \geq \sqrt{n}/2$ 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?
 A: 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}}
$$
A: 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}$$
