Results 1 to 3 of 3

Math Help - Proof with arithmetic functions

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

    Proof with arithmetic functions

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

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by comssa View Post
    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
    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: April 5th 2010, 08:31 PM
  2. Arithmetic functions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 22nd 2010, 01:29 PM
  3. Multiplicative Arithmetic Functions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 3rd 2009, 06:47 PM
  4. Arithmetic Functions
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 4th 2008, 12:53 PM
  5. Arithmetic Functions.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 5th 2008, 01:50 PM

Search Tags


/mathhelpforum @mathhelpforum