Proof with arithmetic functions

**comssa** · November 23rd 2009, 04:40 PM

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

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

I am not too sure about the other direction.

If you let $n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot\cdot\cdot p_k^{\alpha_k}$
then $\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)$
$\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.

**chiph588@** · November 23rd 2009, 07:31 PM

If $n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot\cdot\cdot p_k^{\alpha_k}$ , then $\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 $\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)$ .

$\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 +$ ... $+ \frac{1}{p_1^{\alpha_1-1}}) \cdot\cdot\cdot (p_k+1 + ... + \frac{1}{p_k^{\alpha_k-1}}))$ .

Hence $\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 $(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!

**tonio** · November 24th 2009, 05:58 AM

Originally Posted by comssa

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

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

I am not too sure about the other direction.

If you let $n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot\cdot\cdot p_k^{\alpha_k}$
then $\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)$
$\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.

$\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}$ $\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}$ $\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 $\prod\limits_{i=1}^k\left(p_i^{\alpha_i+1}-1\right)\geq \prod\limits_{i=1}^kp_i^{\alpha_1}$ and $p_i-1\geq 1\,\,\forall\,i$ , we get that (***) is true,

and then we go back and get our original inequality.

Tonio

Thread: Proof with arithmetic functions

LinkBack

Thread Tools

Display

Proof with arithmetic functions

Similar Math Help Forum Discussions

Arithmetic proof

Arithmetic functions

Multiplicative Arithmetic Functions

Arithmetic Functions

Arithmetic Functions.

Search Tags