読者です 読者をやめる 読者になる 読者になる

ニ☆ウ☆ト☆ラ☆ボ

タイトルテスト中

一次不定方程式の整数解 拡張されたユークリッドの互除法

拡張されたユークリッドの互除法
一次不定方程式 \[ a x + b y = c, \quad a, b, c \in \mathbb{Z} \tag{#} \] について以下が知られています. \( d \) を \( a \) と \( b \) の最大公約数とします.
  1. (#)が整数解をもつ. \( \, \Longleftrightarrow \, \) \( c \) は \( d \) の倍数である.
  2. (#) が整数解をもつとき, その整数解が1つ得られれば, 全ての整数解が得られる.
したがって, (#)の整数解について知りたい場合, 以下のことを行います.
  1. \( a \) と \( b \) の最大公約数 \( d \) を求める. (これにより, 整数解をもつかどうか分かる.)
  2. 整数解をもつときには, \[ ax + by = d \] の整数解を1つ見付ける. (これにより, (#)の整数解も1つ見付かり, それ故, 全ての整数解が見付かる.)

この2つのステップを同時に行う方法があり, それは, 「拡張されたユークリッドの互除法」と呼ばれています. 1つ例を計算してみます:

\[ 73 x + 54 y = 2. \tag{##} \]

1.ここから始めます.

\( 73 \,x \) \( + \) \( 54 \, y \)
\( 1 \) \( 0 \)
\( 0 \) \( 1 \) \( \quad 73 \div 54\) \( = \) \( 1 \) \( \cdots \, 19 \)

右側の割り算は, 互除法の最初のステップです.

2.最下段の 0, 1 に対して, 右側の商を掛け, 上側の数を足すという計算を行います.

\( 73 \, x \) \( + \) \( 54 \, y \)
\( 1 \) \( 0 \)
\( 0 \) \( 1 \) \( \quad 73 \div 54\) \( = \) \( 1 \) \( \cdots \, 19 \)
\( 1 \) \( 1 \) \( \quad 54 \div 19 \) \( = \) \( 2 \) \( \cdots \, 16 \)

右側の割り算は, 互除法の第2ステップです.

3.同様の計算を繰り返して, 互除法の余りが 0 になったら, 終了します.

\( 73 \, x \) \( + \) \( 54 \, y \)
\( 1 \) \( 0 \)
\( 0 \) \( 1 \) \( \quad 73 \div 54\) \( = \) \( 1 \) \( \cdots \, 19 \)
\( 1 \) \( 1 \) \( \quad 54 \div 19 \) \( = \) \( 2 \) \( \cdots \, 16 \)
\( 2 \) \( 3 \) \( \quad 19 \div 16\) \( = \) \( 1 \) \( \cdots \, 3 \)
\( 3 \) \( 4 \) \( \quad 16 \div 3\) \( = \) \( 5 \) \( \cdots \, \)\( \, 1 \)
\( 17 \) \( 23 \) \( \quad 3 \div 1 \) \( = \) \( 3 \) \( \cdots \, 0 \)

最大公約数が 1 なので, 方程式 (##) は整数解をもちます.

4.符号を次のように交互に入れます.

\( 73 \, x \) \( + \) \( 54 \, y \)
\( + \) \( 1 \) \( 0 \)
\( - \) \( 0 \) \( 1 \) \( \quad 73 \div 54\) \( = \) \( 1 \) \( \cdots \, 19 \)
\( + \) \( 1 \) \( 1 \) \( \quad 54 \div 19 \) \( = \) \( 2 \) \( \cdots \, 16 \)
\( - \) \( 2 \) \( 3 \) \( \quad 19 \div 16\) \( = \) \( 1 \) \( \cdots \, 3 \)
\( + \) \( 3 \) \( 4 \) \( \quad 16 \div 3\) \( = \) \( 5 \) \( \cdots \, 1 \)
\( - \) \( 17 \) \( + \) \( 23 \) \( \quad 3 \div 1 \) \( = \) \( 3 \) \( \cdots \, 0 \)

これで, 方程式

\[ 73 x + 54 y = 1 \]

の整数解 (-17, 23) が得られました. 2 倍すると (##) の整数解 (-34, 46) が得られます.

互除法の商の列

次のようにしても, 互除法の商の列から整数解が得られます.

\( 23 \) \( + \)
\( 1 \) \( 17 \) \( - \)
\( 2 \) \( 6 \) \( + \)
\( 1 \) \( 5 \) \( - \)
\( 5 \) \( 1 \) \( + \)
\( 0 \)

計算方法の詳しい説明は, 以前の記事(上から計算しても、下から計算しても同じ。)に書いてあります.

広告を非表示にする