# composite number proof

• Sep 6th 2010, 09:17 PM
Danneedshelp
composite number proof
Q) Prove or disprove: there exist infinitely many composite numbers of the form \$\displaystyle 2^{n}-1\$, where \$\displaystyle 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.
• Sep 6th 2010, 10:12 PM
undefined
Quote:

Originally Posted by Danneedshelp
Q) Prove or disprove: there exist infinitely many composite numbers of the form \$\displaystyle 2^{n}-1\$, where \$\displaystyle 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.
• Sep 6th 2010, 10:13 PM
chiph588@
Quote:

Originally Posted by Danneedshelp
Q) Prove or disprove: there exist infinitely many composite numbers of the form \$\displaystyle 2^{n}-1\$, where \$\displaystyle 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 \$\displaystyle 2^a-1 \mid 2^{ab}-1 \$.
• Sep 7th 2010, 07:06 AM
Danneedshelp
Quote:

Originally Posted by chiph588@
Show \$\displaystyle 2^a-1 \mid 2^{ab}-1 \$.

So the proof goes something like this...

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

???
• Sep 7th 2010, 07:12 AM
undefined
Quote:

Originally Posted by Danneedshelp
So the proof goes something like this...

Let \$\displaystyle 2^{a}-1\$ be arbitrary and choose some positive integer b such that \$\displaystyle 2^a-1 \mid 2^{ab}-1 \$ (proof of this here). Since \$\displaystyle 2^{a}-1\$ was arbitrary this proves there are infinitly many numbers of the form \$\displaystyle 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.
• Sep 7th 2010, 06:35 PM
Danneedshelp
So, the identity \$\displaystyle 2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a})\$ with \$\displaystyle a,b>1\$ tells us a number of the form \$\displaystyle 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 \$\displaystyle 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
• Sep 7th 2010, 07:35 PM
undefined
Quote:

Originally Posted by Danneedshelp
So, the identity \$\displaystyle 2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a})\$ with \$\displaystyle a,b>1\$ tells us a number of the form \$\displaystyle 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 \$\displaystyle 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.)