第1回のまくらに、映画『シン・シティ』を出したけど（ブルース・ウィリスが出てたから）、あのなかでアメコミっぽく（って、原作はコミック）ガタイのいいオッサンはミッキー・ロークだったんだよね。彼は僕と同年代で、昔、ネコパンチで笑いものにされたけど、よく頑張っているよな。スターウォーズのクリストファー・リーはさらにスゲーけんど（とんでもなくスゲー）。
それはともかく、“『ダイハード3』に出てきたクイズ＝升で水を量る問題”の話に戻ります。方程式で書くなら、「4n + 7m = 9」を満たす整数n, mを求める問題です。
内容
- また言い訳したりして
- 割り算の原理
- ユークリッド互除法
- 「an + bn = g」の一般的な解法
- まとめと予告
●また言い訳したりして
今回もイデアルの定義が出てきません。ダハハハハ。
僕は、整数のイデアルがイデアルの典型例／教育的例だとは思ってないけど、しかしそれでも、整数のイデアルの初等的性質を知っておくのは有意義だろうとは思ってます。で、整数の話からはじめたのだけど、整数のイデアルを調べるには、整数固有の（初等整数論的）性質がどうしても必要になってしまうのですよ。
必要な性質とは、「“余り付き割り算”がうまく定義できる」ってことです。この性質を持つことは「ユークリッド的」という形容詞で表現するのが適切でしょう、その理由はこのエントリーで書きます。
で、まー、結局、今回は“余り付き割り算”の話ですがね。
●割り算の原理
『ダイハード3』のクイズを一般化すると、整数定数a, b, cに対して、「an + bm = c」を満たす整数n, mを求める問題。特に、a=4, b=7, c=9の具体的ケースが『ダイハード』のクイズ -- とはいっても、映画のなかでの正確な量は憶えてないけど。
この問題の一般的な構造、背景、メカニズムを理解するには、イデアルを導入するのがいいのだけど、具体的な問題を具体的に（実効的に）解くには、抽象的な構造論だけではたいていダメで、なんか具体的な手法が必要なんだよね。『ダイハード』のクイズの場合の具体的な手法とは、整数の割り算です。
正の整数 x, y のあいだで割り算ができる背景には、次の事実があります。
- x = q・y + r, 0≦ r ＜y となる整数qとrが存在する。
qが商でrが余りですね。小学校では、この事実を次のように書くのでした。
- x÷y = q 余り r
大小関係に対しては特に条件を付けません。例えば、「3÷5 = 0 余り 3」でもOK。さらに正の整数という条件もはずすと、次のようになります。
- y≠0なら、x = q・y + r, |r|＜|y| となる整数qとrが存在する。
これだと負の整数も許しますが、商qと余りrが一意的に確定はしなくなります。例えば「-10÷4 = -3 余り 2」、「-10÷4 = -2 余り -2」。ですが、この形のほうが一般化しやすいので、これをユークリッドの割り算原理と呼んでおきましょう。わざわざユークリッド（Euclid）を冠したのは、この原理（公理）を満たす環（正確には整域）を、歴史的な事情からユークリッド環と呼ぶからです。
●ユークリッド互除法
ユークリッド互除法とは、整数xとyの最大公約数（GCD）を実効的に求めるアルゴリズムです。このアルゴリズムを支えているのは、ユークリッドの割り算原理なので、割り算原理が確認できれば互除法アルゴリズムが適用できます。
ユークリッド互除法はとても有名で、プログラミングの例題にもしょっちゅう取り上げられているので説明しません（他で情報を探してください）。ここでは、特殊なケース -- 『ダイハード』のクイズに互除法を適用します。
「4n + 7m = 9」の代わりに「4n + 7m = 1」を考えます。つまり、4リットルと7リットルの升で1リットルを量りたい。効率（升を使う回数）をまったく無視すれば、1リットルを9回量って9リットルを得られますから、「4n + 7m = 1」が解ければ「4n + 7m = 9」だって大丈夫。（『ダイハード」の状況では、こんな悠長な量り方はやってられませんけどね、タイムアウトがありますから。）
互除法は次のように進行します。
- 7÷4 = 1 余り 3
- 4÷3 = 1 余り 1
- 3÷1 = 3 余り 0 （おしまい）
同じことを次のように書き換えます。各箇条の先頭に割り算をする2数を示してます。
- [7, 4] 7 = 1・4 + 3
- [4, 3] 4 = 1・3 + 1
- [3, 1] 3 = 3・1 + 0 （おしまい）
実は、この手順から「4n + 7m = 1」を満たすn, mが求まります。それを見るため、さらに書き換えます。
- [7, 4] 3 = 7 - 1・4
- [4, 3] 1 = 4 - 1・3
- [3, 1] 0 = 3 - 3・1 （おしまい）
2番目の 1 = 4 - 1・3 の3を 3 = 7 - 1・4 を使って置き換えると、
1 = 4 - 1・(7 - 1・4) = 2・4 + (-1)・7 です。
これはつまり、n=2, m=-1が「4n + 7m = 1」を満たすn, mであることを示しています。
●「an + bn = g」の一般的な解法
ユークリッド互除法は、何度か割り算を繰り返して最大公約数を求めるアルゴリズムです。このアルゴリズムがほんとに最大公約数を与えること（アルゴリズムの正当性）が保証されるているなら、その副産物として、g = GCD(a, b)だとして「an + bm = g」を満たすn, mも与えます。
4, 7より大きな数a=351, b=286のケースでやってみましょう。
- [351, 286] 351÷286 = 1 余り 65
- [286, 65] 286÷ 65 = 4 余り 26
- [65, 26] 65÷ 26 = 2 余り 13
- [26, 13] 26÷ 13 = 2 余り 0
これから、13が最大公約数だとわかりますが、同時に次の等式群が得られます。
- [351, 286] 65 = 351 - 1・286
- [286, 65] 26 = 286 - 4・65
- [65, 26] 13 = 65 - 2・26
- [26, 13] 0 = 26 - 2・13
下から2番目からはじめて代入を繰り返すと：
13 = 65 - 2・26
= 65 - 2・(286 - 4・65)
= (351 - 1・286) - 2・(286 - 4・(351 - 1・286))
最後の形は (a - b) - 2(b - 4(a - b)) と書いたほうが見やすいでしょう。中学校で習った計算をすると、9a - 11b 。つまり、9・351 + (-11)・286 = 13 というわけで、「351・n + 286・m = 13」が「n=9, m=-11」と解けました。
●まとめと予告
ユークリッド互除法が最大公約数（GCD）を確かに求めるという仮定のもとで、g = GCD(a, b) に対する「an + bm = g」の解n, mを実効的に求めることができます。
で、問題になるのは、ユークリッド互除法がほんとに最大公約数を与えているかどうかです。このことは何の道具なしでも示せますが、次回、イデアルを使って示す予定です。イデアルを使うのは大げさな感じもしますが、方程式「an + bm = c」の姿を描き出すには有効です。
というわけで、次回でやっと「イデアル登場」となるでしょう。
