# 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 $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.
• 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 $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.
• 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 $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$.
• Sep 7th 2010, 07:06 AM
Danneedshelp
Quote:

Originally Posted by chiph588@
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$.

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

Originally Posted by Danneedshelp
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.
• Sep 7th 2010, 06:35 PM
Danneedshelp
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
• Sep 7th 2010, 07:35 PM
undefined
Quote:

Originally Posted by Danneedshelp
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.)