# Proof on Perfect Numbers

• October 20th 2006, 07:13 AM
EverlastingF
Proof on Perfect Numbers
Need to prove Euclid's theorem:

If p = 2^k - 1 is prime, then N = (2^(k-1))2^(k-1) is a perfect number

And have to explain how this relates to Mersenne primes, and show what Euler subsequently proved based on Euclid's results.

Thanks.
• October 20th 2006, 07:42 AM
ThePerfectHacker
Quote:

Originally Posted by EverlastingF
Need to prove Euclid's theorem:

If p = 2^k - 1 is prime, then N = (2^(k-1))2^(k-1) is a perfect number

And have to explain how this relates to Mersenne primes, and show what Euler subsequently proved based on Euclid's results.

Thanks.

Euler did not prove it, Euiclid did.

The important fact that the sum of divisors number-theortic function $\sigma$ is weakely multiplicative.
That is if $\gcd(a,b)=1$ then,
$\sigma(ab)=\sigma(a)\cdot \sigma(b)$
The prove is simple because,
$\sigma(n)=\sum_{d|n}d$
Since $f(d)=d$ is multiplicative so that is $\sigma$.

What is $\sigma(N)$ where $N=(2^k-1)(2^{k-1})$?
Since $2^k-1$ is odd and $2^{k-1}$ only have even divisors we have,
$\gcd(2^k-1,2^{k-1})=1$
Thus,
$\sigma(N)=\sigma\left( 2^k-1\right) \sigma \left(2^{k-1} \right)$
Now,
$2^k-1$ is a Mersenne prime thus,
$\sigma(2^k-1)=2^k$
And,
$\sigma(2^{k-1})=1+2+2^2+...+2^{k-1}$
That is a geometric series whose sum is,
$2^k-1$
Thus,
$\sigma(N)=2^k\cdot \left(2^k-1\right)=2N$
Thus,
$N$ is perfect.

(The converse that an even perfect number has this form is a little bit more complicated).
Q.E.D.
• October 20th 2006, 08:44 AM
AfterShock
Quote:

Originally Posted by EverlastingF
Need to prove Euclid's theorem:

If p = 2^k - 1 is prime, then N = (2^(k-1))2^(k-1) is a perfect number

And have to explain how this relates to Mersenne primes, and show what Euler subsequently proved based on Euclid's results.

Thanks.

Theorem (Euclid)

If p = 2^k - 1 is prime, then N = [(2^(k - 1))]*2^(k - 1)

First of all, perfect numbers are:

6 (1 + 2 + 3)
28
496
8128
.
.
.
And so forth.

Lemma: (1 + 2 + 4 + 8 + ... + 2^(m) = 2^(m + 1) - 1
Multiply both sides by (2 - 1)

(2 - 1)(1 + 2 + 4 + 8 + ... + 2^(m)) = 2^(m+1) - 1

Proof: N = p*2^(k-1) is the prime factorization of N adding up all proper divisdors of N

1 + 2 + 4 + ... + 2^(k-1) + p + 2p + ... + 2^(k-2)*p

((2^k)-1) + p(1 + 2 + ... + 2^(k-2))

p + p*(2^(k-1) - 1)

p*2^(k - 1)

= N (N is perfect).

Q.E.D.

To find perfect numbers, all we need are Mersenne primes (no one knows how many exist), in the form of p = 2^k - 1

Euler's method:

If N is even and perfect, then N is of the form N = (2^(k) - 1)*(2^(k - 1))

Noone has proved that there are no odd perfect numbers. On the contrary, no one has ever found one.

Although this is not part of your question, I think it's quite interesting that Euler showed in 1772 that 2^(31) - 1 is a mersenne prime, which means that:
(2^(31) - 1)*2^30 is a perfect number.

That's quite amazing.
• October 20th 2006, 09:07 AM
ThePerfectHacker
Quote:

Originally Posted by AfterShock

Euler's method:

If N is even and perfect, then N is of the form N = (2^(k) - 1)*(2^(k - 1))

Thank you Aftershock, I made a mistake, the converse of even perfect numbers was accomplished by the great Euler.

Quote:

Noone has proved that there are no odd perfect numbers. On the contrary, no one has ever found one.
I will. All theorem concenring infinitude are very complicated. They usually involve using Euclid's trick: assume there are finitely many.
Quote:

Although this is not part of your question, I think it's quite interesting that Euler showed in 1772 that 2^(31) - 1 is a mersenne prime, which means that:
(2^(31) - 1)*2^30 is a perfect number.
Another interesting thing about even perfect numbers is that they end in either 6 or 8.