高校数学A 互除法の計算表—割る数と余りを引き継いで最後の非零値を特定する｜武蔵野個別指導塾

互除法の各行で割る数と余りを引き継ぎ、最後の非零値を選んで元の2数に戻して検算します。

よくあるのは、2つの整数の最大公約数を求める途中で、最後の余りが0になったのを見て、そのまま0と答えてしまう場面です。計算は最後まで進んでいても、表のどの欄を答えとして読むかが曖昧だと、正しい値を取り逃します。割る数と余りの移動を目で追い、各行を掛け算と足し算で戻すと、途中の間違いも見つけやすくなります。

数学Aの整数の学習では、ユークリッドの互除法を扱います。ここでは正整数2個の計算表を中心に、余りが0になる行の意味と検算を調べます。余りの式を逆にたどって別の方程式を解く話には進まず、表を正しく完成させることに集中します。

どの欄を問われているか

出方は大きく分けて3つあります。2つの正整数から最大公約数を求める問題、途中まで書かれた表の空欄を埋める問題、最後の行を見て答えと理由を説明する問題です。いずれも、割り算を繰り返すという同じ操作を使いますが、空欄を埋める場合は前後の行のつながりまで確認する必要があります。

例えば、ある行の余りを次の行の割られる数に置くと、計算を進めたつもりでも別の数の組に変わってしまいます。反対に、その行の割る数と余りを順に次の割られる数と割る数にすれば、正しい組を引き継げます。商は引き継がず、その行の計算を確かめるために残します。

問題を読み始めたら、対象が正整数2個であること、求めるものが最大公約数であることを確かめます。答えは正の整数です。表を完成させた後には、最後の0ではなく、その直前に現れた0でない余りを探します。最初の割り算で割り切れた場合には、最初の割る数が答えです。

除法の4つの欄をつなぐ

正整数 a を正整数 b で割ると、商 q と余り r を使って、次のように表せます。余りは0以上で、割る数 b より小さい整数です。

a = b・q + r
0 ≤ r < b

a は割られる数、b は割る数です。余りが0でなければ、次は b を r で割ります。図1のように、前の行の割る数と余りが、次の行の左側の2つの欄に移ります。前の行の商を次の除数にするのではありません。

図1では一般の文字で対応を示しています。余り r は b より小さいので、次の割る数は前より小さくなります。正の整数を割る数として使い続ける間、その値は小さくなり続けるため、いつか余り0に達します。0で割ることはできないので、0が出た行で作業を終えます。

なぜこの手順で最大公約数を保てるのでしょうか。a = b・q + r では、a と b の共通約数は r も割り、b と r の共通約数は a も割ります。したがって共通約数は入れ替わりの前後で同じです。最後に余りが0になったとき、最後の割る数はその前の数を割り、両方を割る数の中で最大になります。ここではこの対応を計算の根拠として使います。

検算には2つの関門があります。まず各行で「割る数・商 + 余り」が割られる数に戻ること、次に余りが0以上かつ割る数未満であることです。等式が合っていても、余りが割る数以上なら商をもう1増やせるため、除法の表としては完成していません。行単位の確認に加えて、前の割る数と余りが次の2つの数になっているかも確認します。

基本例題：表を最後まで進める

正整数 527 と 323 の最大公約数を、互除法の計算表を使って正の整数で求めてください。各行を割られる数、割る数、商、余りの順に読みます。

まず大きい 527 を 323 で割ります。商は1で、余りは 527 − 323 = 204 です。204 は0以上323未満なので、この行の条件を満たします。次は元の割る数323を、得られた余り204で割ります。

527 = 323・1 + 204
323 = 204・1 + 119
204 = 119・1 + 85
119 = 85・1 + 34
85 = 34・2 + 17
34 = 17・2 + 0

図2のように、最後の行の余りは0で、その行の割る数は17です。前の行を見ると17が最後の0でない余りですから、求める最大公約数は17です。0は割り切れたことを示す目印であり、最大公約数の欄ではありません。

