拡張された互除法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 22:35 UTC 版)
「ユークリッドの互除法」の記事における「拡張された互除法」の解説
整数 m, n の最大公約数 (英: Greatest Common Divisor) を gcd(m,n) と表すときに、（拡張された）ユークリッドの互除法を用いて、mx + ny = gcd(m, n) の解となる整数 x, y の組を見つけることができる。上の例の場合、m = 1071, n = 1029 のとき、 1071 = 1 × 1029 + 42 1029 = 24 × 42 + 21 42 = 2 × 21 であるから、gcd(1071, 1029) = 21 であり、 21 = 1029 − 24 × 42 = 1029 − 24 × (1071 − 1 × 1029) = −24 × 1071 + 25 × 1029 となるので、x = −24, y = 25 である。 特に、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)} を満たす。
※この「拡張された互除法」の解説は、「ユークリッドの互除法」の解説の一部です。
「拡張された互除法」を含む「ユークリッドの互除法」の記事については、「ユークリッドの互除法」の概要を参照ください。
- 拡張された互除法のページへのリンク
