1
$\begingroup$

This question already has an answer here:

I'd like to show that if $n$ is a composite number, then so is $2^n-1$.

When $n$ is an even number, this is simple. Let $n$ = 2k. Then, $2^n -1 = (2^k)^2- 1 = (2^k -1)(2^k + 1)$.

For the case where $3|n$, this is also not too hard. For $n = 6$, we have $2^6 -1 = 63 = 7 \cdot 9$.

Assume $7|(2^{3k} -1)$. Then, $2^{3(k +1)} -1 = 7\cdot2^{3k} + (2^{3k} -1) $ which is divisible by 7. So, we can show that this case also leads to a composite number via induction.

However, I can't seem to generalize it for an arbitrary $n$. Any hints to the right direction is much appreciated.

$\endgroup$

marked as duplicate by Dietrich Burde, Community Apr 16 '17 at 19:21

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.

  • $\begingroup$ Do you know the formula for $a^n-b^n$? $\endgroup$ – kingW3 Apr 16 '17 at 18:14
2
$\begingroup$

Suppose, $n=ab$ with $a,b>1$. Then $2^n-1=(2^a)^b-1$

With $u:=2^a$ we get $$2^n-1=u^b-1=(u-1)(u^{b-1}+\cdots +1)$$

Since $u\ge 4$ and $u^{b-1}\ge u\ge 4$ , both factors are greater than $1$, so $2^n-1$ is composite.

$\endgroup$
1
$\begingroup$

One approach is to let $n = 2^k-1$ Then $2^k=1$ (mod n) => $(2^k)^l=1$ (mod n) so that $n$ divides $(2^k)^l-1$ .

$\endgroup$

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