Clever proof of solutions to linear diophantine equation

A simple result in elementary number theory relates to the linear diophantine equation

A property of this equation (which is not proven here) is that it has infinitely many $(x,y)$ solutions if $c$ is a multiple of $\gcd(a,b)$, otherwise it has none.

The clever part is, after finding the first solution we can find the rest. Suppose there exists a solution $(x,y)$, and that $(x',y')$ is another solution:

Rearrange equation

Let $d = \gcd(a,b)$. Naturally, $a$ and $b$ are both divisible by $d$. Divide by $d$

Now, $a/d$ and $b/d$ share no common factors, therefor $a/d$ does not divide $b/d$ and $b/d$ does not divide $a/b$. Note however that $b/d$ does divide the right side of the equation, and therefor must divide the left side of the equation. Because we already determined that $b/d$ does not divide $a/d$, $b/d$ must divide $(x-x')$, thus $(x-x')$ must be a multiple of $b/d$ (likewise $(y-y')$ is a multiple of $a/d$).

State that $(x-x')$ is a multiple of $b/d$ in a new equation:

Likewise of $y$

Thus, given the initial solutions of $x,y$, the other solutions are found as:

This proof is not complete but highlights the clever trick of extracting an equation based on divisibility. It comes down to the (often subtle) fact that when $x$ divides $y$, $y=xq$.