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, Namaste Jan 6 '15 at 15:17

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.


Use the contrapositive:

$2^n-1$ is composite if $n$ is composite

and observe that $2^{pq}-1$ is divisible by $2^p-1$.

  • $\begingroup$ Note that $2^{pq}-1=(2^p-1)(2^{p(q-1)}+2^{p(q-2)}+\dots +1)$ $\endgroup$ – Mark Bennet Jan 6 '15 at 14:31
  • $\begingroup$ Nice answer, +1. Why is your picture a potato? $\endgroup$ – Zubin Mukerjee Jan 6 '15 at 14:34
  • $\begingroup$ Some people use pictures of Georg Cantor or David Hilbert. I don't want to be so pretentious. Also, the potato is funny. $\endgroup$ – MJD Jan 6 '15 at 14:39

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.


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