# Showing $2^n -1$ is composite when n is composite [duplicate]

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.

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

• Do you know the formula for $a^n-b^n$? – kingW3 Apr 16 '17 at 18:14
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.
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$ .