一次不定方程式: ユークリッドの互除法を用いた解法の改良
1. はじめに
互いに素な整数 a, b を係数に持つ一次不定方程式 ax + by = 1 を解きます。通常、ユークリッドの互除法を用いて a, b の最小公倍数を求めるための前進過程を経た後、後退代入過程によって特殊解を得ます。前進過程は効率的にすっきりした形で表されますが、後退代入過程はあまりすっきりした形になりません。本稿では、掃き出し法とユークリッドの互除法を組合せることによって、一次不定方程式の効率的かつすっきりとした解法を構成します。*1
2. ユークリッドの互除法
ユークリッドの互除法とは、2 つの整数 a, b の最大公約数を求めるための効率的なアルゴリズムです:
(1) a を b で割った商を q, 余りを r と置く。
(2) a を b の値で置き直し、b を r の値で置き直す。
(3) もし b = 0 ならば a が最大公約数である。さもなくば(1)へ戻る。
これは整数 a, b の最大公約数は b, r の最大公約数と一致するという性質に基づいています。例えば 6468, 2366 の最大公約数を求めてみましょう。商と余りの関係
a = bq + r
から
6468 = 2366×2 + 1736
2366 = 1736×1 + 630
1736 = 630×2 + 476
630 = 476×1 + 154
476 = 154×3 + 14
154 = 14×11 + 0
と変形されるので最大公約数 14 が得られます。
このように、ユークリッドの互除法を用いることによって、単純な手順を反復するだけで最大公約数を得ることができます。
3. 不定方程式: 従来法
互いに素な整数 462, 169 を係数に持つ一次不定方程式
462x + 169y = 1 ... (i)
を従来法で解いてみましょう。前進過程では、ユークリッドの互除法を用いて
462 = 169×2 + 124
169 = 124×1 + 45
124 = 45×2 + 34
45 = 34×1 + 11
34 = 11×3 + 1
と余りが 1 になるまで反復します。後退代入過程では、最後の式を 1 = 34 - 11× 3 と変形し、前式における余り 11 = 45 - 34×1, 34 = 124 - 45×2, ... を次々と代入していきます。実際
1
= 34 - 11×3 = 34 - (45 - 34×1)×3
= 45×(-3) + 34×4 = 45×(-3) + (124 - 45×2)×4
= 124×4 + 45×(-11) = 124×4 + (169 - 124×1)×(-11)
= 169×(-11) + 124×15 = 169×(-11) + (462 - 169×2)×15
= 462×15 + 169×(-41)
となり、方程式(i)の特殊解
(x, y) = (15, -41) ... (ii)
を得ます。最後に、同次方程式 462p + 169q = 0 の解 (p, q) = (169k, -462k) を特殊解(ii)に加えることで一般解
(x, y) = (169k + 15, -462k - 41) ... (iii)
が求まります(k は任意の整数)。後退代入過程は繁雑な表現になっていることが分かります。
4. 不定方程式: 本手法
本手法は連立一次方程式の解法である掃き出し法とユークリッドの互除法を組合せることによって構成されます。方程式(i)
462x + 169y = 1
を例に本手法を流れを見てみます。まず、方程式(i)の左辺に (x, y) = (1, 0), (0, 1) を代入すると、それぞれ
462×1 + 169×0 = 462
462×0 + 169×1 = 169
となります。左辺の係数 462, 169 を省略し、左側に行番号を付けて
<1> 1, 0 : 462
<2> 0, 1 : 169
と表します。そして行に関する基本変形を繰り返します。基本変形とは、ある 2 つの行を入れ替える、ある行を定数倍する、ある行に他の行の定数倍を加える、という操作です。実際、右辺の値に対してユークリッドの互除法を適用し、右辺が 1 となるまで操作を続けていくと
<1> 1, 0 : 462
<2> 0, 1 : 169
<3> 0, 2 : 338 ... <2> を 2 倍する
<4> 1, -2 : 124 ... <1> から <3> を引く
<5> -1, 3 : 45 ... <2> から <4> を引く
<6> -2, 6 : 90 ... <5> を 2 倍する
<7> 3, -8 : 34 ... <4> から <6> を引く
<8> -4, 11 : 11 ... <5> から <7> を引く
<9> -12, 33 : 33 ... <8> を 3 倍する
<10> 15, -41 : 1 ... <7> から <9> を引く
という形に掃き出されます。したがって 462×15 - 169×41 = 1 より特殊解
(x, y) = (15, -41)
が得られ、従来法の特殊解(ii)と一致することが分かります。ここで各行を求めるための操作を右側に示しました。行 <4>, <5>, <7>, <8>, <10> が従来法の前進過程に対応しているのが分かります。一般解は従来法と同様にして求められます。
従来法の手順に比べて効率的な表記になっているのが分かります。
5. まとめ
ユークリッドの互除法を用いた一次不定方程式の解法を紹介しました。連立一次方程式の解法である掃き出し法とユークリッドの互除法を組合せることにより、従来法と比べて効率的な表記を構成することができました。
今日から
数式を入力できるという噂を聞きつけて Hatena Blog にアカウントを申請しました。
さっそく、はてなブログにLaTeXで数式を書く (Markdown記法用) - 余白の書きなぐりを参考に実験をしてみたいと思います。確かに \(\int_a^b x\,dx=\frac{b^2-a^2}{2}\) や
\[A=\left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right)\]
などが入力可能です。LaTeX コマンドの途中に改行を入れると数式に変換されないなど気になる点はありますが、何とかなりそうです。
ブログの編集画面で一つ気になる点は、キー入力の反応が異常に鈍い点です。十字キーでカーソルを移動させようとしてもなかなか反応せず、動き出したかと思うと止まらず行ってしまう。これは OS やブラウザとの相性もあるのだろうか？
今後の研究にまたれる。
