Editing Euclidean algorithm (section)

=== Bézout's identity ===
{{main|Bézout's identity}}
Bézout's identity states that the greatest common divisor {{math|''g''}} of two integers {{math|''a''}} and {{math|''b''}} can be represented as a linear sum of the original two numbers {{math|''a''}} and {{math|''b''}}.<ref>{{cite book | last1 = Jones |first1=G. A. | last2 = Jones | first2 = J. M. | year = 1998 | chapter = Bezout's Identity | title = Elementary Number Theory | publisher = Springer-Verlag | location = New York | pages = 7–11}}</ref> In other words, it is always possible to find integers {{math|''s''}} and {{math|''t''}} such that {{math|1=''g'' = ''sa'' + ''tb''}}.<ref>{{Harvnb|Rosen|2000|p=81}}</ref><ref>{{Harvnb|Cohn|1980|p=104}}</ref>

The integers {{math|''s''}} and {{math|''t''}} can be calculated from the quotients {{math|''q''<sub>0</sub>}}, {{math|''q''<sub>1</sub>}}, etc. by reversing the order of equations in Euclid's algorithm.<ref>{{Harvnb|Rosen|2000|p=91}}</ref> Beginning with the next-to-last equation, {{math|''g''}} can be expressed in terms of the quotient {{math|''q''<sub>''N''−1</sub>}} and the two preceding remainders, {{math|''r''<sub>''N''−2</sub>}} and {{math|''r''<sub>''N''−3</sub>}}:
: {{math|1=''g'' = ''r''<sub>''N''−1</sub> = ''r''<sub>''N''−3</sub> − ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub>}}.

Those two remainders can be likewise expressed in terms of their quotients and preceding remainders,
: {{math|1=''r''<sub>''N''−2</sub> = ''r''<sub>''N''−4</sub> − ''q''<sub>''N''−2</sub> ''r''<sub>''N''−3</sub>}} and
: {{math|1=''r''<sub>''N''−3</sub> = ''r''<sub>''N''−5</sub> − ''q''<sub>''N''−3</sub> ''r''<sub>''N''−4</sub>}}.

Substituting these formulae for {{math|''r''<sub>''N''−2</sub>}} and {{math|''r''<sub>''N''−3</sub>}} into the first equation yields {{math|''g''}} as a linear sum of the remainders {{math|''r''<sub>''N''−4</sub>}} and {{math|''r''<sub>''N''−5</sub>}}. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers {{math|''a''}} and {{math|''b''}} are reached:
: {{math|1=''r''<sub>2</sub> = ''r''<sub>0</sub> − ''q''<sub>2</sub> ''r''<sub>1</sub>}}
: {{math|1=''r''<sub>1</sub> = ''b'' − ''q''<sub>1</sub> ''r''<sub>0</sub>}}
: {{math|1=''r''<sub>0</sub> = ''a'' − ''q''<sub>0</sub> ''b''}}.

After all the remainders {{math|''r''<sub>0</sub>}}, {{math|''r''<sub>1</sub>}}, etc. have been substituted, the final equation expresses {{math|''g''}} as a linear sum of {{math|''a''}} and {{math|''b''}}, so that {{math|1=''g'' = ''sa'' + ''tb''}}.

The Euclidean algorithm, and thus Bézout's identity, can be generalized to the context of [[Euclidean domain]]s.