1. ## 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.

2. 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.

3. 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$.

4. 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$.

???

5. 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.

6. 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

7. 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.)

,

,

,

,

,

### proof of composite number

Click on a term to search for related topics.