Results 1 to 10 of 10

Math Help - Perfect Numbers

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    20

    Perfect Numbers

    Hey I was having a little trouble with this one problem and was wondering if you all could help me.

    I have to explain why:

    2 ^(k-1)(2 ^(k)-1) is perfect if 2 ^(k)-1 is prime.

    Any ideas on how I would start this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by BlakeRobertsonMD View Post
    Hey I was having a little trouble with this one problem and was wondering if you all could help me.

    I have to explain why:

    2 ^(k-1)(2 ^(k-1)) is perfect if 2 ^(k-1) is prime.

    Any ideas on how I would start this?
    Let \sigma (n) be the sum of divisors of n.
    It is easy to show \sigma (2^r) = 2^{r+1} - 1.
    Also \sigma (p) = p+1 if p is prime.
    Finally \sigma (ab) = \sigma (a ) \sigma (b) if \gcd(a,b)=1.

    A number of perfect if and only if \sigma (n) = 2n.
    Set n=2^{k-1} (2^k -1) and use the above results.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2008
    Posts
    20
    Thanks. I written up a proof of induction and I think I got the problem to work well. Can any of you tell me if this sounds about correct?

    Proof: 2 ^ (k 1) ( 2 ^ k 1) is always perfect when 2 ^ k - 1 is prime.
    We will use induction for this proof.
    Let P(k) be the predicate: 2^(k-1) (2 ^(k) -1).
    Base Case: Let P(2).
    2^(2-1) (2 ^ (2) -1) = 2 * 3 = 6
    As you see k = 2 lets 2 ^ k 1 become 3 which is the lowest prime number possible for this equation.
    Our answer to the equation is 6 which is a perfect number because:
    6 = 1 + 2 + 3.
    Inductive Step: Assume that P(k) is true, where k >= 2. Then P(k + 1) is also true, because:
    Using assumption we add (k+1) to the equation:
    2 ^ ((k+1)-1) * (2 ^ (k+1) 1)
    As the equation shows P(k) implies P(k+1) for every natural number k >=2.
    By Principle of induction, 2^(k 1)(2^(k)-1) is a perfect number if 2^(k) -1 is a prime number for every natural number k>=2, which proves the claim.
    How does it sound?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    That doesn't work. The statement doesn't say that it works for every k greater than or equal to 2. For example, take k = 6. 2^{6} - 1 = 63 which isn't prime. I don't quite see how you got your inductive step to work. It seems you just said 'P(k) implies P(k+1)' without actually showing it.

    Use the hints ThePerfectHacker gave you.

    \begin{array}{rcll}\sigma (n) & = & \sigma \! \bigg(2^{k-1} \left(2^k - 1\right) \bigg) & \\ & = & \sigma (2^{k-1}) \cdot \sigma (2^k - 1) & \quad \text{Since: } \text{gcd}\!\left(2^{k}-1, 2^{k-1}\right) = 1 \\ & = & (2^k - 1) \cdot 2^k & \quad \text{Since: } \sigma (2^r) = 2^{r+1} - 1 \ \text{and} \ \sigma (p) = p + 1  \\ & \vdots & & \end{array}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2008
    Posts
    20
    So is n just any natural number or what? Not really sure where n came from.

    Also I made a mistake in the first posting, 2^(k) -1 is prime, not 2^(k-1). sorry ><
    Follow Math Help Forum on Facebook and Google+

  6. #6
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    No. As TPH gave you, n = 2^{k-1} \left(2^k - 1\right).

    We have to prove that \sigma (n) = 2n since this is what it means for n to be perfect. Read through TPH's hints then the post I gave.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2008
    Posts
    20
    Okay personally I'm lost. I was never good at discrete math and I was never really good at induction either.

    I've never used the divisor function nor was I ever taught it. Usually I would think that the sum of all the divisors of a number would equal the number if it was truely perfect, not 2 * the number as shown with 2n.

    Sorry but after the hints you and the perfect hacker gave me, i'm still lost. Such as how did you go from o(2^(k-1)) * o(2^(k) - 1) to just 2^(k) -1 * 2 ^(k).

    I'm sorry if I seem slow with this.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    A number exist iff it is equal to the sum of its positive divisors excluding itself, i.e. \underbrace{\sigma (n)}_{\text{the sum of its divisors}} - \underbrace{n}_{\text{excluding itself}} = n.

    Simply moving n to the other side gives us \sigma (n) = 2n. So if n is perfect, then \sigma (n) = 2n

    To answer your questions:

    1. Why \sigma (2^{k-1}) = 2^k - 1.

    What are the divisors of 2^r? Well, there's 1, 2, 2^2, 2^3, \hdots, 2^{r-1}, 2^r. For example, 2^8 can be divided by 1, 2, 4, 8, etc. since \frac{2^8}{2^2} = 2^6, \ \frac{2^8}{2^3} = 2^5, \ \hdots

    Now, TPH said that the sum of the divisors of 2^r is 2^{r+1} - 1. In other words: 1 + 2 + 2^2 + \hdots + 2^r = 2^{r+1} - 1

    To prove this, let S = 1 + 2 + 2^2 + \hdots + 2^r and then consider S = 2S - S and you will get the desired result.

    Thus, \sigma(2^r) = 1 + 2 + 2^2 + \hdots + 2^{r-1} + 2^r = 2^{r+1} - 1. Now imagine r = k-1 and you're set.
    __________________________________________________ ____________________________________

    2. Why does \sigma (2^k - 1) = 2^k ?

    We were given that 2^k - 1 is prime. For any prime, its divisors are 1 and itself. So, the sum of its divisors is just itself plus 1, i.e. \sigma (p) = p + 1 where p is prime.

    Now put (1) and (2) together and you get what you needed.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2008
    Posts
    20
    Okay so the overall equation is 2^(2k)-(2^(k))
    Follow Math Help Forum on Facebook and Google+

  10. #10
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    No. Should be 2^{k+1} - 2^k. But that isn't the way to go.

    Factor out a 2 from 2^k and you should notice that: 2^{k} \left( 2^{k} - 1\right) = 2^1 \cdot \underbrace{ 2^{k-1}\left( 2^{k} - 1\right)}_{n} = 2n
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Perfect Numbers ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 21st 2010, 07:27 PM
  2. Perfect Numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 24th 2009, 04:47 AM
  3. Proof Perfect Numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 29th 2007, 02:11 PM
  4. Even Perfect Numbers
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2007, 05:04 PM
  5. [SOLVED] Proof on Perfect Numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 20th 2006, 10:07 AM

Search Tags


/mathhelpforum @mathhelpforum