  Given a prime number $q$ and a squarefree integer $C_1$, we develop a method
to explicitly determine the tuples $(y, n, \alpha)$ for which the difference
$y^n-q^\alpha$ has squarefree part equal to $C_1$. Our techniques include the
combination of the local information provided by Galois representations of
Frey-Hellegouarch curves with the effective resolution of Thue-Mahler
equations, as well as the use of improved lower bounds for $q-$adic and complex
logarithms. As an application of this methodology, we will completely resolve
the case when $1 \le C_1 \le 20$ and $ 2 \le q < 25$.
