Results 1 to 3 of 3

Thread: Proof with arithmetic functions

  1. #1
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by comssa View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Arithmetic proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 5th 2010, 08:31 PM
  2. Arithmetic functions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 22nd 2010, 01:29 PM
  3. Multiplicative Arithmetic Functions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 3rd 2009, 06:47 PM
  4. Arithmetic Functions
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 4th 2008, 12:53 PM
  5. Arithmetic Functions.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 5th 2008, 01:50 PM

Search Tags


/mathhelpforum @mathhelpforum