Editing Euclidean algorithm (section)

=== Matrix method ===

The integers {{math|''s''}} and {{math|''t''}} can also be found using an equivalent [[matrix (mathematics)|matrix]] method.<ref name="Koshy_2002">{{cite book | last = Koshy | first = T. | year = 2002 | title = Elementary Number Theory with Applications | publisher = Harcourt/Academic Press | location = Burlington, MA | isbn = 0-12-421171-2 | pages = 167–169}}</ref> The sequence of equations of Euclid's algorithm
: <math>
\begin{align}
a & = q_0 b + r_0 \\
b & = q_1 r_0 + r_1 \\
& \,\,\,\vdots \\
r_{N-2} & = q_N r_{N-1} + 0
\end{align}
</math>
can be written as a product of {{math|2×2}} quotient matrices multiplying a two-dimensional remainder vector
<!--  :<math alt="A series of equations consisting of two-dimensional vectors multiplied by an ever-increasing number of 2×2 matrices. The vector a b equals the matrix q sub zero 1 1 0 times the vector b r sub zero. It also equals the matrix q sub zero 1 1 0 times the matrix q sub one 1 1 0 times the vector r sub zero r sub one. Continuing to the last step N of the algorithm, it equals the product of all 2×2 matrices of the form q sub i 1 1 0 times the vector r sub N minus one r sub N. The index i ranges from 0 to N and the last remainder r sub N is zero."> -->
: <math>
\begin{pmatrix} a \\ b \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_0 \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \end{pmatrix} =
\cdots =
\prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} \,.
</math>

Let {{math|'''M'''}} represent the product of all the quotient matrices
<!--:<math alt="The 2×2 matrix M has four components, m sub 1 1, m sub 1 2, m sub 2 1, and m sub 2 2. It is defined as the product of all 2×2 matrices of the form q sub i 1 1 0, where the index i ranges from 0 to N.">  -->
: <math>
\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} =
\prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix} \,.
</math>

This simplifies the Euclidean algorithm to the form
<!-- alt="The two-dimensional vector a b equals the matrix M times the final vector, r sub N minus one zero. The final non-zero remainder is the greatest common divisor g. Therefore, the vector a b equals the matrix M times the vector g zero."> -->
: <math> 
\begin{pmatrix} a \\ b \end{pmatrix} =
\mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} =
\mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix} \,.
</math>

To express {{math|''g''}} as a linear sum of {{math|''a''}} and {{math|''b''}}, both sides of this equation can be multiplied by the [[invertible matrix|inverse]] of the matrix {{math|'''M'''}}.<ref name="Koshy_2002" /><ref name="Bach_1996">{{cite book | last1 = Bach | first1 = E. | author1-link = Eric Bach | last2= Shallit | first2 = J. | author2-link = Jeffrey Shallit | year = 1996 | title = Algorithmic number theory | publisher = MIT Press | location = Cambridge, MA | isbn = 0-262-02405-5 | pages = 70–73}}</ref> The [[determinant]] of {{math|'''M'''}} equals {{math|(−1)<sup>''N''+1</sup>}}, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of {{math|'''M'''}} is never zero, the vector of the final remainders can be solved using the inverse of {{math|'''M'''}}
<!--  :<math alt="The two-dimensional vector g 0 equals the inverse of matrix M times the vector a b. This equals minus one to the Nth plus one power, times the matrix with components m sub 2 2, minus m sub 1 2, minus m sub 2 1, and m sub 1 1, times the vector a b.">-->
: <math>
\begin{pmatrix} g \\ 0 \end{pmatrix} =
\mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} =
(-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} \,.
</math>

Since the top equation gives
: {{math|1=''g'' = (−1)<sup>''N''+1</sup> ( ''m''<sub>22</sub> ''a'' − ''m''<sub>12</sub> ''b'')}},
the two integers of Bézout's identity are {{math|1=''s'' = (−1)<sup>''N''+1</sup>''m''<sub>22</sub>}} and {{math|1=''t'' = (−1)<sup>''N''</sup>''m''<sub>12</sub>}}. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.