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

Question

Así que estoy tratando de probar las siguientes dos desigualdades:$$\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% Parece que no me da la desigualdad. ¿Puede usted ayudar?

Answer 1

Tenemos

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

Ahora para $p\geq 3$ tenemos $p^2-3p+1=1+p(p-3)\geq 0$, por lo que $p^2-2p+1 \geq p$ y, por tanto,$\frac{(p-1)^2}{p} \geq 1$.

Así

$$ \frac{\phi(n)^2}{n} \geq \prod_{p|n \ p=2} \frac{(p-1)^2}{p} $$

Al $2$ no divide $n$, esto le da un límite inferior de $1$. Al $2$ divide $n$, esto le da un límite inferior de $\frac{1}{2}$. En cualquier caso, siempre tenemos $\frac{\phi(n)^2}{n} \geq \frac{1}{2}$. Podemos deducir el más fuerte de la desigualdad

$$ \phi(n) \geq \sqrt{\frac{n}{2}} $$