# 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 2n−1 is prime then n is prime.

Proof. Suppose that 2n−1 is prime, and write n=st where s,t are positive integers. Since xs−1=(x−1)(xs−1+xs−2+⋯+1) , we can substitute x=2t to see that 2t−1 is a factor of 2n−1. Since 2n−1 is prime there are only two possibilities, 2t−1=1or2t−1=2n−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 xs−1=(x−1)(xs−1+xs−2+⋯+1) 2) why is '2t−1' a factor of '2n−1' 3) how do you determine '2t−1=1or2t−1=2n−1' from 'Since 2n−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?

## marked as duplicate by user26486, user147263, Daniel W. Farlow, Claude Leibovici, KrishMar 31 '15 at 7:24

• If $\exists p,q\in\mathbb N_{\neq 1} (n=pq)$, then $2^n-1=(2^p-1)(2^{n-p}+\cdots+1)$, contradiction. – user26486 Mar 31 '15 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).
• Oh, my bad. $\mid$ represents "divides": $a\mid b$ means you can write $b = ak$, for some integer $k$. – Miguelgondu Mar 31 '15 at 3:13
• @amin It means $\frac{b}{a}$ is an integer, except for $0\mid 0$. – user26486 Mar 31 '15 at 3:16
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.