Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

marked as duplicate by Steven Stadnicki, Gerry Myerson, Ross Millikan, William, J. M. Sep 27 '12 at 10: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.

(And abstractly a duplicate of so many other questions that it's actually hard to find them all, but...) –  Steven Stadnicki Sep 24 '12 at 23:28

2 Answers 2

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$.

share|improve this answer
wow, this is so elegant, thanks so much! –  YZH Sep 24 '12 at 23:30

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$.

share|improve this answer

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