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.

Printable View

- Oct 20th 2006, 08:13 AMEverlastingFProof 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. - Oct 20th 2006, 08:42 AMThePerfectHacker
Euler did not prove it, Euiclid did.

The important fact that the sum of divisors number-theortic function is weakely multiplicative.

That is if then,

The prove is simple because,

Since is multiplicative so that is .

What is where ?

Since is odd and only have even divisors we have,

Thus,

Now,

is a Mersenne prime thus,

And,

That is a geometric series whose sum is,

Thus,

Thus,

is perfect.

(The converse that an even perfect number has this form is a little bit more complicated).

Q.E.D. - Oct 20th 2006, 09:44 AMAfterShock
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. - Oct 20th 2006, 10:07 AMThePerfectHacker
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.

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.