 The "k"th step of the algorithm gives the equation

Since the recursion formula has been assumed to be correct for "r""k"−2 and "r""k"−1, they may be expressed in terms of the corresponding "s" and "t" variables

Rearranging this equation yields the recursion formula for step "k", as required

The integers "s" and "t" can also be found using an equivalent matrix method.The sequence of equations of Euclid's algorithm

can be written as a product of 2-by-2 quotient matrices multiplying a two-dimensional remainder vector

Let M represent the product of all the quotient matrices

This simplifies the Euclidean algorithm to the form

To express "g" as a linear sum of "a" and "b", both sides of this equation can be multiplied by the inverse of the matrix M. The determinant of M equals (−1)"N"+1, since it equals the product of the determinants of the quotient matrices, each of which is negative one.Since the determinant of M is never zero, the vector of the final remainders can be solved using the inverse of M

Since the top equation gives

the two integers of Bézout's identity are "s" = (−1)"N"+1"m"22 and "t" = (−1)"N""m"12.