# Prove if, $2^n - 1$ is prime, then $n$ is prime. [duplicate]

Prove, when $$n$$ is a positive integer, if $$2^n - 1$$ is prime, then $$n$$ is prime.

I did read some sort of proving on the web, but I could not understand it...

Any help?

And if possible, could the explanations be very clear?

Thank you guys :)

So, I've found this from somewhere:

Theorem. If $$2^n−1$$ is prime then $$n$$ is prime.

Proof. Suppose that $$2^n−1$$ is prime, and write $$n=st$$ where $$s,t$$ are positive integers. Since $$x^s−1=(x−1)(x^{s−1}+x^{s−2}+⋯+1)$$ , we can substitute $$x=2^t$$ to see that $$2^t−1$$ is a factor of $$2^n−1$$. Since $$2^n−1$$ is prime there are only two possibilities, $$2^t−1=1$$ or $$2^t−1=2^n−1$$. Therefore $$t=1$$ or $$t=n$$. We have shown that the only possible factorisations of $$n$$ are $$n×1$$ and $$1×n$$. Hence, $$n$$ is prime.

However, I have a few questions:

1. how do you know $$x^s−1=(x−1)(x^{s−1}+x^{s−2}+⋯+1)$$
2. why is$$2^t−1$$a factor of $$2^n−1$$
3. how do you determine $$2^t−1=1$$or$$2^t−1=2^n−1$$from 'Since $$2^n−1$$ is prime'
4. 'the only possible factorisations of $$n$$ are$$n×1$$ and $$1×n$$. ' how?
5. how did 'Hence, $$n$$ is prime' come out as result?
• If $\exists p,q\in\mathbb N_{\neq 1} (n=pq)$, then $2^n-1=(2^p-1)(2^{n-p}+\cdots+1)$, contradiction. Commented Mar 31, 2015 at 2:27

Hint: First, you'd need to know that $(a-b)\mid (a^n - b^n)$ for all $n\in\mathbb{N}$. Once you do that, consider the contrapositive (if $n$ is not prime, then $2^n - 1$ is not prime).

• what doess the ' ∣ ' represent?
– amin
Commented Mar 31, 2015 at 3:12
• Oh, my bad. $\mid$ represents "divides": $a\mid b$ means you can write $b = ak$, for some integer $k$. Commented Mar 31, 2015 at 3:13
• No problem :) So, a ∣ b means b/a ?
– amin
Commented Mar 31, 2015 at 3:14
• @amin It means $\frac{b}{a}$ is an integer, except for $0\mid 0$. Commented Mar 31, 2015 at 3:16
• Oh okay, thanks. And how do you write the indices... all my indices keep being corrected automatically to become as such: 2^b becomes 2b...
– amin
Commented Mar 31, 2015 at 3:27

If you know the formula for the sum of the terms of a geometric progression find the sum of first $q-1$ terms of a G.P. with first term $1$ and common ratio $2^p$, and remember that the sum is an integer.