各行を復元すると、323 + 204 = 527、204 + 119 = 323、119 + 85 = 204、85 + 34 = 119、68 + 17 = 85、34 + 0 = 34 です。余りは順に204、119、85、34、17、0で、それぞれの割る数より小さいことも確かめられます。さらに元の2数について 527 = 17・31、323 = 17・19 となり、17が両方を割ることに戻ります。最大である理由は、各行で共通約数が変わらず最後の組が34と17になることです。

この例では余りが何度も出ますが、表の完成を急ぐ必要はありません。1行を書いたら復元し、その行の割る数と余りを次の行の左へ移す、と区切ると、転記と商の間違いを別々に発見できます。余り0を見た後にさらに17を0で割ろうとせず、直前の値を丸で囲んで終了します。

標準例題：商が大きい行を確かめる

正整数 851 と 437 の最大公約数を正の整数で求め、各行の商と余りも示してください。

851 = 437・1 + 414
437 = 414・1 + 23
414 = 23・18 + 0

最初の余りは 851 − 437 = 414 で、437未満です。次の余りは 437 − 414 = 23 です。最後は 23・18 = 414 なので余り0となり、答えは23です。商18は最後の計算に必要ですが、最大公約数は商ではありません。

行の復元は、437 + 414 = 851、414 + 23 = 437、23・18 + 0 = 414 です。元の数へ戻すと 851 = 23・37、437 = 23・19 となり、両方が23で割り切れます。最後の割る数23を超える共通約数が残らないことは、最後の組414と23の共通約数を考えれば確かめられます。

この問題では最後の商を1と決めつけると、余りが割る数より小さいという条件を満たせません。商を見積もった後に掛け算で引き戻すと、大きい商の行でも処理できます。各数の約数を全て列挙する方法もありますが、大きな数では列挙の漏れを点検しにくいため、ここでは除法の表を使います。

発展例題：途中の値から全体を読む

正整数 1157 と 481 の互除法を行います。最大公約数を正の整数で求め、各行の余りと最後に割り切れたことを示してください。

1157 = 481・2 + 195
481 = 195・2 + 91
195 = 91・2 + 13
91 = 13・7 + 0

最初の行は 481・2 = 962、1157 − 962 = 195 です。次は 195・2 = 390、481 − 390 = 91 となります。その次は 91・2 = 182、195 − 182 = 13 です。13は91より小さいので次の割る数に使えます。最後は 13・7 = 91 で、余りが0になりました。

復元すると 962 + 195 = 1157、390 + 91 = 481、182 + 13 = 195、91 + 0 = 91 です。余り195、91、13、0は各行の割る数481、195、91、13よりそれぞれ小さくなっています。よって最大公約数は最後の0でない余り13です。

元の数に戻して 1157 = 13・89、481 = 13・37 も確かめます。この確認で13が共通約数であることは確定します。ただし、それだけで他にもっと大きい共通約数がないとは言えません。最大性まで述べるには、各行で共通約数が保たれ、最後の組91と13の最大公約数が13であるという筋道を添えます。

空欄のある表で途中の行だけ見せられた場合も、同じ基準を使います。割られる数は直前の割る数、割る数は直前の余りです。商と余りはその2数の除法から決まり、式が合っていても余りの範囲に合わなければ修正します。前後の対応と各行の復元は、別々に検査することが大切です。

0を答えにしたとき、どこを直すか

基本例題の最後を「34 = 17・2 + 0、よって最大公約数は0」とするのは誤りです。原因は、最後の行に書かれた余りを、最後の0でない余りと取り違えたことです。図3のように、停止の目印と答えを別の欄として読みます。

図3では17が最後の割る数であり、直前の行で得た余りでもあります。0は割り切れたことを示すので、0を答えから外し、17を元の527と323に戻して割れるか確認します。さらに、最後の組34と17の最大公約数が17であることから、最大性も確かめます。

もう1つの誤りは、例えば 85 = 34・1 + 51 と書いて次へ進むことです。等式そのものは正しいのですが、余り51は割る数34以上です。34をもう1回引くと、85 = 34・2 + 17 となります。式の成立と余りの範囲を両方確認しなければ、誤った行を通してしまいます。

