# $2^n-1$ is prime or composite as $n$ is prime or composite [without using induction method] [duplicate]

I have proved this for prime $n$.

I need help to prove $2^n-1$ is composite when $n$ composite

As far I can think - suppose $2^n-1$ is composite but $n$ is prime. $\\$
Therefore, $1$ divides $$2^n-1=(2-1)(2^{n-1}+2^{n-2}+....+2+1)$$ which means $2^n-1$ is divisible by $1$ and the number itself. Hence $2^{n-1}+2^{n-2}+...+2+1>1$ and it cannot be represented as the product of its factors. Hence $2^n-1$ is prime - a contradiction, hence $n$ is composite.

Am I correct here? I need help. Any help is appreciated.

## marked as duplicate by Dietrich Burde, Community♦Mar 8 '18 at 16:33

• Your proof is wrong because you don't know the second factor is prime (and it's not). Hint: $2^{ab} = (2^a)^b$. And $2^{11} -1$ is NOT prime. Search for Mersenne prime. – Ethan Bolker Mar 8 '18 at 16:22
• I used that to prove $n$ prime, assuming $2^n-1$ prime but $n$ is composite. – thevbm Mar 8 '18 at 16:24
• $n$ prime does not imply $2^n-1$ prime ($2^{11}-1 = 23\cdot 89$, for instance). It's rather common, though, and there are specialized efficient primality tests, so it's the simplest way to search for new primes. – Arthur Mar 8 '18 at 16:24
• @Arthur, Yes that's true but if $2^n-1$ is prime that is only for prime $n$ – thevbm Mar 8 '18 at 16:25
• If $n$ is composite, then $n=ab$ for some $a,b>1$. So you need to factor $x^{ab}-1$. An obvious factor is $x^a-1$. Can you see how that works. – almagest Mar 8 '18 at 16:27
Hint Write $n=ab$ where $1<a,b<n$ and use the factorization $$(x^b-1)=(x-1)(x^{b-1}+x^{b-2}+\dotsb+1)$$ where $x=2^a$. Show that the factorization is indeed witness to $2^n-1$ being composite.
Hint: $$2^n-1=\left (2^a\right)^b-1=(2^a-1)(2^{(a-1)b}+2^{(a-2)b}+\ldots +1)$$