# What prime powers differ by one

I thought this would be a hard problem but I found a link that seems to ask the answer to this question as a homework problem? Can somone help me out here, are there an infinite number of prime powers that differ by 1? or are there a finite number of them? If so which are they?

-
You mean like $\,|2^5-31^1|=1\,,\,|2^4-17^1|=1\,,...$ , or ...what happens with prime powers of odd primes? – DonAntonio Nov 14 '12 at 3:28
If we count a prime itself as a prime power, then the answer is not known, since it is not known whether there are infinitely many Fermat primes. If we are looking at powers $\ge 2$, everything is known. – André Nicolas Nov 14 '12 at 3:29

## 3 Answers

Catalan's Conjecture, a theorem since $2002$, shows that the only examples where the exponents are $\ge 2$ are $3^2-2^3$.

If we allow exponent equal to $1$, the answer is not known. Perhaps there are infinitely many Fermat primes, that is, primes of the form $2^n+1$ (it turns out that for $2^n+1$ to be prime, we need $n$ to have shape $2^k$).

For many years, only five such primes have been known. There may not be others, or there may be finitely many others, or infinitely many. At the current time, we do not know.

-
It is probably possible to settle $2^r-p^s=\pm1$, $p$ prime, $s\ge2$, by elementary means, in particular, without invoking the proof of Catalan. – Gerry Myerson Nov 14 '12 at 3:44

Finally, I know why this problem is elementary.

$p^r-q^s=1$ where $p$, $q$ are primes, and $r$, $s$ are integers greater than $1$.

If $p$ and $q$ are both odd primes, then $p^r$ and $q^s$ are both odd, then $p^r-q^s$ can only be even. So, either $p$ or $q$ is a even prime, that is $2$.

It seems the problem becomes elementary when $p=2$ or $q=2$. In the following, we will prove the claim when $p=2$ or $q=2$. It is not important whether the other is prime or not.

Case 1. $p=2$, that is $q^s=2^r-1$.

$2^r-1$ is a $4k-1$ type number, so $q^s$ has to be $4k-1$ type.

For an odd number $q$, there are two choices: $4k+1$ type or $4k-1$ type.

For $4k+1$ type numbers, any power is $4k+1$ type.

For $4k-1$ type numbers, odd power is $4k-1$ type, even power is $4k+1$ type.

So, $q$ has to be $4k-1$ type, and $s$ has to be odd.

$2^r=q^s+1=(q+1)(q^{s-1}-q^{s-2}+\cdots-q+1)$

Notice that $q^{s-1}-q^{s-2}+\cdots-q+1$ has odd number of terms and each term is odd, so it is an odd number, which contradicts that $2^r$ only has factor $2$.

Case 2. $q=2$, that is $p^r=2^s+1$.

$2^s+1$ is a $4k+1$ type number, so:

If $p$ is $4k-1$ type, $r$ has to be even.

If $p$ is $4k+1$ type, $r$ can be even or odd.

Case 2.1. $p$ is $4k-1$ type, and $r=2m$ is even.

$2^s=p^{2m}-1=(p^m+1)(p^m-1)$

$p^m-1$ is $4k-2$ type. If it only has factor $2$, it has to be $p^m-1=2$, and then we obtain the only solution in this case: $3^2-2^3=1$.

Case 2.2. $p$ is $4k+1$ type, and $r=2m$ is even.

$2^s=p^{2m}-1=(p^m+1)(p^m-1)$

$p^m+1$ is $4k+2$ type. If it only has factor $2$, it has to be $p^m+1=2$, which has no solution.

Case 2.3. $p$ is $4k+1$ type, and $r$ is odd.

$2^s=p^r-1=(p-1)(p^{r-1}+p^{r-2}+\cdots+p+1)$

Notice that $p^{r-1}+p^{r-2}+\cdots+p+1$ has odd number of terms and each term is odd, so it is an odd number, which contradicts that $2^s$ only has factor $2$.

-

In number theory, Mihailescu theorem is the solution to a famous and old conjecture formulated by French mathematician Eugene Charles Catalan in $1844$ (see "Note extraite d'une lettre adressè à l'èditeur). Although it was proved in April $2002$, it appeared for first time in Crelle's Jounal in $2004$. His formulation is really easy: there is a unique couple of powers of natural numbers such that they differ by $1$. Formally:

If $x,y,p,q$ are integers greater than $1$ and $x^p-y^q=1$ then $x=q=3$ and $y=p=2$.

If someone is really interested in a complete proof, then it can be found in Catalan's Conjecture, Springer, 2007. Otherwise, I can assure that some highlight cases can be completely solved with elementary tools (I actually made a .pdf file collecting these proof, if needed I will attach it here):

• Case $2\mid q$;

• Case $2\mid p$;

• Case $x=q$ (completely solved by myself, actually I cannot find references about it);

• Case $y\mid x-1$ (some its corollaries are still used as olympid problems).

With regard to the original question, we missed only the case that a prime $p$ is in the form $q^m \pm 1$ for some prime $q$ and positive integer $m$. Avoiding trivial cases, if $q$ is odd then $2\mid q^m\pm 1$, i.e. $p$ must be in the form $2^m \pm 1$. If a prime $p$ is in the form $2^m-1$ then it's defined "Mersenne prime", if a prime is in the form $2^{2^k}+1$ then it's defined "Fermat prime".

The fact is that, up to now, it's still unknows if one or both those set of primes are not finite.

-