Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 24 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|improve this answer

Your Answer

 
discard

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.