ツルカメトンボからの雑談 最終回

もともと、中学入試がネタ元で、「小学生に方程式を教えてもいいんじゃない？」
みたいな話を書こうと思っていたのに、全然違う方向に来てしまったので、
この話は今日でおしまい。
　
a と b の最大公約数を d としたとき、
　
　ax + by = d　　(☆)
　
は整数解を持つか、という話になっていた。
答は「持つ」。証明は、格調高く（？）イデアルの話をしたり、計算一本やりの
ユークリッドの互除法を使ったりするらしい。
本質は同じはずだが、ここでは私が勉強したり考えたことを書いてみたい。
　
まず、{ ax + by }という集合を考えてみる。
それは { ・・・, 0, a, b, a + b, 2a + b, a + 2b, 2a + 2b, ・・・ } なんてもの。
この集合を A とよぶことにしよう。
わかっていることは、
　
・集合 A は 0 を含む　（a・0 + b・0）
・集合 A は a、bを含む　（a・1 + b・0、a・0 + b・1）
・集合 A の要素は dで割れる　（aもbもdで割れるから）
　
ということである。
　
今、上の集合で正の数だけを考える。
その中で2つの数を適当に選ぶと、それらから、もっと小さい数が作れる。
それは以下のようにする。
　
たとえば、2つの数を z、z' とする。これらは
　
　am + bn = z
　am' + bn' = z'
　
のように作られた数だ。ここで、z > z' としておく。
また、z が z' の倍数だとあんまりおもしろくないので、そうではないとする。
このとき、上の式を辺々引いてみる。
　
　a(m - m') + b(n - n') = z - z'
　
当然、「 z - z' 」も集合 A の正の要素で、しかも、これは z より小さい。
しかし、z' よりは大きいかもしれない。
それなら、もう一度、これから「am' + bn' = z'」を引いてみる。すると、
　
　a(m - 2m') + b(n - 2n') = z - 2z'
　
やっぱり「 z - 2z' 」も集合 A の正の要素で、しかも、 z より小さい。
これがまだz'より大きければ、同様のことを繰り返し、ついには、z' より
小さい正の数を作ることができるだろう。
「一方が他方の倍数でない2つの数」を選んで同じような作業をやってみると、
どんどん小さな正の数を作ることができる。
　
じゃあ、どのくらい小さい数が作れるかというと、整数の範囲で考えているから、
無限に小さくはならなくて、適当に小さな正の整数になるだろう。
つまり、「 ax + by 」の形で書ける最小の正の整数があるだろうということだ。
（これは、正の整数の驚くべき性質だ。）
それを r としてみよう。
　
以下のように考えてみると、r は、集合 A のすべての要素を割り切ることがわかる。
　もし、r の倍数でない数が集合 A の中にあれば、それと r で上の作業を
　繰り返し、rより小さい正の数が作れてしまう。
　しかし、それは、「rが最小」と言ったことと矛盾してしまう。
　だから、集合 A のすべての要素は、r で割れると言える。
　
ところが、集合 A は、a、b を含んでいるので、r は a、b の公約数ということになる。
しかも、r 自身は、集合 A の要素なので、d の倍数でなければならない。
　
えーと。
r は、a と b の公約数であり、かつ、a と b の最大公約数の倍数である、と。
こんがらがって、頭をかかえてしまいそうだが、よ〜く考えると、そんなもんは、
d 自身しかない。つまり、r = d なのである。
　
以上をまとめると、（☆）は、必ず整数解を持つということになる。
（この話をよく考えると、ユークリッドの互除法で d が出せるわけもわかる。）
　
うにゃあ。疲れたので、おしまい。