Let $a,b \in \mathbb{Z}$ and let $p$ be a prime. Let $d = \gcd(a,b)$, and let $s$ and $t$ be integers such that $d = as+bt$.
The solutions $(x,y,z) \in \mathbb{Z} \times \mathbb{Z} \times \mathbb{Z}_{\geq 0}$ of the Diophantine equation $$ax+by = p^z$$ exist only if $d$ is a power of $p$.
Assume $d = p^c$ for some $c \in \mathbb{Z}_{\geq 0}$. Then the full set of solutions is given by \begin{align} x &= p^{m}s + \Big(\frac{b}{d}\Big)n \\ y &= p^{m}t - \Big(\frac{a}{d}\Big)n \\ z &= m + c \end{align} for all $m \in \mathbb{Z}_{\geq 0}$ and $n \in \mathbb{Z}$.
It's easy to see that every solution $(x,y,z)$ is generated by a solution $(x^{\prime},y^{\prime},z^{\prime})$ with $\gcd(x^{\prime},y^{\prime})=1$ in the sense that $(x,y,z) = (p^kx^{\prime},p^ky^{\prime},k+z^{\prime})$ for some $k \in \mathbb{Z}_{\geq 0}$.
My question is:
What is the set of all solutions $(x^{\prime},y^{\prime},z^{\prime})$ with $\gcd(x^{\prime},y^{\prime})=1$? Can the set be parametrized nicely?
EDIT: The equation can easily be reduced to one of the same shape with $a = 1$, so assuming $a = 1$ is fine.