第195回 ユークリッドの互除法(前編)

「一歩一歩、追いかけていくのはいいんですが、そうすると全体がわからなくなるんです……」とテトラちゃんは言った。「整数に誘われて」シーズン第3章前編。
登場人物紹介

:数学が好きな高校生。

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

リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
$ \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$
出力
  • $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$も正の整数になっている。 だから$\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}$を計算するのは正しい。 両方等しいんだから。これで(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}$の計算が、 いつか必ず終了するという仮定が隠されているんだよ! でも、 僕のさっきの説明の中には、計算が終了することの証明は何一つ出てこなかった。 リサはそこにダメ出しをしたんだね。《停止性の証明》が欠けていたわけだ」

リサ「(頷く)」

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

「うん。実際には$\text{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$の繰り返しで終わる」

リサ「証明完了」

エラーを見つけよ

テトラ「リサちゃん、問題2も出してください」

リサは真っ赤なコンピュータを操作して、別のアルゴリズムを表示させた。
問題2

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

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

テトラ「解説します。$n \bmod m$というのは、$n$から$m$を引けるだけ引き、これ以上$m$を引いたらマイナスになってしまうというところで止めたときの数です」

「ああ、うん。$n \bmod m$は知ってるよ。$n$を$m$で割った剰余、つまり《余り》だよね」

テトラ「失礼しました。その通りです」

「うん、さっき僕もこれと似た手続きのことを考えていたんだよ」

テトラ「そうなんですね!」

「さっきの$\GCD{m}{n}$では《引き算の繰り返し》が出てきたじゃない? それはちょうど、いまテトラちゃんが 《引けるだけ引き、これ以上引いたらマイナスになってしまうというところで止めた》という感覚だなあ、 と思ったんだ。そのこと、ユーリとしゃべったこともあったよ(第194回参照)」

テトラ「それで、余り?」

「うん。リサちゃんの$\GCD{m}{n}$の手続きを見ていて『引き算の繰り返しなんだから、余りを使って表現できそうだ』と考えていたんだ」

テトラ「$\GCD{m}{n}$と、$\XGCD{m}{n}$はそっくりですよね」

《$\GCD{m}{n}$と$\XGCD{m}{n}$の比較》

「そうだね。ちょうど《引き算》のところに《剰余》が出てきてる……で、テトラちゃんは引っ掛かったの?」

テトラ「どき」

「リサちゃんが仕掛けたトラップに引っ掛かったんだね」

テトラ「そうなんです。この$\XGCD{m}{n}$では、最大公約数の計算はできないんです!」

(読者さんへ。$\GCD{m}{n}$では最大公約数が計算できるのに、 $\XGCD{m}{n}$では計算できないのはなぜでしょうか)

「余りのことを《引き算の繰り返し》として考えると見落とすんだけど、$n \bmod m$のことをきちんと《割り算したときの余り》だと考えると、

 ゼロ割り

に注意する必要があるって気づくよね。$n \bmod m$は$m \neq 0$が前提になっている」

テトラ「はい……その通りです」

「$\XGCD{m}{n}$に対する入力のときは、確かに$m > 0, n > 0$が前提になってるから、$n \bmod m$だろうと、$m \bmod n$であろうと未定義にはならない。 でも、《次》がだめなんだよね」

テトラ「そうなんです。$\XGCD{m}{n}$を計算しようとして、$\XGCD{m}{n \bmod m}$の計算を始めようとしたとき、新たな入力の一つ、$n \bmod m$は$0$になっているかもしれません!」

解答2

計算するとはいえない。 計算の途中で$m \bmod n$または$n \bmod m$のいずれかで、 ゼロ割りとなり未定義の計算を実行することになるためである。

「なるほどね。たとえば、$\XGCD{4}{6}$を計算すると……」

X1: $\XGCD{4}{6}$を計算しよう。

X2: $4 < 6$だから、X3へ進む。

X3: $\XGCD{4}{6 \bmod 4}$つまり$\XGCD{4}{2}$を計算して出力しよう。

  X1: $\XGCD{4}{2}$を計算しよう。

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

  X4: $4 > 2$だから、X5へ進む。

  X5: $\XGCD{4 \bmod 2}{2}$つまり$\XGCD{0}{2}$を計算して出力しよう。

    X1: $\XGCD{0}{2}$を計算しよう。

    X2: $0 < 2$だから、X3へ進む。

    X3: $\XGCD{0}{2 \bmod 0}$つまり……と、ここだね!

「ここで$2 \bmod 0$の計算をおこなおうとするけれど、これは未定義だから計算ができない」

リサ「(頷く)」

テトラ「……」

「なるほど。アルゴリズムというのは微妙なものだね……テトラちゃん、何を考えているの?」

テトラ「改良です。訂正です。ゼロ割りの部分を回避すれば、$\XGCD{m}{n}$を正しく動くように直せますね!」

リサ「バグフィックス」

「どんなふうに?」

テトラ「リサちゃん、こんなふうに直してもらえますか?」

テトラちゃんがノートを見せると、リサがすばやくタイプした。

「……そうか。ゼロ割りを回避すればってそういうことか。$n \bmod m = 0$になる場合には$m$が、$m \bmod n = 0$になる場合には$n$が最大公約数だってことだね」

テトラ「はい、これでいいですよね? リサちゃん?」

リサ「《ちゃん》は不要……もっと、簡単にできる(咳)」

リサは、こんなアルゴリズムを見せた。
ユークリッドの互除法

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

リサユークリッドの互除法

「そうか、そうか。これだけでいいわけだ!」

テトラ「ええ? こんなに短くなってしまうんですか? ほんとにこれで$m$と$n$の最大公約数が……」

「うん、うまくいくねえ……」

テトラ「ちょっと待ってください。先ほどは$m < n$と$m > n$を調べていましたよ。でも、今度は$m > 0$しか調べていません!」

「いやいや、そこは大丈夫なんだよ、テトラちゃん。さっき$m < n$と$m > n$を調べていたのは、引き算を使っていたから。 でも、今度は余りを考えている。だから……」

テトラ「……なるほど? $n \bmod m$は、$m < n$のときだけではなく、$m > n$のときも使えるということですね。小さな$n$を大きな$m$で割ったときは、商が$0$で余りが$n$そのもの?」

「そうそう。$\EUCLID{m}{n}$を計算しようとして、もしも$m > n$だったら、E3のところで$\EUCLID{n \bmod m}{m}$つまり$\EUCLID{n}{m}$を計算することになる。 ここで入力の$m$と$n$が交換されている!」

テトラ「でも、肝心のゼロ割り問題は……あああっ、なるほどです。$m = 0$のときには、E5に来て、自動的に$n$が出力となるんですね。この部分はあたしがさきほど考えた訂正と同じですね」

「リサは、さりげなく入力の条件を変更しているよね。これまでは$m > 0$という条件だったけど、$\EUCLID{m}{n}$に対しては$m \GEQ 0$にしてる」

リサ「テトラ氏の追加6行をまとめるため」

「入力が$m \GEQ 0$という条件になっていて、二つの《場合分け》をしていることになるね。(1)$m > 0$の場合と、(2)それ以外の場合。そして(2)は、$m = 0$ということなんだね」

テトラ「……確かに。あたしがさきほど追加したX2a,X2b,X2c,X4a,X4b,X4cの6行分は、ゼロ割りを回避するためでしたが、リサちゃんの$\EUCLID{m}{n}$では、$m > 0$かどうかを調べるだけでゼロ割りの回避ができているんですね……ううう……」

(第195回終わり、第196回へ続く)

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

heliac_arc 頭の中で長方形がいくつかの正方形に切り出されていく・・・ 4日前 replyretweetfavorite

LaplasWitch 今ちょうどユークリッドの互除法について勉強してたからタメになった。 4日前 replyretweetfavorite

maki_glenscape 疑似コードのあるリサ回だと「考えてみましょう!」に挑む気になるなぁ。 ところで「僕」からのリサの呼び方に表記ゆれ……。 5日前 replyretweetfavorite

ryaon 高専1年生の時にやった.懐かしい 5日前 replyretweetfavorite