第194回　レンガを重ねて（後編）

$ \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\UL}[1]{\underline{#1}} \newcommand{\LCM}[2]{\text{LCM}(#1,#2)} \newcommand{\GCD}[2]{\text{GCD}(#1,#2)} \newcommand{\ABS}[1]{\bigl|#1\bigr|} \newcommand{\SETL}{\bigl\{} \newcommand{\SETM}{\bigm|} \newcommand{\SETR}{\bigr\}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} $

僕「僕たちの予想はこういえる。$$ 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$を表してみよう」

ユーリ「ふんふん」

$$ \begin{align*} a{m} - b{n} &= a{M\cdot\GCD{m}{n}} - b{N\cdot\GCD{m}{n}} \\ &= (aM - bN)\cdot\GCD{m}{n} \qquad \text{$\GCD{m}{n}$でくくった} \\ \end{align*} $$

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

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

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

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

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

といえる」

ユーリ「ふむふむ……」

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