僕:数学が好きな高校生。
ユーリ:僕のいとこの中学生。 僕のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。
僕「僕たちの予想はこういえる。$$ am - bn $$ という数式が作り出す整数のうち、 もっとも小さな正の数は、$m$と$n$の最大公約数に等しい……ってね!」
ユーリ「おおっ?」
僕「そして、きっと……
$am - bn$という整数は《$m$と$n$の最大公約数》の倍数になる
……んじゃないかな? これが、 ユーリが見つけたレンガの《ずれ》の正体だ!」
ユーリ「……盛り上がってるところ悪いんだけど、それって《予想》でしょ? 《証明》しなくちゃだめなんでしょ?」
僕「もちろん、そうだね。でもこれはすごくいい。だってね、いまから証明したいことを、シンプルな数式で書けたわけだから」
二つの整数$m$と$n$が与えられていて、$0 < m < n$とする。
$a$と$b$を任意の整数として、 $$ am - bn $$ で表される整数を考えよう。
$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$をいうだけだ!」
この続きは有料会員の方のみ
読むことができます。
cakes会員の方はここからログイン
この連載について
数学ガールの秘密ノート
数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに14巻以上も書籍化されている大人気連載です。 (毎週金曜日更新)