問題12　（tomhさん）解　答
問題のみ　読みたい方は物語編を読み飛ばしてください。
でもtomhさん渾身の物語です。ぜひ読んでください。
【みっちの互助法】

物語編
みっちは東H校の数学教師をしている。しかも、数学教師のまとめ役だった。
今日は成績があまり良くない者たちを集めて補習を行っていた。その人数は
10名になった。みっちはまとめ役ということもあり、この補習につきあっていた。
実際の補習の進行は、同僚の"桃ちゃん"先生がやっていた。みっちは、机
の間を歩いて、個別にできない者達にアドバイスをしていた。
　「…というわけで、この問題の答えは"2"になるわけです。」
と桃ちゃんが、ある問題の説明を終えた。説明を聞き終えた者達の表情は
様々だった。納得している者や困った顔をしている者、表情からは何を考え
ているかわからない者もいた。幸い、眠っている輩はいなかったが…
そのうち、一人が質問をした。
　「桃ちゃん先生、途中で出てきた"ユークリッドのゴジョ法"ってのが
わからなかったんだけど…」
みっちは、「ま、わからないままにするよりは、質問が出る方がましかぁ (--; 」
と思いながら、続きを聞いていた。
　「ユークリッドは、"互助法"っていうので誰と助け合ってたの?」
みっちも桃ちゃんもその言葉で、一気に力が抜ける思いだった。
　「あのね、それは"ゴジョ"違いなの。"ゴジョ"ってのは、こう書くのよ」
そう言って、桃ちゃんは黒板に"Euclidの互除法"と書いた。
　「これはね、二つの数の公約数を求めるのに使うのよ。お互いに割り算を
していくから"互除法"っていうのよ。習ったでしょ?」
ここで、みっちは桃ちゃんだけに分かるように合図を送った。折角、できない
ことを自覚して集まってきた者達に、"習ったでしょ"とか"そんなことも分から
ないのか"とかは、禁句にしようと二人は打ち合わせをしていたのだった。
みっちの合図に気付いた桃ちゃんは、すぐにEuclidの"互除法"の説明を
始めた。
「分からなくてもいいわ。今日覚えてしまえばいいのよ」と言って、
桃ちゃんは黒板に向かった。
　「いい、60と25を例にとるわよ」
桃ちゃんは、次のような式を黒板に書きながら説明をした。

　65 = 2x25 +15,
　25 = 1x15 +10,
　15 = 1x10 + 5,
　10 = 2x 5 + 0.

　「…となって、65と25の公約数は5だってわかるのよ」
　「ふ〜ん。でも、何回も割り算をやらなきゃならないなんて面倒だなぁ」
と、最初に質問をした者が言った。
　「何言ってるの、公約数を求める便利な方法なのよ」　と桃ちゃんは言った。
　「でもさ、今は、割り算が4回で済んだけど、延々と何回もやらなきゃ
ならないかもじゃん」と、今度は別の者が言った。それに呼応して、教室中が
ザワザワしてきた。そんな中、また別の者が桃ちゃんに当然の質問をした。
　「一体何回やれば、必ず終わるのさ」
桃ちゃんは、一瞬戸惑った。 (--;ウゥ そして、みっちの方を見て言った。
「それは、みっち先生に答えてもらいましょうね… (^^; 」
教室にいる者が一斉にみっちの方を見た。みっちは、教室の中をゆっくり見回すと、
自信に満ちた顔で前に進み出た。実は、この答えをみっちは知っていたのだった。(^o^)
　「これで数学教師としての威厳を見せることができるなぁ。(*^.^*)」と
思いつつ、みっちは話し始めた。
　「二つの数を1億以下としよう…」

（この物語はフィクションです。実在の人物・団体とは一切関係
ありません。 (^^; ）

問題編
問：1億以下の2つの自然数a,b(a>b)が与えられたとき、Euclidの互除法で
公約数を見つけることにします。この方法で最悪の場合、何回割り算を
行わなければならないでしょうか？
また、そのような最悪の組み合わせになる(a,b)は何組ありますか？

注：a>bのとき、b=0xa+bとすると1回多くなってしまいますので、
割り算は、a=qb+rから始めることにします。
また、互除法の終了は、余りが0になるまでとします。

問題1２　正解者一覧表