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

第195回 シーズン20 エピソード5
ユークリッドの互除法(前編)

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。好奇心旺盛で根気強い《元気少女》。

リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

$ \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\UL}[1]{\underline{#1}} \newcommand{\LCM}[2]{\REMTEXT{LCM}(#1,#2)} \newcommand{\gcdmath}[2]{\REMTEXT{gcd}(#1,#2)} \newcommand{\GCD}[2]{\REMTEXT{GCD}(#1,#2)} \newcommand{\XGCD}[2]{\REMTEXT{XGCD}(#1,#2)} \newcommand{\EUCLID}[2]{\REMTEXT{EUCLID}(#1,#2)} \newcommand{\ABS}[1]{\bigl|#1\bigr|} \newcommand{\SETL}{\bigl\{} \newcommand{\SETM}{\bigm|} \newcommand{\SETR}{\bigr\}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} $

アルゴリズムクイズ!

放課後。が高校の図書室に行くと、 テトラちゃんリサがおしゃべりをしていた。 といっても主に「しゃべって」いるのはテトラちゃんの方だけれど。

テトラ「あ、先輩! 先輩もいっしょに考えましょうよ」

「何の話?」

テトラ「リサちゃんが、クイズを出しているんです。 アルゴリズムクイズです!」

リサ「《ちゃん》は不要」

真っ赤な髪のリサはコンピュータ少女。 彼女はいつも、真っ赤なノートブック・コンピュータを持ち歩き、 すばやく無音でタイピングする。

「へえ……」

問題1

このアルゴリズムは正しく最大公約数を計算するか。

入力

  • 正の整数 $m, n$
出力
  • $m$ と $n$ の最大公約数
手続き

テトラ「あたしはこの問題1、もう答えたんですが、 先輩も考えてみてください!」

後輩の数学ガール二人に見つめられた状態で問題を考えるというのは、 それは、なかなか、光栄なのか、恐怖なのか。

「《例示は理解の試金石》ということで、 $m,n$ に適当な数をいれて試してみれば、 手がかりがつかめると思うけど……」

テトラ「あっ、あっ、それはそうなんですが、 クイズなので、まずは頭だけで考えてくださいよう!」

「……それじゃ、いちおうこのアルゴリズムの表記法だけ確認させてよ。 これは $\GCD{m}{n}$ という手続きで、 $m$ と $n$ が与えられているんだよね?」

リサ「$m,n$ は入力」

「もしも $m < n$ ならば、 $\GCD{m}{n - m}$ を計算した結果を答えとする?」

リサ「それが出力」

「もしも $m > n$ ならば、 $\GCD{m - n}{n}$ を計算した結果を答え……出力とする」

リサ「場合分け」

「どちらでもなければ、 $n$ を出力とする」

テトラ「読み方はそれで大丈夫です! どうですか、先輩!」

「……」

は頭の中でそっと考える。 やはり《小さな数で確かめる》のが基本だな。 たとえば、 $m = 4, n = 6$ で考えてみよう。

G1: $\GCD{4}{6}$ を計算しよう。

G2: $4 < 6$ だから、G3へ進む。

G3: $\GCD{4}{6 - 4}$ つまり $\GCD{4}{2}$ を計算して出力しよう。

(では、ここで改めて……)

  G1: $\GCD{4}{2}$ を計算しよう。

  G2: $4 < 2$ ではないから、G4へ進む。

  G4: $4 > 2$ だから、G5へ進む。

  G5: $\GCD{4 - 2}{2}$ つまり $\GCD{2}{2}$ を計算して出力しよう。

  (では、ここで改めて……)

    G1: $\GCD{2}{2}$ を計算しよう。

    G2: $2 < 2$ ではないから、G4へ進む。

    G4: $2 > 2$ ではないから、G6へ進む。

    G6: G7へ進む。

    G7: $n$ つまり $2$ が出力となる(これは $\GCD{2}{2}$ の結果だ)。

  G5: $\GCD{2}{2}$ の出力は $2$ だ(これは $\GCD{4}{2}$ の結果だ)。

G3: $\GCD{4}{2}$ の出力は $2$ だ(これは $\GCD{4}{6}$ の結果だ)。

……確かに、 $4$ と $6$ の最大公約数 $2$ になっているな。

テトラ「先輩、先輩……考えてますね?」

「考えてるよ。確かに、 この手続き $\GCD{m}{n}$ は $m$ と $n$ の最大公約数を求めているようだね。 答えは一応《いえる》じゃないかな」

リサ「正解」

解答1

このアルゴリズムは正しく最大公約数を計算する。

テトラ「やっぱり先輩は早いですね。 あたしはかなりノートに書いてはじめて納得できました」

「なんだ、テトラちゃんはノートに書いたんだ」

テトラ「あちゃっ!」

「僕は頭の中で $m = 4, n = 6$ で考えただけだよ。 だから、たった一つの例しか考えてない。 でも、これは正しいアルゴリズムになるということはわかる」

テトラ「それは、どうしてでしょうか?」

「うん、これはよく考えられている。 最大公約数が持っている性質をしっかりと満たしているんだよ」

リサ「……」

テトラ「?」

「この手続き $\GCD{m}{n}$ は《場合分け》をやっているよね。三つの場合に分けて考えている。

  • (1)$m < n$ の場合
  • (2)$m > n$ の場合
  • (3)それ以外($m = n$)の場合
という三つの場合」

テトラ「そうですね」

「そしてこれはちゃんと《もれなく、だぶりなく》という場合分けになっている。 二つの正の整数 $m,n$ が与えられたとき、 $m < n$ か、 $m > n$ か、それ以外になるからね。 そして《それ以外》というのは $m = n$ のとき」

テトラ「はい」

「一番簡単なのが $m = n$ のときで、 そのとき $\GCD{m}{n}$ の出力は $n$ になるけど、 最大公約数も確かに $n$ になっている。だから(3)の場合は正しい」

  • (1)$m < n$ のとき
  • (2)$m > n$ のとき
  • (3)それ以外($m = n$)のとき ← 正しい!

テトラ「なるほど……あとは(1)と(2)が正しいといえばいい?」

「そうだよね。(1)というのは $m < n$ の場合だけど、 これは $\GCD{m}{n - m}$ の計算をしている。 $m < n$ なんだから、 $n - m > 0$ となっていて、 $m$ も $n-m$ も正の整数になっている。 だから$\REMTEXT{GCD}$という手続きへの入力の条件を満たしている」

リサ「(頷く)」

「すると、あとは数学的な話として、

 《$m$ と $n$ の最大公約数》$=$《$m$ と $n - m$ の最大公約数》

が常に成り立つかどうかをいえばいい。そしてこれはもちろん成り立つ」

テトラ「お待ちください。それって《もちろん》といえるくらい、簡単な話なんでしょうか」

「そうだね。数学的な最大公約数と、 この手続きが計算する値が混乱しちゃうから、 数学的な最大公約数は $\gcdmath{m}{n}$ と書いて、 この手続きが計算する値は $\GCD{m}{n}$ と書くことにしようか。 いま僕は、 $m < n$ のとき、 $$ \gcdmath{m}{n} = \gcdmath{m}{n - m} $$ は簡単にわかるよ、っていったんだ」

テトラ「あたしってほんと鈍いですね……そんなに簡単にはわかりません……」

「ひとつひとつ考えれば大丈夫だよ。 まず、 $\gcdmath{m}{n}$ は $m$ と $n$ の最大公約数だから、 $m$ も割り切るし、 $n$ も割り切る。 だから、 $\gcdmath{m}{n}$ は $n-m$ も割り切る……ここまではいい?」

テトラ「$\gcdmath{m}{n}$ は $n - m$ を割り切るか……そうですね。 $$ n - m = A\gcdmath{m}{n} - B\gcdmath{m}{n} = (A - B)\gcdmath{m}{n} $$ ということですね?」

「そうそう。だから、 $\gcdmath{m}{n}$ は、 $m$ と $n - m$ を割り切る。 つまり、 $\gcdmath{m}{n}$ は《$m$ と $n-m$ の公約数》といえる」

テトラ「はい」

「すると、 $\gcdmath{m}{n}$ は《$\gcdmath{m}{n-m}$ の約数》であるといえる」

テトラ「ははあ……そうですね。公約数は、最大公約数の約数なので?」

「うん。逆に、 $\gcdmath{m}{n - m}$ は $m$ と $n-m$ の両方を割り切るから、 $m$ と $n$ の両方も割り切る。さっきのテトラちゃんの書き方をまねするなら、 $$ m = C\gcdmath{m}{n-m}, n - m = D\gcdmath{m}{n-m}, $$ から、 $$ n = m + (n-m) = (C + D)\gcdmath{m}{n-m} $$ がいえるから。つまり、 $\gcdmath{m}{n - m}$ は《$m$ と $n$ の公約数》になってる。 ということは $\gcdmath{m}{n-m}$ は《$\gcdmath{m}{n}$ の約数》になる」

テトラ「お互いがお互いの約数?」

「そういうことだね。

  • $\gcdmath{m}{n}$ は、 $\gcdmath{m}{n-m}$ の約数である。
  • $\gcdmath{m}{n-m}$ は、 $\gcdmath{m}{n}$ の約数である。
だから、 $$ \gcdmath{m}{n} = \gcdmath{m}{n-m} $$ がいえる。《$m$ と $n$ の最大公約数》は《$m$ と $n - m$ の最大公約数》に等しいんだね」

リサ「アルゴリズムの話」

「うん、いま戻るよ。 $$ \gcdmath{m}{n} = \gcdmath{m}{n-m} $$ だから、 $\GCD{m}{n}$ を計算する代わりに、 $\GCD{m}{n-m}$ を計算するのは正しい。 両方等しいんだから。これで(1)の正しさを証明したことになる」

  • (1)$m < n$ のとき ← 正しい!
  • (2)$m > n$ のとき
  • (3)それ以外($m = n$)のとき ← 正しい!

テトラ「だとしたら、(2)も正しいですね。(1)と同じことですから」

「そうだね」

  • (1)$m < n$ のとき ← 正しい!
  • (2)$m > n$ のとき ← 正しい!
  • (3)それ以外($m = n$)のとき ← 正しい!

テトラ「これで証明できたんですね?」

リサ「できてない」

「え?」

テトラ「いま、先輩が話してたのはまちがい?」

リサ「まちがいではない」

「なのに、証明できてない……」

テトラ「リサちゃんは何かを見抜いているんですよね。ちょっと待ってください。ここまでのお話を整理します!」

  • $\GCD{m}{n}$ が、正の整数 $m,n$ の最大公約数を計算するかどうかを考えています。
  • $\GCD{m}{n}$ は《場合分け》を行っています。
  • (1)は $m < n$ の場合です。 $\GCD{m}{n - m}$ が《$m$ と $n - m$ の最大公約数》を正しく計算するなら、それは《$m$ と $n$ の最大公約数》に等しくなります。
  • (2)は $m > n$ の場合です。 $\GCD{m - n}{n}$ が《$m - n$ と $n$ の最大公約数》を正しく計算するなら、それは《$m$ と $n$ の最大公約数》に等しくなります。
  • (3)は $m = n$ の場合です。この場合、 $n$ は《$m$ と $n$ の最大公約数》に等しくなります。

「うん、テトラちゃんの整理は僕の理解と完全に一致しているなあ……ここまでの説明で、 $\GCD{m}{n}$ が、正の整数 $m,n$ の最大公約数を正しく計算することは証明できていない?」

リサ「(頷く)」

テトラ「ここまでのお話で、どこに穴があるんでしょう……」

テトラちゃんはしばらく考える。

リサは涼しげな顔で無言のまま、キーボードを叩いて何かを書いている。

「降参。わからないよ」

リサの顔を見て、続いてテトラちゃんに目を移す。

テトラ「あたしも、降参です」

リサ停止性の証明

テトラ「停止性……このアルゴリズムが停止するかどうか、ということでしょうか」

「なるほど! わかったよ。確かにリサのいう通りだ」

テトラ「どういうことですか?」

「さっきのテトラちゃんの整理の中に、こういう部分が出てきたよね。 $m < n$ の場合……」

$\GCD{m}{n - m}$ が《$m$ と $n - m$ の最大公約数》を正しく計算するなら、 それは《$m$ と $n$ の最大公約数》に等しくなります。

テトラ「そうですが……」

「$\GCD{m}{n - m}$ が《$m$ と $n - m$ の最大公約数》を正しく計算するなら、 という仮定には、 $\GCD{m}{n - m}$ の計算が、 いつか必ず終了するという仮定が隠されているんだよ! でも、 僕のさっきの説明の中には、計算が終了することの証明は何一つ出てこなかった。 リサはそこにダメ出しをしたんだね。《停止性の証明》が欠けていたわけだ」

リサ「(頷く)」

テトラ「……三つの場合分けで、完璧だと思ったんですが、 そうじゃないんですね。終了することの証明がないというのは、 無限に計算を続けてしまう可能性がある……と?」

「うん。実際には$\REMTEXT{GCD}$というこの手続きは正しいよ。無限に計算が続くことはない。 ただ、計算は無限に続かずアルゴリズムは必ず停止するという主張を僕はしなかった。 もっとも、《停止性の証明》が必要だとわかってしまえば、 証明そのものはすぐにできるけどね。だって」

テトラ「お待ちください! テトラはリベンジに挑戦します。 この $\GCD{m}{n}$ が必ず計算を終了して出力することを証明すればいいんですよね?」

「そうそう」

リサ「……」

テトラちゃんはノートに何か書き始めた。

リサはキーボードを叩いている。

も、あることを考え始める。

テトラ「……わかりました。簡単です。入力が必ず小さくなっていくからです」

「そうだね」

テトラ「どんな正の整数 $m,n$ が与えられても、 $\GCD{m}{n}$ が計算を終了することを証明すればいいんですよね。 だって、計算が終了しさえすれば、その結果が正しいことはもう証明済みですから」

リサ「(頷く)」

テトラ「これも場合分けなんですよ。(3)$m = n$ の場合、計算は終了します。だって $n$ を出力して終わりですから。 (1)の場合はどうかというと、 $\GCD{m}{n}$ の代わりに $\GCD{m}{n - m}$ を計算します。 このとき、入力 $(m,n)$ が $(m,n-m)$ と変化しました。 $n > n-m$ ですから、二つ目の入力は小さくなっています。 (2)の場合は入力が $(m,n)$ から $(m-n,n)$ に変化します。 $m > n-m$ ですから、一つ目の入力が小さくなります」

「うんうん」

テトラ「ですから、 $\GCD{m}{n}$ を計算するのに……計算は……無限には続きません。 だって、正の整数という条件がありますから。 ……これで証明に、なっているでしょうか?」

「いいたいことはわかるけど、もう一声! という感じかなあ。(1)の場合でも、(2)の場合でも、(3)の場合でも有限回で終わる、 っていいたいんだよね。だったら、何か確実に単調減少していく数を作れば明確になるよ。 たとえば、二つの入力の和である $m+n$ という数を《目印》に使う。 $\GCD{m}{n}$ を計算するとき、(1)の場合には $\GCD{m}{n-m}$ を計算するわけだから、 二つの入力の和は $m+(n-m) = n$ になる。《目印》は $m+n \to n$ に減ったわけだ」

テトラ「なるほど……(2)の場合には《目印》は $m+n \to m$ に減りますね。(3)の場合は確実に終了する」

「そういうこと。だから $\GCD{m}{n}$ の計算はいくら多く深みに入ったとしても無限には続かず、たかだか $m+n$ の繰り返しで終わる」

リサ「証明完了」

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

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


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

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

(2017年5月19日)

[icon]

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


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

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