# The Diophantine equation $ax+by = p^z$.

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.

• @DietrichBurde : I think I have already written above the parametrized set of all solutions to the equation. What I want is the parametrized set of the solutions that satisfy $\gcd(x,y)=1$. – LucasSilva Nov 13 '14 at 20:08
• OK, I see. Every solution of $ax+by=c=p^z$ is given by $(x,y)=((cx_0+tb)/d, (cy_0-at)/d)$, where $t$ is an integer and $(x_0,y_0)$ is a special solution. Now we have to test $gcd(x,y)=1$, right ? – Dietrich Burde Nov 13 '14 at 20:19
• @DietrichBurde : z is also a variable taking non-negative integer values. – LucasSilva Nov 13 '14 at 20:47