[logo] Web連載「数学ガールの秘密ノート」
Share

第194回 シーズン20 エピソード4
レンガを重ねて(後編)

登場人物紹介

:数学が好きな高校生。

ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。

$ \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\UL}[1]{\underline{#1}} \newcommand{\LCM}[2]{\REMTEXT{LCM}(#1,#2)} \newcommand{\GCD}[2]{\REMTEXT{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 \REMTEXT{$\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}$ の倍数

といえる」

ユーリ「ふむふむ……」

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

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 435本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2017年5月12日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home