After some work, I got this nice inequality:

$$ \frac{n^2}{2} < \phi(n)\cdot \sigma(n) $$

where $\phi(n)$ is Euler's phi function and $\sigma(n)= \sum_{d|n} d$. I know this is true because I'm aware that this can be further refined to

$$ \frac{6 n^2}{\pi^2} < \phi(n)\cdot \sigma(n) $$

However, I'm interested in the first one because I'm sure there is an elemental proof of it (which I can't find at the moment). Any ideas?

  • 1
    $\begingroup$ Note if you want the $\varphi$ instead of $\phi$ It's written as \varphi $\endgroup$ – kingW3 Dec 10 '14 at 20:03
  • $\begingroup$ I've seen it written both ways. Is there any standard way of writing it? $\endgroup$ – nabla Dec 10 '14 at 20:06

If $n=\prod_ip_i^{a_i}$, then $$ \sigma(n)=\prod_i \frac{p_i^{a_i+1}-1}{p_i-1}=n\prod_i\frac{1-p_i^{-a_i-1}}{1-p_i^{-1}}, $$ and $$ \phi(n)=n\prod_i(1-p_i^{-1}) $$ Hence we obtain $$ \frac{\sigma(n)\phi(n)}{n^2}=\prod_i (1-p_i^{-a_i-1}). $$ Hence the first inequality is obvious, and the second also: each of the exponents is less than or equal to $−2$, so the product is at least as large as the product 􏰌$\prod_p(1 − p^{−2})=\frac{1}{\zeta(2)}=\frac{6}{\pi^2}$. Hence we obtain $$ 6\frac{n^2}{\pi^2}<\sigma(n)\phi(n). $$ The first inequality is obtained if we just use $\frac{1}{\zeta(2)}>\frac{1}{2}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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