「一歩一歩、追いかけていくのはいいんですが、そうすると全体がわからなくなるんです......」とテトラちゃんは言った。「整数に誘われて」シーズン第3章前編。:数学が好きな高校生。テトラちゃん:僕の後輩。好奇心旺盛で根気強い《元気少女》。リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。$アルゴリズムクイズ!放課後。テトラちゃんとリサがおしゃべりをしていた。いっても主に「しゃべって」いるのはテトラちゃんの方だけれど。僕「何の話?」テトラ「リサちゃんが、クイズを出しているんです。真っ赤な髪のリサはコンピュータ少女。すばやく無音でタイピングする。問題1このアルゴリズムは正しく最大公約数を計算するか。それは、なかなか、光栄なのか、恐怖なのか。僕「......それじゃ、いちおうこのアルゴリズムの表記法だけ確認させてよ。僕は頭の中でそっと考える。《小さな数で確かめる》のが基本だな。$\GCD{4}{6}$を計算しよう。6$だから、G3へ進む。4}$つまり$\GCD{4}{2}$を計算して出力しよう。$\GCD{4}{2}$を計算しよう。2$ではないから、G4へ進む。2$だから、G5へ進む。2}{2}$つまり$\GCD{2}{2}$を計算して出力しよう。$\GCD{2}{2}$を計算しよう。2$ではないから、G4へ進む。2$ではないから、G6へ進む。$n$つまり$2$が出力となる(これは$\GCD{2}{2}$の結果だ)。$\GCD{2}{2}$の出力は$2$だ(これは$\GCD{4}{2}$の結果だ)。$\GCD{4}{2}$の出力は$2$だ(これは$\GCD{4}{6}$の結果だ)。......確かに、$4$と$6$の最大公約数$2$になっているな。確かに、この手続き$\GCD{m}{n}$は$m$と$n$の最大公約数を求めているようだね。解答1このアルゴリズムは正しく最大公約数を計算する。テトラ「やっぱり先輩は早いですね。6$で考えただけだよ。一つの例しか考えてない。僕「うん、これはよく考えられている。僕「この手続き$\GCD{m}{n}$は《場合分け》をやっているよね。三つの場合に分けて考えている。僕「そしてこれはちゃんと《もれなく、だぶりなく》という場合分けになっている。n$か、それ以外になるからね。最大公約数も確かに$n$になっている。m}$の計算をしている。0$となっていて、$m$も$n-m$も正の整数になっている。m$の最大公約数》が常に成り立つかどうかをいえばいい。これはもちろん成り立つ」テトラ「お待ちください。この手続きが計算する値は$\GCD{m}{n}$と書くことにしようか。僕「ひとつひとつ考えれば大丈夫だよ。$\gcdmath{m}{n}$は$m$と$n$の最大公約数だから、$m$も割り切るし、$n$も割り切る。m$を割り切るか......そうですね。