Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Are there any solutions to $x^{n}-1=p$ with p prime, integers $x,n>1$ and $x$ not a power of $2$?

$x$ must be even. $n$ is odd since if $n=2m$ then $p=x^{n}-1=(x^{m}+1)(x^{m}-1)$ hence $p=x^{m}+1$ and $1=x^{m}-1$, which has solution $p=3$ given by $x=2^{2}$.

This generalises; for any solution to $x^{n}-c^{2}=p$, $n$ must be odd. And for any solution to $x^{n}-c=p$, $x$ is odd iff $c$ is odd unless $p=2$ and, if $a$ divides $c$ and $p$ does not divide $c$ then $x$ divides $c$.

share|cite|improve this question
up vote 27 down vote accepted

The following result can be found in most introductions to Number Theory.

Theorem: Let $x$ and $n$ be integers greater than $1$. If $x^n-1$ is prime, then $x=2$ and $n$ is prime.

Proof: Note that $x-1$ divides $x^n-1$, for $$x^n-1=(x-1)(x^{n-1}+x^{n-2}+ \cdots + 1).$$ If $x>2$ and $n>1$, each of the above factors of $x^n-1$ is $>1$. It follows that if $x>2$ and $n>1$, then $x^n-1$ cannot be prime. So if $x^n-1$ is prime, then $x=2$.

Next we show that if $2^n-1$ is prime, then $n$ itself must be prime. For suppose to the contrary that $n=ab$ where $a$ and $b$ are greater than $1$. Then $$2^n-1=2^{ab}-1=(2^a)^b-1.$$ Let $y=2^a$. Then $2^n-1=y^b-1$. But $y-1$ divides $y^b-1$. Thus $2^a-1$ divides $2^n-1$. It is easy to see that in fact $2^a-1$ is a proper divisor of $2^n-1$, so $2^n-1$ cannot be prime.

This concludes the proof. By calculating, we can verify that $2^n-1$ is prime for $n=2$, $3$, $5$, and $7$. But one should not jump to conclusions. When $n=11$, $2^n-1$ is not prime, for $23$ divides $2^{11}$.

Primes of the form $2^n-1$ (where $n$ is necessarily prime) are called Mersenne primes.

There has been interest in what would later be called Mersenne primes ever since the time of Euclid, because of their connection with the even perfect numbers. Despite a search spanning millenia, only $47$ Mersenne primes are currently known. The current record holder is $2^{43,112,609}-1$. From the computational evidence, it appears that for "most" primes $p$, the number $2^p-1$ is not prime. It is not known whether there are infinitely many Mersenne primes.

share|cite|improve this answer
Is there a proof that if $X>2$ then $X^n-1$ cannot be prime? – michaelmross Jun 12 at 21:26
@michaelmross: Sure, for $n\gt 1$. We have $x^n-1=(x-1)(x^{n-1}+x^{n-2}+\cdots +1)$, and each factor on the right is $\ge 2$. – André Nicolas Jun 12 at 21:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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