# Thread: Eulers totient function

1. How can I show that

$

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

Write
$

n= {p_1}^n_1...{p_r}^n_r.
$

Then

$

\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 $n\geq{2}$ for the ineuqality to hold

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

$
\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 $k\geq{1}$

For the second:

$
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}}
$
$
\Rightarrow p - 1 \geqslant p^{1 - \tfrac{k}
{2}}$

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

In fact, you can see from the inequalities above -check the equality conditions- that your inequality is strict for all $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 $\phi(n)>\sqrt{n}$ for $n$ odd (n greater than 1). Which is in fact stronger because $\sqrt{n}>\sqrt{\tfrac{n}{2}}$

You take from above the factors that you need.