平成28年度 秋期 午前 問7

✓ これが正解イ3

解説

余りを取り続けると3が残ります。最大公約数です。

定義をそのまま当てていきます。2番目の引数が0でないあいだは、1番目に2番目の値を、2番目に割った余りを置いて自分自身を呼び直します。2番目が0になったところで、そのときの1番目の値が答えになります。231を15で割ると余りが6なので、次は15と6の組です。15を6で割ると余りが3なので、次は6と3の組になります。6を3で割ると余りが0なので、次は3と0の組で、ここで2番目が0ですから1番目の3が値でした。この関数は、二つの整数の最大公約数を求めるやり方として知られています。実際、231は3と7と11を掛けた数、15は3と5を掛けた数なので、両方を割り切る数のうち最大のものは3であり、たどり着いた値と一致します。

ほかの選択肢はなぜ違うのか

• ア2：2 は計算の途中に現れる商です。15を6で割ったときの商がこの値になりますが、この手続きが返すのは商ではなく、余りが0になった時点で割られる側に残っている値でした。見る場所が違います。
• ウ5：5 は15を割り切りますが、231は割り切りません。231を5で割ると余りが1になります。片方だけを割り切る数はこの手続きの終点にならず、実際、途中に現れる値の中にも出てきませんでした。
• エ7：7 は231を割り切りますが、15は割り切りません。15を7で割ると余りが1になります。こちらも片方だけの約数なので、両方を割り切る数を探していくこの手続きの行き着く先にはなりません。