Show that $\phi(n)+\sigma(n) \ge 2n$ for all positive integers $n$.
Problem
Source:
Tags: function, number theory, totient function, Divisor Functions
22.07.2007 06:11
Robert Gerbicz wrote: Let $ n$ be a positive integer, and it's prime factorization is: $ n=\prod_{i=1}^{k}{{p}_{i}^{{a}_{i}}}$, then $ {\sigma(n)}\geq \prod_{i=1}^{k}({{p}_{i}^{{a}_{i}}}+{{p}_{i}^{{a}_{i}-1}})=n*\prod_{i=1}^{k}(1+\frac{1}{{p}_{i}})$ and it is well known that $ \phi(n)=n*\prod_{i=1}^{k}(1-\frac{1}{{p}_{i}})$ from these we can get: $ \sigma(n)+\phi(n)\geq n*(\prod_{i=1}^{k}(1+\frac{1}{{p}_{i}})+\prod_{i=1}^{k}(1-\frac{1}{{p}_{i}}))$ So it is enough to prove that $ \prod_{i=1}^{k}(1+\frac{1}{{p}_{i}})+\prod_{i=1}^{k}(1-\frac{1}{{p}_{i}})\geq 2$ is true. And this is easy because if we expand the products then there are the same numbers in the two products: in the first product the sign is always positive and in the second product the sign is positive or negative, so the sum of these two products is nonnegative, but there are 1 and 1 in the two products so the sum is is at least 2.
19.08.2012 18:59
Alternatively, using the Möbius Inversion Formula for Euler's totient function, we get \begin{align*} \phi(n) + \sigma(n) &= \sum_{d \mid n} \mu\left(d\right)\frac{n}{d}+\sum_{d \mid n} d =\sum_{d \mid n} \mu\left(\frac{n}{d}\right)d+\sum_{d \mid n} d \\&= \sum_{d \mid n} \left(\mu\left(\frac{n}{d}\right)+1\right)d =2n+\sum_{\substack{{d \mid n}\\{d < n}}} \left(\mu\left(\frac{n}{d}\right)+1\right)d \\& \geq 2n\,. \end{align*} The equality holds if and only if $\mu\left(\frac{n}{d}\right)=-1$ for every proper divisor $d$ of $n$. Equivalently, $n=1$ or $n$ is a prime number is the necessary and sufficient condition for the equality case.