Editing Euclidean algorithm (section)

=== Extended Euclidean algorithm ===
{{Main|Extended Euclidean algorithm}}

The integers {{math|''s''}} and {{math|''t''}} of Bézout's identity can be computed efficiently using the [[extended Euclidean algorithm]]. This extension adds two recursive equations to Euclid's algorithm<ref>{{Harvnb|Rosen|2000|pp=90–93}}</ref>
: {{math|1=''s''<sub>''k''</sub> = ''s''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''s''<sub>''k''−1</sub>}}
: {{math|1=''t''<sub>''k''</sub> = ''t''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''t''<sub>''k''−1</sub>}}
with the starting values
: {{math|1=''s''<sub>−2</sub> = 1, ''t''<sub>−2</sub> = 0}}
: {{math|1=''s''<sub>−1</sub> = 0, ''t''<sub>−1</sub> = 1}}.

Using this recursion, Bézout's integers {{math|''s''}} and {{math|''t''}} are given by {{math|1=''s'' = ''s''<sub>''N''</sub>}} and {{math|1=''t'' = ''t''<sub>''N''</sub>}}, where {{math|''N'' + 1}} is the step on which the algorithm terminates with {{math|1=''r''<sub>''N''+1</sub> = 0}}.

The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step {{math|''k'' − 1}} of the algorithm; in other words, assume that
: {{math|1=''r''<sub>''j''</sub> = ''s''<sub>''j''</sub> ''a'' + ''t''<sub>''j''</sub> ''b''}}
for all {{math|''j''}} less than {{math|''k''}}. The {{math|''k''}}th step of the algorithm gives the equation
: {{math|1=''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''r''<sub>''k''−1</sub>}}.

Since the recursion formula has been assumed to be correct for {{math|''r''<sub>''k''−2</sub>}} and {{math|''r''<sub>''k''−1</sub>}}, they may be expressed in terms of the corresponding {{math|''s''}} and {{math|''t''}} variables
: {{math|1=''r''<sub>''k''</sub> = (''s''<sub>''k''−2</sub> ''a'' + ''t''<sub>''k''−2</sub> ''b'') − ''q''<sub>''k''</sub>(''s''<sub>''k''−1</sub> ''a'' + ''t''<sub>''k''−1</sub> ''b'')}}.

Rearranging this equation yields the recursion formula for step {{math|''k''}}, as required
: {{math|1=''r''<sub>''k''</sub> = ''s''<sub>''k''</sub> ''a'' + ''t''<sub>''k''</sub> ''b'' = (''s''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''s''<sub>''k''−1</sub>) ''a'' + (''t''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''t''<sub>''k''−1</sub>) ''b''}}.