Results 1 to 2 of 2

Math Help - (easy?) Proof: divisors and primality

  1. #1
    Member
    Joined
    Feb 2008
    Posts
    79

    (easy?) Proof: divisors and primality

    Prove:

    For all pos. integers n, if sum of divisors of n is n+1, then n is prime.

    Apparently this is famous. This is an intro course though and the proofs I found tend to be complicated. Prove it by contrapositive? Or contradiction?

    Anyone know how to prove it?

    The proof I found is: the sum of divisors is at least n+1 since 1 and n divide n. If it's n+1, we then know there are no other divisors. Thus, n is prime.

    How do we know there are no other divisors?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by DiscreteW View Post
    Prove:

    For all pos. integers n, if sum of divisors of n is n+1, then n is prime.

    Apparently this is famous. This is an intro course though and the proofs I found tend to be complicated. Prove it by contrapositive? Or contradiction?

    Anyone know how to prove it?

    The proof I found is: the sum of divisors is at least n+1 since 1 and n divide n. If it's n+1, we then know there are no other divisors. Thus, n is prime.

    How do we know there are no other divisors?
    if there were any other divisors, the sum would be greater than (n + 1) since we would be adding more positive numbers to that number. it would have to mean that 1 and n are not the only divisors, so n would be composite if the sum of the divisors exceed (n + 1)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relitivly prime, unique divisors of divisors
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 24th 2010, 08:40 AM
  2. Sum of divisors proof question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 30th 2010, 09:40 PM
  3. Ironing out the Lucas Primality Test proof
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 24th 2010, 06:31 PM
  4. σ sum of divisors proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 30th 2009, 02:39 AM
  5. Easy thing about divisors
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 30th 2006, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum