0
$\begingroup$

This question already has an answer here:

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Hint: you only have to prove this for powers of primes (think about why). $\endgroup$ – Wojowu Jul 15 '15 at 19:28
  • 1
    $\begingroup$ @Wojowu The case $n \equiv 2 \pmod{4}$ makes it a little harder. $\endgroup$ – Daniel Fischer Jul 15 '15 at 19:30
  • $\begingroup$ 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)$. $\endgroup$ – Dietrich Burde Jul 15 '15 at 19:32
  • $\begingroup$ @DanielFischer That's true, I didn't think about all the details of the proof, so I've missed that. $\endgroup$ – Wojowu Jul 15 '15 at 19:34
  • $\begingroup$ @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$. $\endgroup$ – David K Jul 15 '15 at 19:54
0
$\begingroup$

We have:

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.