Editing Euclidean algorithm (section)

=== Linear Diophantine equations ===
[[File:Diophante Bezout.svg|thumb|alt="A diagonal line running from the upper left corner to the lower right. Fifteen circles are spaced at regular intervals along the line. Perpendicular x-y coordinate axes have their origin in the lower left corner; the line crossed the y-axis at the upper left and crosse the x-axis at the lower right."|Plot of a linear [[Diophantine equation]], {{math|1=9''x'' + 12''y'' = 483}}. The solutions are shown as blue circles.]]

[[Diophantine equation]]s are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician [[Diophantus]].<ref>{{Harvnb|Rosen|2000|pp=119–125}}</ref> A typical ''linear'' Diophantine equation seeks integers {{math|''x''}} and {{math|''y''}} such that<ref>{{Harvnb|Schroeder|2005|pp=106–107}}</ref>
: {{math|1=''ax'' + ''by'' = ''c''}}
where {{math|''a''}}, {{math|''b''}} and {{math|''c''}} are given integers. This can be written as an equation for {{math|''x''}} in [[modular arithmetic]]:
: {{math|1=''ax'' &equiv; ''c'' mod ''b''}}.

Let {{math|''g''}} be the greatest common divisor of {{math|''a''}} and {{math|''b''}}. Both terms in {{math|''ax'' + ''by''}} are divisible by {{math|''g''}}; therefore, {{math|''c''}} must also be divisible by {{math|''g''}}, or the equation has no solutions. By dividing both sides by {{math|''c''/''g''}}, the equation can be reduced to Bezout's identity
: {{math|1=''sa'' + ''tb'' = ''g''}},
where {{math|''s''}} and {{math|''t''}} can be found by the [[extended Euclidean algorithm]].<ref>{{Harvnb|Schroeder|2005|pp=108–109}}</ref> This provides one solution to the Diophantine equation, {{math|1=''x''<sub>1</sub> = ''s'' (''c''/''g'')}} and {{math|1=''y''<sub>1</sub> = ''t'' (''c''/''g'')}}.

In general, a linear Diophantine equation has no solutions, or an infinite number of solutions.<ref>{{Harvnb|Rosen|2000|pp=120–121}}</ref> To find the latter, consider two solutions, {{math|(''x''<sub>1</sub>, ''y''<sub>1</sub>)}} and {{math|(''x''<sub>2</sub>, ''y''<sub>2</sub>)}}, where
: {{math|1=''ax''<sub>1</sub> + ''by''<sub>1</sub> = ''c'' = ''ax''<sub>2</sub> + ''by''<sub>2</sub>}}
or equivalently
: {{math|1=''a''(''x''<sub>1</sub> − ''x''<sub>2</sub>) = ''b''(''y''<sub>2</sub> − ''y''<sub>1</sub>)}}.

Therefore, the smallest difference between two {{math|''x''}} solutions is {{math|''b''/''g''}}, whereas the smallest difference between two {{math|''y''}} solutions is {{math|''a''/''g''}}. Thus, the solutions may be expressed as
: {{math|1=''x'' = ''x''<sub>1</sub> − ''bu''/''g''}}
: {{math|1=''y'' = ''y''<sub>1</sub> + ''au''/''g''}}.

By allowing {{math|''u''}} to vary over all possible integers, an infinite family of solutions can be generated from a single solution {{math|(''x''<sub>1</sub>, ''y''<sub>1</sub>)}}. If the solutions are required to be ''positive'' integers {{math|(''x'' > 0, ''y'' > 0)}}, only a finite number of solutions may be possible. This restriction on the acceptable solutions allows some systems of Diophantine equations with more unknowns than equations to have a finite number of solutions;<ref>{{Harvnb|Stark|1978|p=47}}</ref> this is impossible for a [[system of linear equations]] when the solutions can be any [[real number]] (see [[Underdetermined system]]).