(easy?) Proof: divisors and primality

• Feb 10th 2009, 07:49 PM
DiscreteW
(easy?) Proof: divisors and primality
Prove:

For all pos. integers \$\displaystyle n\$, if sum of divisors of \$\displaystyle n\$ is \$\displaystyle n+1\$, then \$\displaystyle 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 \$\displaystyle n+1\$ since \$\displaystyle 1\$ and \$\displaystyle n\$ divide \$\displaystyle n\$. If it's \$\displaystyle n+1\$, we then know there are no other divisors. Thus, \$\displaystyle n\$ is prime.

How do we know there are no other divisors?
• Feb 10th 2009, 08:11 PM
Jhevon
Quote:

Originally Posted by DiscreteW
Prove:

For all pos. integers \$\displaystyle n\$, if sum of divisors of \$\displaystyle n\$ is \$\displaystyle n+1\$, then \$\displaystyle 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 \$\displaystyle n+1\$ since \$\displaystyle 1\$ and \$\displaystyle n\$ divide \$\displaystyle n\$. If it's \$\displaystyle n+1\$, we then know there are no other divisors. Thus, \$\displaystyle 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)