Help with proving that $\phi(n)$ $\ge$ ${\sqrt n} \over 2$

893 Views Asked by At

So far I have

$${{\phi(n)^2} \over n} = n \prod_{i = 1}^k \left(1 - {1 \over p_i}\right)^2$$

We know that $$\left(1 - \frac{1}{p_i}\right) \geq \frac{1}{2}$$

So $$n \prod_{i = 1}^k \left(1 - {1 \over p_i}\right)^2 \geq \frac{n}{4^k} = \frac{n}{2^{2k}}$$

Want to show that $$\frac{n}{2^{2k}} \geq \frac{1}{2}$$

$n \geq 2^{2k - 1}$

Got stuck here. Any help to prove this?

EDIT: Ok so I looked at the answer in the thread provided and I don't understand how $\frac{\phi(n)^2}{n}= \prod_{p|n \ \text{prime}} \frac{(p^{a_p-1}(p-1))^2}{p^{a_p}}$

There's a factor of n missing since the $\phi$ function is being squared

1

There are 1 best solutions below

1
On

$$1\leq p\left(1-\frac{1}{p}\right)^2$$ except when $p=2$.