  We develop machinery to explicitly determine, in many instances, when the
difference $x^2-y^n$ is divisible only by powers of a given fixed prime. This
combines a wide variety of techniques from Diophantine approximation (bounds
for linear forms in logarithms, both archimedean and non-archimedean, lattice
basis reduction, methods for solving Thue-Mahler and $S$-unit equations, and
the Primitive Divisor Theorem of Bilu, Hanrot and Voutier) and classical
Algebraic Number Theory, with results derived from the modularity of Galois
representations attached to Frey-Hellegoaurch elliptic curves. By way of
example, we completely solve the equation \[ x^2+q^\alpha = y^n, \] where $2
\leq q < 100$ is prime, and $x, y, \alpha$ and $n$ are integers with $n \geq 3$
and $\gcd (x,y)=1$.
