# Thread: (easy?) Proof: divisors and primality

1. ## (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?

2. 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)