また、最初から割り切れるときに「0の直前の余りが見当たらない」と迷うことがあります。その場合は、最初の割る数が最後の割る数です。大きい数が小さい数で割り切れたので、小さい数が両方の共通約数であり、それを超える共通約数はありません。2数が等しい場合も同じ読み方で処理できます。

練習：表と答えを自分で確かめる

次の数はすべて正整数です。各問で最大公約数を正の整数で答え、必要な除法の行と元の数に戻す確認を書いてください。問題を先に解いてから、後の解答を読みます。

1. 713 と 527 の最大公約数を求めてください。
2. 943 と 667 の最大公約数を求めてください。
3. 1073 と 703 の最大公約数を求めてください。
4. 1221 と 814 の最大公約数を求め、余り0の行を明示してください。
5. 899 と 493 の最大公約数を求め、最後の0でない余りと停止の行を区別してください。

練習の解答と読み戻し

1

713 = 527・1 + 186
527 = 186・2 + 155
186 = 155・1 + 31
155 = 31・5 + 0

答えは31です。各行は 527 + 186 = 713、372 + 155 = 527、155 + 31 = 186、155 + 0 = 155 と戻り、余りは各除数未満です。元の数も 713 = 31・23、527 = 31・17 となります。最後の組155と31における最大公約数が31なので、共通約数の最大も31です。

2

943 = 667・1 + 276
667 = 276・2 + 115
276 = 115・2 + 46
115 = 46・2 + 23
46 = 23・2 + 0

答えは23です。各行は 667 + 276 = 943、552 + 115 = 667、230 + 46 = 276、92 + 23 = 115、46 + 0 = 46 と復元できます。余りはそれぞれ割る数より小さく、元の数も 943 = 23・41、667 = 23・29 です。最後の組46と23まで共通約数は変わりません。

3

1073 = 703・1 + 370
703 = 370・1 + 333
370 = 333・1 + 37
333 = 37・9 + 0

答えは37です。各行は 703 + 370 = 1073、370 + 333 = 703、333 + 37 = 370、333 + 0 = 333 と復元でき、余りも範囲内です。1073 = 37・29、703 = 37・19 と元の条件へ戻せます。最後の組333と37の最大公約数は37です。

4

1221 = 814・1 + 407
814 = 407・2 + 0

答えは407です。814 + 407 = 1221、814 + 0 = 814 と復元でき、407は814未満です。余り0の行は2行目で、407はその直前の0でない余りです。1221 = 407・3、814 = 407・2 なので元の数も割れ、最後の組814と407の最大公約数は407です。

5

899 = 493・1 + 406
493 = 406・1 + 87
406 = 87・4 + 58
87 = 58・1 + 29
58 = 29・2 + 0

答えは29です。493 + 406 = 899、406 + 87 = 493、348 + 58 = 406、58 + 29 = 87、58 + 0 = 58 と各行が戻り、余りも各除数より小さくなります。最後の0でない余りは29、停止の行は 58 = 29・2 + 0 です。元の数も 899 = 29・31、493 = 29・17 と割れ、最後の組58と29から最大性が確かめられます。

手元に残す4行

割られる数 = 割る数・商 + 余り、余りは0以上で割る数未満です。 次の行には、今の割る数と余りをこの順に移します。 余り0で停止し、最後の0でない余りを答えます。 各行を復元し、答えを元の2数にも戻します。

つまずきを見つける問い

自分の表を見ながら「次の行の2数は、前の行のどの欄から来たか」と声に出して説明してみてください。商を移していた場合は、1行ごとの掛け算が合っていても、別の組へ進んでいます。表の矢印を指で追い、最初にずれた行から作り直します。

個別指導で確認するときは、最後の行に0を書く理由と、その左の割る数を答えにできる理由を別々に尋ねます。また、等式が成り立っても余りが除数以上の行を示し、商を増やして直せるかを確かめます。割り切れた印と最大公約数の位置を区別できれば、長い表でも終点を見失いません。