Diophantine Equation: ax+by=gcd(a,b)
Once you know how to solve diophantine equations with a single variable, the next step in complexity is to consider equations with two variables. The simplest such equations are linear and take the form ax+by=c. Before we solve this equation generally, we need a preliminary result. We show that you can solve the equation ax+by=GCD(a,b) by performing the Euclidean algorithm, and then reverse-substituting to arrive at a single solution.
Once you know how to solve diophantine equations with a single variable, the next step in complexity is to consider equations with two variables. The simplest such equations are linear and take the form ax+by=c. Before we solve this equation generally, we need a preliminary result. We show that you can solve the equation ax+by=GCD(a,b) by performing the Euclidean algorithm, and then reverse-substituting to arrive at a single solution.