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, 07: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, 07:42 AMThePerfectHacker
Euler did not prove it, Euiclid did.

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

That is if $\displaystyle \gcd(a,b)=1$ then,

$\displaystyle \sigma(ab)=\sigma(a)\cdot \sigma(b)$

The prove is simple because,

$\displaystyle \sigma(n)=\sum_{d|n}d$

Since $\displaystyle f(d)=d$ is multiplicative so that is $\displaystyle \sigma$.

What is $\displaystyle \sigma(N)$ where $\displaystyle N=(2^k-1)(2^{k-1})$?

Since $\displaystyle 2^k-1$ is odd and $\displaystyle 2^{k-1}$ only have even divisors we have,

$\displaystyle \gcd(2^k-1,2^{k-1})=1$

Thus,

$\displaystyle \sigma(N)=\sigma\left( 2^k-1\right) \sigma \left(2^{k-1} \right)$

Now,

$\displaystyle 2^k-1$ is a Mersenne prime thus,

$\displaystyle \sigma(2^k-1)=2^k$

And,

$\displaystyle \sigma(2^{k-1})=1+2+2^2+...+2^{k-1}$

That is a geometric series whose sum is,

$\displaystyle 2^k-1$

Thus,

$\displaystyle \sigma(N)=2^k\cdot \left(2^k-1\right)=2N$

Thus,

$\displaystyle N$ is perfect.

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

Q.E.D. - Oct 20th 2006, 08: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, 09: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.