# (easy?) Proof: divisors and primality

• Feb 10th 2009, 08:49 PM
DiscreteW
(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?
• Feb 10th 2009, 09:11 PM
Jhevon
Quote:

Originally Posted by DiscreteW
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)