第195回　ユークリッドの互除法（前編）

$ \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{\gcdmath}[2]{\text{gcd}(#1,#2)} \newcommand{\GCD}[2]{\text{GCD}(#1,#2)} \newcommand{\XGCD}[2]{\text{XGCD}(#1,#2)} \newcommand{\EUCLID}[2]{\text{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$に適当な数をいれて試してみれば、 手がかりがつかめると思うけど……」

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

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

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

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

リサ「それが出力」

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

リサ「場合分け」

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

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

僕「……」

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

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

リサ「正解」

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

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

テトラ「あちゃっ！」

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

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

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

リサ「……」

テトラ「？」

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

• （１）$m < n$の場合
• （２）$m > n$の場合
• （３）それ以外（$m = n$）の場合

という三つの場合」

テトラ「そうですね」

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

テトラ「はい」

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

• （１）$m < n$のとき
• （２）$m > n$のとき
• （３）それ以外（$m = n$）のとき　←　正しい！

テトラ「なるほど……あとは（１）と（２）が正しいといえばいい？」

僕「そうだよね。（１）というのは$m < n$の場合だけど、これは$\GCD{m}{n - m}$の計算をしている。$m < n$なんだから、$n - m > 0$となっていて、$m$も$n-m$も正の整数になっている。 だから$\text{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}$を計算するのは正しい。 両方等しいんだから。これで（１）の正しさを証明したことになる」

• （１）$m < n$のとき　←　正しい！
• （２）$m > n$のとき
• （３）それ以外（$m = n$）のとき　←　正しい！

テトラ「だとしたら、（２）も正しいですね。（１）と同じことですから」

僕「そうだね」

• （１）$m < n$のとき　←　正しい！
• （２）$m > n$のとき　←　正しい！
• （３）それ以外（$m = n$）のとき　←　正しい！

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

リサ「できてない」

僕「え？」

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

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

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

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

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

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

リサ「（頷く）」

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

僕「降参。わからないよ」

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

リサ「停止性の証明」

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

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

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

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

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

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

リサ「（頷く）」

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

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

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

僕「そうそう」

リサ「……」

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

僕「そうだね」

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

リサ「（頷く）」

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

僕「うんうん」

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

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

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

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

リサ「証明完了」