TITLE: consecutive prime power
QUESTION [5 upvotes]: I'm interesting on consecutive prime power numbers. I see that there is the Mersenne primes and the Fermat Primes that give solutions and $(8,9)$. In Sloane collection it is referred on A006549 and it is written: 

David W. Wilson and Eric Rains found a simple proof that in this case of Catalan's conjecture either n or n+1 must be a power of 2 and the other number must be a prime, except for n=8.

But I can't find this proof on the web (and I don't find it myself...).
I tried the first case. I get a proof for $2^k+1=3^q$, but found it complicated. If someone has something simple?
Simple: I see that it's enough to consider the case $(2^k, q^n)$ because... ok it's clear
I see that it's enough to show that $2^k=-1$ mod $q$ or $q^2$ is impossible. But for exemple that give nothing for $2^k+1=5^q$ because $2$ is primite modulo $5$ and $25$ and so modulo all the $5^q$.

REPLY [7 votes]: There is indeed a relatively easy proof of the fact that if $n$ and $n+1$ are consecutive prime powers, then 
1) Either $n$ or $n+1$ must be a power of 2.
2) Apart from $n=8$, the other number must be a prime.
Note: Here, the proof is relatively easy because we exploit the fact that the numbers are prime powers, and not just perfect powers. The proof of the full statement of Catalan's conjecture/Mihailescu's theorem is much harder.

Proof:
1) is trivial: One of $n, n+1$ must be even, hence must a power of $2$ since it is a prime power.
2) We have two cases ($n$ even or $n+1$ even)
Case 1: $n$ even. We have $n=2^a, n+1=p^b$, $p$ an odd prime, $a, b \in \mathbb{Z}^+$. Thus $2^a=p^b-1$.
If $b$ is even, then write $b=2c$.
$$2^a=p^b-1=(p^c-1)(p^c+1)$$
$p^c \pm 1$ are two powers of $2$ which differ by $2$, so must be $2$ and $4$. Thus $n=2^a=(2)(4)=8$. (the only exception where the other number is not prime)
If $b$ is odd, then 
$$2^a=p^b-1=(p-1)(p^{b-1}+ \ldots +p+1)$$
$p^{b-1}+ \ldots +p+1 \equiv b \equiv 1 \pmod{2}$, so $p^{b-1}+ \ldots +p+1 \mid 2^a$ implies $p^{b-1}+ \ldots +p+1=1$. Thus $b=1$, so $n+1$ is a prime and we are done.
Case 2: $n$ odd. Then $n+1=2^a, n=p^b$, $p$ an odd prime, $a, b \in \mathbb{Z}^+$. Thus $2^a=p^b+1$.
If $b$ is even, then $p^b \equiv 1 \pmod{4}$. Thus $2^a=p^b+1 \equiv 2 \pmod{4}$. Therefore $a=1$, so $n+1=2^a=2$, so $n=1$, a contradiction.
If $b$ is odd, then 
$$2^a=p^b+1=(1+p)(p^{b-1}-p^{b-2}+ \ldots +p^2-p+1)$$
We have $(p^{b-1}-p^{b-2}+ \ldots +p^2-p+1) \equiv b \equiv 1 \pmod{2}$, and $(p^{b-1}-p^{b-2}+ \ldots +p^2-p+1)$ is a power of $2$, so $(p^{b-1}-p^{b-2}+ \ldots +p^2-p+1)=1$. Thus $b=1$, so $n$ is a prime and we are done.
{"set_name": "stack_exchange", "score": 5, "question_id": 735653}