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.