If $n$ is composite, so is $2^n-1$ [duplicate]

Possible Duplicate:
Simple Mersenne prime divisibility proofs

I'm taking elementary number theory and there is this one question that I don't know where to start at... Please help me, thanks!

Prove that if $n$ is composite, then $2^n - 1$ is composite.

Solution 1:

Let $n$ be composite. Then there exist $a$ and $b$, both greater than $1$, such that $n=ab$.

Note that $2^n-1=2^{ab}-1=(2^a)^b-1$. Let $x=2^a$. Note that $x-1$ divides $x^b-1$, for $$x^b-1=(x-1)(x^{b-1}+x^{b-2}+\cdots+1).$$

You still need to check that $2^a-1$ is a proper divisor of $2^n-1$.

Remark: If you are familiar with congruence notation, we can be more succinct. Let $m=2^a-1$. Then $2^a\equiv 1\pmod{m}$. It follows that $(2^a)^b\equiv 1\pmod{m}$, so $m$ divides $(2^a)^b-1$.

Solution 2:

Yet another way to see it: the binary representation of $2^n-1$ is $\underbrace{1\dots 1}_n$. If $n=ab$, you can divide this up as

$$\underbrace{\underbrace{1\dots 1}_a\underbrace{1\dots 1}_a\dots\underbrace{1\dots 1}_a}_b\;,$$

which represents the product of $\underbrace{1\dots 1}_a$, or $2^a-1$, with the number whose binary representation is a $1$ followed by $b-1$ blocks of the form $\underbrace{0\dots 0}_{a-1}1$.