Thread: 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.

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

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.

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.

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.

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.