Results 1 to 7 of 7

Math Help - composite number proof

  1. #1
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303

    composite number proof

    Q) Prove or disprove: there exist infinitely many composite numbers of the form 2^{n}-1, where n is any positive integer.

    I am not sure how to approach this. I beleive that the statement is true, but I am not sure how to approach this proof. My first thought is to do a proof by contradiction by assuming I can list all such composite number. However, I cannot find a way to arrive at a contradiction.

    Some direction would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Danneedshelp View Post
    Q) Prove or disprove: there exist infinitely many composite numbers of the form 2^{n}-1, where n is any positive integer.

    I am not sure how to approach this. I beleive that the statement is true, but I am not sure how to approach this proof. My first thought is to do a proof by contradiction by assuming I can list all such composite number. However, I cannot find a way to arrive at a contradiction.

    Some direction would be appreciated.
    Do a google search on Mersenne number. You will find a relevant theorem that makes this trivial.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Danneedshelp View Post
    Q) Prove or disprove: there exist infinitely many composite numbers of the form 2^{n}-1, where n is any positive integer.

    I am not sure how to approach this. I beleive that the statement is true, but I am not sure how to approach this proof. My first thought is to do a proof by contradiction by assuming I can list all such composite number. However, I cannot find a way to arrive at a contradiction.

    Some direction would be appreciated.
    Show  2^a-1 \mid 2^{ab}-1 .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    Quote Originally Posted by chiph588@ View Post
    Show  2^a-1 \mid 2^{ab}-1 .
    So the proof goes something like this...

    Let 2^{a}-1 be arbitrary and choose some positive integer b such that  2^a-1 \mid 2^{ab}-1 (proof of this here). Since 2^{a}-1 was arbitrary this proves there are infinitly many numbers of the form 2^{n}-1.

    ???
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Danneedshelp View Post
    So the proof goes something like this...

    Let 2^{a}-1 be arbitrary and choose some positive integer b such that  2^a-1 \mid 2^{ab}-1 (proof of this here). Since 2^{a}-1 was arbitrary this proves there are infinitly many numbers of the form 2^{n}-1.

    ???
    I think the crux of the argument should be that a composite exponent makes a composite Mersenne number, and there are infinitely many composites that you can put as exponent.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    So, the identity 2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}) with a,b>1 tells us a number of the form 2^{n}-1 is composite whenever n is composite. Since there are infinitly many composite numbers, there must be infinitly many composite numbers of the form 2^{n}-1.

    Is this sufficient? Do I need to specify the exponent n mentioned above has to be the product of two integers greater than one?

    Thanks for the help
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Danneedshelp View Post
    So, the identity 2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}) with a,b>1 tells us a number of the form 2^{n}-1 is composite whenever n is composite. Since there are infinitly many composite numbers, there must be infinitly many composite numbers of the form 2^{n}-1.

    Is this sufficient? Do I need to specify the exponent n mentioned above has to be the product of two integers greater than one?

    Thanks for the help
    I think it's sufficient, but to make it more formal, you can consider the set of positive composite integers, call it A, then consider the bijection from A -> B mapping x in A to 2^x-1 in B, and conclude that B is countably infinite. (B is a subset of the set of composite Mersenne numbers.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What's so special about this composite number
    Posted in the Number Theory Forum
    Replies: 33
    Last Post: May 5th 2010, 03:14 AM
  2. Show that this number is odd and composite
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 11th 2010, 04:12 AM
  3. rolling a composite number with one die
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 29th 2009, 02:19 PM
  4. Replies: 4
    Last Post: October 23rd 2008, 11:16 AM
  5. Composite number proof help
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 6th 2007, 11:26 AM

Search Tags


/mathhelpforum @mathhelpforum