# Can $x^{n}-1$ be prime if $x$ is not a power of $2$ and $n$ is odd?

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$.

-

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.

-
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