Results 1 to 4 of 4

Math Help - Proof on Perfect Numbers

  1. #1
    EverlastingF
    Guest

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by EverlastingF View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    Quote Originally Posted by EverlastingF View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by AfterShock View Post

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof with perfect and prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2010, 07:46 PM
  2. Perfect Numbers ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 21st 2010, 06:27 PM
  3. Perfect Numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 24th 2009, 03:47 AM
  4. Perfect Numbers
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: October 19th 2008, 03:00 PM
  5. Proof Perfect Numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 29th 2007, 01:11 PM

/mathhelpforum @mathhelpforum