# Thread: Proof with arithmetic functions

1. ## Proof with arithmetic functions

For any positive integer $\displaystyle n$ prove that $\displaystyle \phi(n) + \sigma(n) \geq 2n$, with equality if and only if $\displaystyle n = 1 \mbox{ or }n$ is a prime.

I figured that if n = 1, they obviously equal. If n is a prime, you get$\displaystyle (n - 1) + (1 + n) = 2n$

I am not too sure about the other direction.

If you let $\displaystyle n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot\cdot\cdot p_k^{\alpha_k}$
then $\displaystyle \phi(n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdot\cdot\cdot\left(1 - \frac{1}{p_k}\right)$
$\displaystyle \sigma(n) = \left(\frac{p_1^{\alpha_1 + 1} - 1}{p_1 - 1}\right)\left(\frac{p_2^{\alpha_2 + 1} - 1}{p_2 - 1}\right)\cdot\cdot\cdot\left(\frac{p_k^{\alpha_k + 1} - 1}{p_k - 1}\right)$

and then I am stuck. Can anyone help me? Thanks.

2. If $\displaystyle n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot\cdot\cdot p_k^{\alpha_k}$, then $\displaystyle \phi(n) = p_1^{\alpha_1-1}p_2^{\alpha_2-1} \cdot\cdot\cdot p_k^{\alpha_k-1}(p_1-1)(p_2-1) \cdot\cdot\cdot (p_k-1)$

and $\displaystyle \sigma(n) = (p_1^{\alpha_1}+p_1^{\alpha_1-1} + \cdot\cdot\cdot + 1)(p_2^{\alpha_2}+p_2^{\alpha_2-1} + \cdot\cdot\cdot + 1) \cdot\cdot\cdot (p_k^{\alpha_k}+p_k^{\alpha_k-1} + \cdot\cdot\cdot + 1)$.

$\displaystyle \phi(n)+\sigma(n) = p_1^{\alpha_1-1}p_2^{\alpha_2-1} \cdot\cdot\cdot p_k^{\alpha_k-1}((p_1-1)(p_2-1) \cdot\cdot\cdot (p_k-1)+(p_1+1 +$ ... $\displaystyle + \frac{1}{p_1^{\alpha_1-1}}) \cdot\cdot\cdot (p_k+1 + ... + \frac{1}{p_k^{\alpha_k-1}}))$.

Hence $\displaystyle \phi(n)+\sigma(n) \geq p_1^{\alpha_1-1}p_2^{\alpha_2-1} \cdot\cdot\cdot p_k^{\alpha_k-1}((p_1-1)(p_2-1) \cdot\cdot\cdot (p_k-1)+(p_1+1)(p_2+1) \cdot\cdot\cdot (p_k+1))$.

Now all you need to show is that $\displaystyle (p_1-1)(p_2-1) \cdot\cdot\cdot (p_k-1)+(p_1+1)(p_2+1) \cdot\cdot\cdot (p_k+1) > 2p_1p_2 \cdot\cdot\cdot p_k$ and you're done!

3. Originally Posted by comssa
For any positive integer $\displaystyle n$ prove that $\displaystyle \phi(n) + \sigma(n) \geq 2n$, with equality if and only if $\displaystyle n = 1 \mbox{ or }n$ is a prime.

I figured that if n = 1, they obviously equal. If n is a prime, you get$\displaystyle (n - 1) + (1 + n) = 2n$

I am not too sure about the other direction.

If you let $\displaystyle n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot\cdot\cdot p_k^{\alpha_k}$
then $\displaystyle \phi(n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdot\cdot\cdot\left(1 - \frac{1}{p_k}\right)$
$\displaystyle \sigma(n) = \left(\frac{p_1^{\alpha_1 + 1} - 1}{p_1 - 1}\right)\left(\frac{p_2^{\alpha_2 + 1} - 1}{p_2 - 1}\right)\cdot\cdot\cdot\left(\frac{p_k^{\alpha_k + 1} - 1}{p_k - 1}\right)$

and then I am stuck. Can anyone help me? Thanks.

$\displaystyle \phi(n)+\sigma(n)\geq 2n\Longleftrightarrow \prod\limits_{i=1}^k\left(p_i^{\alpha_i}-p_i^{\alpha_i-1}\right)+\prod\limits_{i=1}^k\frac{p_i^{\alpha_i+ 1}-1}{p_i}\geq 2\prod\limits_{i=1}^kp_i^{\alpha_i}$ $\displaystyle \Longleftrightarrow \frac{\prod\limits_{i=1}^k\left(p_i^{\alpha_i+1}-p_i^{\alpha_i}\right)+\prod\limits_{i=1}^k\left(p_ i^{\alpha_i+1}-1\right)}{\prod\limits_{i=1}^kp_i}\geq 2\prod\limits_{i=1}^kp_i^{\alpha_i}$ $\displaystyle \Longleftrightarrow \prod\limits_{i=1}^kp_i^{\alpha_i}\prod\limits_{i= 1}^k(p_i-1)+\prod\limits_{i=1}^k\left(p_i^{\alpha_i+1}-1\right)\geq 2\prod\limits_{i=1}^kp_i^{\alpha_i+1}$ (***), but since clearly $\displaystyle \prod\limits_{i=1}^k\left(p_i^{\alpha_i+1}-1\right)\geq \prod\limits_{i=1}^kp_i^{\alpha_1}$ and $\displaystyle p_i-1\geq 1\,\,\forall\,i$ , we get that (***) is true,

and then we go back and get our original inequality.

Tonio