How can I intuitively understand the algorithm for finding the integer solutions to $ax+by=c$?

Question

Recently I've started to take interest in linear diophantine equations (they play a key role in a math puzzle I stumbled upon).

I don't have a strong math background, and at first I had no clue how to solve an equation like $ax+by=c$ over the integers. After playing with it for a while I realized some things about the solutions (namely, if $(g,h)$ is a solution, then so will be $(g+b,h-a)$). However, I wasn't able to find a solution to the general case. Eventually I gave up trying on my own and started researching (including here on math.se) for how to solve diophantine equations (I became acquainted with the terminology in this step).

I've learned two things:

• For an equation like this to have integer solutions, $c$ must be divisible by $gcd(a,b)$.
• Provided the solutions exist, there exists an algorithm to find them, and it has a connection with Euclid's algorithm for finding the greatest common divisor of two numbers.

As it is now, I'm able to tell if an equation like this has integer solutions and I'm even able to execute the steps needed to find all of its solutions. For all it matters, I can solve linear diophantine equations in two variables.

However, I really would like to know why those two things are true, and moreover, what is the connection between Euclid's algorithm and the algorithm for finding the roots (I can see the similarity in the coefficients involved, but I feel like there's a more meaningful reason for the connection, a reason which I didn't yet fully grasped).

So I guess the question is:

How can I intuitively understand the algorithm for finding the integer solutions to $ax+by=c$?

---

I hope I made myself clear. If more clarification is needed, please ask. Thank's in advance.

Answer 1

A request for "intuitive understanding" is always tricky, but see if this helps.

For simplicity of explanation we shall assume that $a,b$ are positive integers with no common factor - it's not too hard to amend things so as to cover other cases. Looking at the equation $$ax+by=c\ ,$$ we might have the idea that this would be very easy to solve if $a$ were small. For example, in the extreme case, if $a=1$ then we have $x+by=c$ and the solution is clearly $$y=\langle\hbox{anything}\rangle\ ,\quad x=c-by\ .$$ If $a=2$ it's not too much harder: $b$ must be odd, so we choose $y$ to be the same parity (odd or even) as $c$ and then take $$x=\frac{c-by}{2}\ .$$

So we could then think: is there any way to rearrange the original equation in such a way that $a$ is reduced? Well, if we split $a$ into a multiple of $b$ plus a remainder, then the multiple of $b$ in the term $ax$ could be included with the $by$ term. That's probably pretty confusing in words, hopefully it's easier in symbols: if $$a=bq+r$$ then the equation becomes $(bq+r)x+by=c$, that is, $$b(qx+y)+rx=c\ .$$ If we can solve this to find values for our "new variables" $qx+y$ and $x$, then we easily get the values of $x$ and $y$. If $b$ and $r$ are still too big to solve easily, we can repeat the procedure, writing $b$ as a multiple of $r$ plus another remainder, $$b=q'r+r'\ .$$ I expect you can see that we have just computed the second step of a Euclidean algorith which started with $a$ and $b$, and perhaps this is sufficient to explain the connection.

Hope this helps!