1. How can I show that

$\displaystyle \phi(n) \geq \sqrt{n/2}.$

Write
$\displaystyle n= {p_1}^n_1...{p_r}^n_r.$
Then

$\displaystyle \frac {\phi({p_1}^n_1)}{\sqrt {n}} = \frac{(p_1-1)p^{n_1-1}}{p_1^{n_1/2}}$

then what?

2. First we must have $\displaystyle n\geq{2}$ for the ineuqality to hold

You'll need these 2 inequalities (by $\displaystyle p$ I mean prime):

$\displaystyle \left\{ \begin{gathered} \phi \left( {2^k } \right) = 2^{k - 1} \geqslant \sqrt {\tfrac{{2^k }} {2}} = 2^{\tfrac{{k - 1}} {2}} \hfill \\ \phi \left( {p^k } \right) = p^{k - 1} \cdot \left( {p - 1} \right) \geqslant \sqrt {p^k }{\text{ if }}p > 2 \hfill \\ \end{gathered} \right.$ for $\displaystyle k\geq{1}$

For the second:

$\displaystyle p - \sqrt p + \tfrac{1} {4} = \left( {\sqrt{p} - \tfrac{1} {2}} \right)^2 \geqslant \left( {\sqrt{3} - \tfrac{1} {2}} \right)^2 \geqslant \tfrac{5} {4}\therefore p - 1 \geqslant \sqrt p \geqslant p^{1 - \tfrac{k} {2}}$ $\displaystyle \Rightarrow p - 1 \geqslant p^{1 - \tfrac{k} {2}}$

Now your inequality follows easily from the fact that $\displaystyle \phi$ is multiplicative.

In fact, you can see from the inequalities above -check the equality conditions- that your inequality is strict for all $\displaystyle n>2$

3. Thank you very much for the very clear and detailed answer.

4. Dont you think that there is something wrong with it because if we say
n=2^r_0*p_1^r_1*...*p_m^r_m,

then dont you think that we missing odd numbers?

5. Originally Posted by peteryellow
Dont you think that there is something wrong with it because if we say
n=2^r_0*p_1^r_1*...*p_m^r_m,

then dont you think that we missing odd numbers?
If you followed what I said you'd get $\displaystyle \phi(n)>\sqrt{n}$ for $\displaystyle n$ odd (n greater than 1). Which is in fact stronger because $\displaystyle \sqrt{n}>\sqrt{\tfrac{n}{2}}$

You take from above the factors that you need.