Under which conditions is $1+p^k$ a power of $2$? So I'm trying to find conditions on $p$ and $k$ under which $1+p^k$ is a power of $2$, i.e.,
$$1+p^k=2^\ell.$$
Let's first note some facts.

*

*Obviously $\ell \geq 2.$

*If $p\equiv 1 \pmod 4,$ then $p^k\equiv 1 \pmod 4$.

*If $p\equiv 3 \pmod 4,$ then $p^k\equiv 1 \pmod 4$, when $k$ is even and $p^k\equiv 3 \pmod 4$, when $k$ is odd.

If I write this as $$1=2^\ell -p^k$$ and look at this modulo $4$, we get that
$$1\equiv -p^k \pmod 4.$$ So this is obviously possible only when $p\equiv 3 \pmod 4$ and $k$ is odd.
It turns out that the converse is not true in every such case, and I don't know how to get iff condition. Any suggestions?
 A: There's an elementary argument showing there are no solutions for $k \gt 1$ without invoking Mihăilescu's theorem (previously Catalan's conjecture).
Assume $k$ is odd, then $p+1 \mid p^k+1$. Therefore, $p+1$ is also a power of $2$, take $p+1=2^m$. Then,
$$ p \equiv -1 \pmod {2^m} $$
Now,
$$ \begin{align} \frac{p^k+1}{p+1} & = \sum_{i=0}^{k-1} (-p)^i \\ & \equiv \sum_{i=0}^{k-1} 1^i \pmod {2^m} \\ & \equiv k \pmod {2^m} \end{align}$$
Since $k$ is odd, $\frac{p^k+1}{p+1}$ is also odd, which is a power of $2$ only when it is equal to $1$. This forces $k$ to equal $1$, and the only such primes are Mersenne primes.
The case of $k$ being even is already proved in the question, and hence all possibilities have been exhausted. (Note that the above arguments also work for all odd $n \gt 1$, not just primes. The case of even $n$ is trivial).
A: By Mihăilescu's theorem there are no solutions with $k\ge 2$. For $k=1$, we obtain that $p=2^\ell-1$. Such primes $p$ are known as Mersenne primes and they are important because fast primality tests exist for numbers of the form $2^\ell-1$. In fact, the largest known prime numbers are Mersenne primes.
A necessary (but not sufficient) condition for $2^\ell-1$ to be prime is for $\ell$ to be prime, since for all $d\mid \ell$, we have $2^d-1\mid 2^\ell-1$.
