 This extension adds two recursive equations to Euclid's algorithm

with the starting values

Using this recursion, Bézout's integers "s" and "t" are given by "s" = "s""N" and "t" = "t""N", where "N+1" is the step on which the algorithm terminates with "r""N+1" = 0.The validity of this approach can be shown by induction.Assume that the recursion formula is correct up to step "k" − 1 of the algorithm; in other words, assume that

for all "j" less than "k".