第194回 レンガを重ねて(後編)

「どーして《ずれ》が最大公約数を作るの?」とユーリは疑問を口にする。初夏へ向かう季節に、やさしい整数の話を楽しもう。「整数に誘われて」シーズン第2章後編。
登場人物紹介

:数学が好きな高校生。

ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。
$ \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} $
高校生のと中学生のユーリは、 《レンガ積み》についておしゃべりしているうちに、最大公約数について考え始めた (第193回の続き)。

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

ユーリ「おおっ?」

「そして、きっと……

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

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

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

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

問題1($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会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに12巻も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 今回の証明は式だけでは足りず文章で書くことが多かった。思いつかねば無理と思えたけれど、いつもこんなことを考えていればいいのかと。確かに。 3年弱前 replyretweetfavorite

m_yas1028 今回出てきた証明は読むとなるほどと思うんだけど、自分で再現しようとしてもなかなかできない^^; 3年弱前 replyretweetfavorite

wed7931 整数問題の時点で、自分の心が半分折れるくらい苦手意識あり。さらに不等式に持ち込むことで心がほぼ完全に折れる。でも、この証明はいい練習問題ですね。 3年弱前 replyretweetfavorite

MQ_null 「テレパシーはあまり使いたくないんだけど」ってセリフ、よく分かる……でも最後には使ってしまって毎度反省 にしても、やっぱり整数問題は大変だなあ 3年弱前 replyretweetfavorite