Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

37x+10y = 1 を拡張されたユークリッドの互除法で解いてみる

37と10は違いに素なので、 37x_0 + 10y_0 = 1は整数解(x, y)を持ちます。
この解を求める方法を拡張されたユークリッドの互除法と呼ぶようです。
具体的には、 ax + by = 1の形でaをbで割った余りをaに置き換える操作を余りが0になるまで繰り返します。
 37x_0 + 10y_0 = 1
 x_0 ( 3 \cdot 10 + 7) + 10 y_0 = 1
 10 (3 x_0 + y_0) + 7 x_0 = 1
 x_1 = 3 x_0 + y_0, y_1 = x_0とおきます。
 10 x_1 + 7 y_1 = 1
 x_1 (7 + 3) + 7 y_1 = 1
 7 (x_1 + y_1) + 3 x_1 = 1
 x_2 = x_1 + y_1, y_2 = x_1とおきます。
 7 x_2 + 3 y_2 = 1
 x_2 (3 \cdot 2 + 1) + 3 y_2 = 1
 3 ( 2 x_2 + y_2) + x_2 = 1
 x_3 = 2 x_2 + y_2, y_3 = x_2とおきます。
 3 x_3 + y_3 = 1
 y_2側の係数が1になったらこの繰り返しは終了します。
なぜなら、解の一つが x_3 = 0, y_3 = 1と簡単に分かるからです。
これを逆に辿っていって x_0, y_0が求まります。
 x_2 = 1, y_2 = x_3 - 2 x_2 = -2
 x_1 = y_2 = -2, y_1 = x_2 - x_1 = 3
 x_0 = y_1 = 3, y_0 = x_1 - 3 x_0 = -11

計算の過程をみて分かる通り、2x2行列の計算を繰り返していることが分かります。

ユークリッドの互除法 - Wikipedia

発見・予想を積み重ねる ―それが整数論

発見・予想を積み重ねる ―それが整数論

プライバシーポリシー

お問い合わせ

スポンサーリンク