# How to prove that $n$ is a prime if $2^n-1$ is a prime [duplicate]

I got this by watching a video on youtube and they said that this is always true but I am wondering why. I have tried to use Fermat's little theorem (FLT) but got nowhere bcs it says that if p is a prime then $p|{a^p-a}$.

## marked as duplicate by Jonas Meyer, MJD, Michael Grant, Davide Giraudo, NamasteJan 6 '15 at 15:17

$2^n-1$ is composite if $n$ is composite
and observe that $2^{pq}-1$ is divisible by $2^p-1$.
• Note that $2^{pq}-1=(2^p-1)(2^{p(q-1)}+2^{p(q-2)}+\dots +1)$ – Mark Bennet Jan 6 '15 at 14:31
Here's an elementary proof. Assume $n$ is not prime. Then $n=p \cdot q$ for some integers $p$ and $q$ such that $p \leq q$ and $p \neq 1$. Then $$2^n-1=(2^q)^p-1$$ factorizing that $$(2^q)^p-1^p=(2^q-1)((2^q)^{p-1}+ \cdots + 1)$$ Since $q \neq 1$, we have obtained factors for $2^n-1$ which shouldn't have been possible if it was prime, hence we have a contradiction.