A linear Diophantine equation (in two variables) is an equation of the general form

(1) |

(2) |

(3) | |||

(4) | |||

(5) | |||

(6) |

Starting from the bottom gives

(7) | |||

(8) |

so

(9) |

Continue this procedure all the way back to the top.

Take as an example the equation

(10) |

The solution is therefore , . The above procedure can be simplified by noting that the two left-most columns are offset by one entry and alternate signs, as they must since

(11) | |||

(12) | |||

(13) |

so the Coefficients of and are the same and

(14) |

and we recover the above solution.

Call the solutions to

(15) |

equation | ||

In fact, the solution to the equation

(16) |

(17) |

(18) | |||

(19) |

with an arbitrary Integer. The solution in terms of smallest Positive Integers is given by choosing an appropriate .

Now consider the general first-order equation of the form

(20) |

(21) |

(22) |

(23) |

**References**

Courant, R. and Robbins, H. ``Continued Fractions. Diophantine Equations.'' §2.4 in Supplement to Ch. 1 in
*What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed.*
Oxford, England: Oxford University Press, pp. 49-51, 1996.

Dickson, L. E. ``Linear Diophantine Equations and Congruences.'' Ch. 2 in
*History of the Theory of Numbers, Vol. 2: Diophantine Analysis.* New York: Chelsea, pp. 41-99, 1952.

Olds, C. D. Ch. 2 in *Continued Fractions.* New York: Random House, 1963.

© 1996-9

1999-05-24