0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ 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. $\endgroup$ – Ethan Bolker Mar 8 '18 at 16:22
  • $\begingroup$ I used that to prove $n$ prime, assuming $2^n-1$ prime but $n$ is composite. $\endgroup$ – thevbm Mar 8 '18 at 16:24
  • 1
    $\begingroup$ $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. $\endgroup$ – Arthur Mar 8 '18 at 16:24
  • $\begingroup$ @Arthur, Yes that's true but if $2^n-1$ is prime that is only for prime $n$ $\endgroup$ – thevbm Mar 8 '18 at 16:25
  • $\begingroup$ 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. $\endgroup$ – almagest Mar 8 '18 at 16:27
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Hint: $$2^n-1=\left (2^a\right)^b-1=(2^a-1)(2^{(a-1)b}+2^{(a-2)b}+\ldots +1)$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.