# euler function property $\varphi(n)\geq\sqrt{n}$ [duplicate]

How to prove that $\varphi(n)\geq \sqrt{n}$ for every positive integer $n$ distinct of $2$ and $6$.

## marked as duplicate by Erick Wong, Dietrich Burde, user223391, user147263, ncmathsadistJul 15 '15 at 20:01

• @Wojowu The case $n \equiv 2 \pmod{4}$ makes it a little harder. – Daniel Fischer Jul 15 '15 at 19:30
• From the duplicate's answer: Show that if $n$ is odd or a multiple of $4$, then $\varphi(n)\ge\sqrt n$; for this you’ll use the prime factorization of $n$ and the multiplicativity of $\varphi$. Then handle the case $n=2m$ with $m$ odd by using the multiplicativity of $\varphi$ to write $\varphi(n)=\varphi(2)\varphi(m)$. – Dietrich Burde Jul 15 '15 at 19:32
• @DietrichBurde It seems to me the "duplicate" proved only that $\varphi(n)\geq \sqrt{n}$ when $n\not\equiv 2 \pmod 4$ and $\varphi(n)\geq \sqrt{n}/\sqrt2$ when $n\equiv 2 \pmod 4$. – David K Jul 15 '15 at 19:54
$$\frac{\phi(n)}{n}=\prod_{p\mid n}\left(1-\frac{1}{p}\right)\geq \prod_{p\leq n}\left(1-\frac{1}{p}\right)=\frac{1}{\sum_{m\in A_n}\frac{1}{m}}$$ where $A_n$ is the set of $n$-smooth numbers, i.e. the set of numbers having all their prime divisors $\leq b$. You just have to prove that: $$\sum_{m\in A_n}\frac{1}{m}\leq \sqrt{n}.$$ A good idea is to consider that: $$\sum_{m\in A_n}\frac{1}{m} = 1 +\sum_{p\leq n}\frac{1}{p}+\sum_{\substack{m\in A_n\\ \Omega(m)\geq 2}}\frac{1}{m} \leq \sum_{p\leq n}\frac{1}{p}+\left(\sum_{m\in A_n}\frac{1}{m}\right)^2$$ then it is enough to (roughly) estimate $\sum_{p\leq n}\frac{1}{p}$.