【Webサイト】 ・マルコフ過程 ? wikipedia ・確率過程 ? wikipedia ・確率分布 ? wikipedia ・条件付き確率 ? wikipedia ・マルコフ性 ? wikipedia ・隠れマルコフモデル ? wikipedia ・マルコフ連鎖の話 ・マルコフ連鎖モンテカルロ法入門-１ ・隠れマルコフモデルの大雑把な解説 ・隠れマルコフモデルによる音声認識と音声合成
特に、m, n が互いに素（最大公約数が 1）である場合、mx + ny = 1 の整数解を (x, y) とすると、mx + ny = c は任意の整数 c に対して整数解 (cx, cy) をもつことが分かる。
一般に、 m = r 0 , n = r 1 {\displaystyle m=r_{0},n=r_{1}} において、ユークリッドの互除法の各過程を繰り返して
r 0 = k 0 r 1 + r 2 ( 0 < r 2 < r 1 ) {\displaystyle r_{0}=k_{0}r_{1}+r_{2}\ \ (0<r_{2}<r_{1})}
r 1 = k 1 r 2 + r 3 ( 0 < r 3 < r 2 ) {\displaystyle r_{1}=k_{1}r_{2}+r_{3}\ \ (0<r_{3}<r_{2})}
r 2 = k 2 r 3 + r 4 ( 0 < r 4 < r 3 ) {\displaystyle r_{2}=k_{2}r_{3}+r_{4}\ \ (0<r_{4}<r_{3})}
. . . {\displaystyle ...}
r h − 1 = k h − 1 r h + 0 {\displaystyle r_{h-1}=k_{h-1}r_{h}+0}
が得られるとき、
( r 0 r 1 ) = ( k 0 1 1 0 ) ( r 1 r 2 ) {\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\\end{pmatrix}}={\begin{pmatrix}k_{0}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{1}\\r_{2}\\\end{pmatrix}}}
( r 1 r 2 ) = ( k 1 1 1 0 ) ( r 2 r 3 ) {\displaystyle {\begin{pmatrix}r_{1}\\r_{2}\\\end{pmatrix}}={\begin{pmatrix}k_{1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{2}\\r_{3}\\\end{pmatrix}}}
( r 2 r 3 ) = ( k 2 1 1 0 ) ( r 3 r 4 ) {\displaystyle {\begin{pmatrix}r_{2}\\r_{3}\\\end{pmatrix}}={\begin{pmatrix}k_{2}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{3}\\r_{4}\\\end{pmatrix}}}
. . . {\displaystyle ...}
( r h − 1 r h ) = ( k h − 1 1 1 0 ) ( r h 0 ) {\displaystyle {\begin{pmatrix}r_{h-1}\\r_{h}\\\end{pmatrix}}={\begin{pmatrix}k_{h-1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{h}\\0\\\end{pmatrix}}}
すなわち
( r 0 r 1 ) = ( k 0 1 1 0 ) ( k 1 1 1 0 ) ( k 2 1 1 0 ) ( k 3 1 1 0 ) . . . ( k h − 1 1 1 0 ) ( r h 0 ) {\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\\end{pmatrix}}={\begin{pmatrix}k_{0}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}k_{1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}k_{2}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}k_{3}&1\\1&0\\\end{pmatrix}}...{\begin{pmatrix}k_{h-1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{h}\\0\\\end{pmatrix}}}
ここで
K i = ( k i 1 1 0 ) {\displaystyle K_{i}={\begin{pmatrix}k_{i}&1\\1&0\\\end{pmatrix}}} とおくと、 | K i | = − 1 {\displaystyle |K_{i}|=-1} であるから K i − 1 {\displaystyle K_{i}^{-1}}は存在して
( k h − 1 1 1 0 ) − 1 ( k h − 2 1 1 0 ) − 1 . . . ( k 2 1 1 0 ) − 1 ( k 1 1 1 0 ) − 1 ( k 0 1 1 0 ) − 1 ( r 0 r 1 ) = ( r h 0 ) {\displaystyle {\begin{pmatrix}k_{h-1}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{h-2}&1\\1&0\\\end{pmatrix}}^{-1}...{\begin{pmatrix}k_{2}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{1}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{0}&1\\1&0\\\end{pmatrix}}^{-1}{\begin{pmatrix}r_{0}\\r_{1}\\\end{pmatrix}}={\begin{pmatrix}r_{h}\\0\\\end{pmatrix}}}
これらの過程において、 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)}
ジジイがあれこれ考えた 