Results 1 to 7 of 7

Math Help - For any integer n

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    6

    For any integer n

    For any integer n show that there exist integers k and j such that φ(k)+σ(j)=n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by ogajawasungu View Post
    For any integer n show that there exist integers k and j such that φ(k)+σ(j)=n
    In words, show that for all n there exists integers k and j such that the number of divisors of j plus the number of numbers coprime to and less than k is n.

    So, I would note that \sigma(p^m) = m+1 so taking k=0,  j=p^{n-1}.

    However, this is only for the natural numbers and zero...not the whole integers. You can't get a negative number of divisors!

    It is also a somewhat boring result - why the Euler totient function if we can just forget about it?...

    Have you perhaps missed out something from the question?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    6
    Sorry, the question should read; find all integers n such that σ(n)+φ(n)=2n
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by ogajawasungu View Post
    Sorry, the question should read; find all integers n such that σ(n)+φ(n)=2n
    That's a huge typo!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2010
    Posts
    913
    Thanks
    205
    If p is prime, then sigma(p)=p+1 (since there are only the two factors, 1 and p). Also, phi(p)=p-1 since all of the integers from 1 to p-1 are coprime to p, so sigma(p)+phi(p)=2p.

    I think it's probably true, but I can't see a way to prove that there are no composite n with sigma(n)+phi(n)=2n.

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by hollywood
    I think it's probably true, but I can't see a way to prove that there are no composite n with sigma(n)+phi(n)=2n.
    Take n = pq with p and q prime. \varphi{(n)} = (p - 1)(q - 1), \sigma{(n)} = p + q + pq + 1

    So \varphi{(n)} + \sigma{(n)} = (p - 1)(q - 1) + p + q + pq + 1 = pq - p - q + 1 + p + q + pq + 1  = 2pq + 2 = 2n + 2 \color{red}{\ \neq 2n}

    Oops, I just wiped out all semiprimes

    I believe there is a general proof that can be built around this with infinitely many prime factors instead of a semiprime. I've seen it but unfortunately forgot it, I'll have to check it out some time.

    Conclusion : only prime numbers satisfy this statement, along with 1, assuming the validity and existence of the GFP (Generalized Forgotten Proof )
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Bacterius View Post
    ...assuming the validity and existence of the GFP (Generalized Forgotten Proof )
    That GFP sounds very useful! I'll have to use it in future proofs in coordination with TAMH.


    (Then a Miracle Happens, for the uninitiated.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: August 3rd 2010, 03:16 AM
  2. integer?
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: May 30th 2010, 04:43 AM
  3. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 12:39 PM
  4. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 12:20 PM
  5. [SOLVED] even integer and odd integer
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 1st 2008, 08:35 PM

Search Tags


/mathhelpforum @mathhelpforum