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.
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 $\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.
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.
Thank you Aftershock, I made a mistake, the converse of even perfect numbers was accomplished by the great Euler.
I will. All theorem concenring infinitude are very complicated. They usually involve using Euclid's trick: assume there are finitely many.Noone has proved that there are no odd perfect numbers. On the contrary, no one has ever found one.
Another interesting thing about even perfect numbers is that they end in either 6 or 8.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.