ユークリッドの互除法
これらの過程において、 m = r 0 , n = r 1 {\displaystyle m=r_{0},n=r_{1}} 、ユークリッドの互除法により、 r h = gcd ( m , n ) {\displaystyle r_{h}=\gcd(m,n)} であるから、 K i − 1 = ( 0 1 1 − k i ) {\displaystyle K_{i}^{-1}={\begin{pmatrix}0&1\\1&-k_{i}\\\end{pmatrix}}} を考慮すると、
( 0 1 1 − k h − 1 ) ( 0 1 1 − k h − 2 ) . . . ( 0 1 1 − k 2 ) ( 0 1 1 − k 1 ) ( 0 1 1 − k 0 ) ( m n ) = ( gcd ( m , n ) 0 ) {\displaystyle {\begin{pmatrix}0&1\\1&-k_{h-1}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{h-2}\\\end{pmatrix}}...{\begin{pmatrix}0&1\\1&-k_{2}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{1}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{0}\\\end{pmatrix}}{\begin{pmatrix}m\\n\\\end{pmatrix}}={\begin{pmatrix}\gcd(m,n)\\0\\\end{pmatrix}}}
となる。
( x y u v ) = ( 0 1 1 − k h − 1 ) ( 0 1 1 − k h − 2 ) . . . ( 0 1 1 − k 2 ) ( 0 1 1 − k 1 ) ( 0 1 1 − k 0 ) {\displaystyle {\begin{pmatrix}x&y\\u&v\\\end{pmatrix}}={\begin{pmatrix}0&1\\1&-k_{h-1}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{h-2}\\\end{pmatrix}}...{\begin{pmatrix}0&1\\1&-k_{2}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{1}\\\end{pmatrix}}{\begin{pmatrix}0&1\\1&-k_{0}\\\end{pmatrix}}}
とおき、ユークリッドの互除法の各過程で得られた k 0 {\displaystyle k_{0}} , k 1 {\displaystyle k_{1}} , k 2 {\displaystyle k_{2}} 等を用いて、右辺を計算すれば、左辺の x {\displaystyle x} , y {\displaystyle y} が求まり、これはベズーの等式
m x + n y = gcd ( m , n ) {\displaystyle mx+ny=\gcd(m,n)}
を満たす。