第194回 シーズン20 エピソード4

レンガを重ねて（後編）

僕「僕たちの予想はこういえる。 $$ am - bn $$ という数式が作り出す整数のうち、 もっとも小さな正の数は、 $m$ と $n$ の最大公約数に等しい……ってね！」

ユーリ「おおっ？」

僕「そして、きっと……

　 $am - bn$ という整数は《$m$ と $n$ の最大公約数》の倍数になる

……んじゃないかな？　これが、 ユーリが見つけたレンガの《ずれ》の正体だ！」

ユーリ「……盛り上がってるところ悪いんだけど、それって《予想》でしょ？　《証明》しなくちゃだめなんでしょ？」

僕「もちろん、そうだね。でもこれはすごくいい。 だってね、いまから証明したいことを、シンプルな数式で書けたわけだから」

ユーリ「わかった！」

僕「早いな！」

ユーリ「あっ、違うの違うの。証明がわかったんじゃなくて、 この問題がいってることがわかったって言ったの」

僕「ああ」

ユーリ「《数式で表す》って意味、わかったかも！　 $am - bn$ という式見てるだけで、 レンガがチラチラ見えるし、《ずれ》もチラチラ見えるもん」

僕「それは素敵だな！」

ユーリ「チラチラ見えるのはいーけど、証明はどーすんの？」

僕「……うん、まず $am - bn$ という式をほぐしていこう。 $a,b,m,n$ はすべて整数なんだから、 $am - bn$ が整数になるのはいいよね。整数と整数を掛けた結果は整数になるし、 整数から整数を引いた結果も整数になるから」

ユーリ「そだね」

僕「$m$ と $n$ は与えられている。 $a$ と $b$ がいろんな整数値をとるとき、 $am - bn$ もいろんな整数値をとる。 正になったり、負になったり、ゼロになったりする。 そして、 $am - bn$ が《もっとも小さな正の数》になるときに注目したい……んだ」

ユーリ「うんうん。レンガの《ずれ》はいろんな数になるけど、 そのうちいちばん小さな正の数？」

僕「そういうこと。 じゃあ、まず、 $am - bn$ を別の数を使って書き換えてみようかな。 僕たちは、 $m$ と $n$ の最大公約数に関心があるから、それを使って $am - bn$ を表してみよう」

ユーリ「ほほー？　それがプロの選ぶ王道ですか」

僕「プロとかじゃないし。そうじゃなくて、とにかくいまはわかることを探っているんだよ」

ユーリ「へーい」

僕「《定義にかえれ》に従って考えると、 $m$ と $n$ の最大公約数というのは……」

ユーリ「$m$ と $n$ の最大公約数は、 $\GCD{m}{n}$ でいーんでしょ？」

僕「うん、そうだけど、 $\GCD{m}{n}$ と書くだけでは定義は見えてこないよね。 《$m$ と $n$ の最大公約数》の定義は《$m$ と $n$ の公約数のうち、最大の整数》だよね。 そして $m$ と $n$ の公約数というのは……」

ユーリ「$m$ の約数でもあるし、 $n$ の約数でもある整数？」

僕「そういうこと。その定義を念頭に置いて数式で書いてみよう。 $m$ と $n$ は、整数 $M,N$ を使って、 $$ \left\{\begin{array}{llll} m &= M\cdot\GCD{m}{n} \\ n &= N\cdot\GCD{m}{n} \\ \end{array}\right. $$ のように表せることがわかる。 $m$ と $n$ が決まれば $M$ と $N$ も決まる」

ユーリ「$M$ と $N$ ……ためらいなく文字をどんどん出してくるねー、お兄ちゃん」

僕「でもユーリはこの式は読み解けるよね」

ユーリ「だいじょーぶ。 $m$ と $n$ は $\GCD{m}{n}$ の倍数の形に書けるってことでしょ？」

僕「そうだね。そして、このとき、 $M$ と $N$ には条件が付くこともわかる？」

ユーリ「$M$ と $N$ の条件？　……あー、そだね。 $M$ と $N$ の最大公約数は $1$ になる！」

僕「その通り。そういう条件がどうして出てくるかもわかってるよね」

ユーリ「わかってる。だって、 $\GCD{m}{n}$ がぜんぶ持ってったから！　ぜんぶ……」

僕「$m$ と $n$ で共通になっている素因数が全部だね」

ユーリ「すごい！　お兄ちゃん、テレパシーだ」

僕「テレパシーはあまり使いたくないんだけどな。 ユーリの言いたいことはわかるよ。 $m = M\cdot\GCD{m}{n}$ と $n = N\cdot\GCD{m}{n}$ という形にしたとき、 $m$ と $n$ が共通に持っている素因数は《$\GCD{m}{n}$ がぜんぶ持っていった》わけだね。 $M$ と $N$ には共通の素因数は一つもない。もしも共通の素因数 $p$ があったら、 $\GCD{m}{n}$ よりも大きな公約数 $p\cdot\GCD{m}{n}$ が作れてしまうことになる。それじゃ、 $\GCD{m}{n}$ が最大の公約数だという定義に反する」

ユーリ「そーそー！　そーゆーことを言いたかったの」

僕「ともかくこれで、 $m$ と $n$ を $\GCD{m}{n}$ を使って表せた。 次に、 $m = M\cdot\GCD{m}{n}$ と $n = N\cdot\GCD{m}{n}$ を使って $am - bn$ を表してみよう」

ユーリ「ふんふん」

ユーリ「ねえお兄ちゃん。この式って、

　 $am - bn$ は $\GCD{m}{n}$ の倍数

ってことだよね？ お兄ちゃんがさっき盛り上がってたことだ！」

僕「そうだね！　 $a$ と $b$ がどんな整数であったとしても、 $$ am - bn = (aM - bN)\cdot\GCD{m}{n} $$ と表せて、しかも $aM - bN$ は整数だ。 ということは、 $a$ と $b$ がどんな整数であったとしても、

　 $am - bn$ は $\GCD{m}{n}$ の倍数

といえる」

ユーリ「ふむふむ……」

僕「うん、なかなかいいぞ。僕たちは最終的に、 $$ \REMTEXT{《$am - bn$が表す整数のうち、もっとも小さな正の数》} = \GCD{m}{n} $$ がいいたい。 $am - bn$ は $\GCD{m}{n}$ の倍数であることがわかったので、 少なくとも、 $$ \REMTEXT{《$am - bn$が表す整数のうち、もっとも小さな正の数》} = C\cdot\GCD{m}{n} $$ と書けることはわかった。 $C$ は正の整数。あとは $C = 1$ をいうだけだ！」