高校数学A ユークリッドの互除法—余りで割る手順を続けて最大公約数を求める｜武蔵野個別指導塾

商と余りの受け渡しを表で追い、互除法が公約数を保つ理由を確かめてから、最大公約数を元の2数の整数倍で表せます。

定期テスト前に割り算の式を並べていて、前の行の商を次の除数にしてしまう場面はよくあります。商も余りも割り算から出る数ですが、次に受け渡す役割は同じではありません。余りがどこへ移るかを確かめながら進めれば、数が大きくても最大公約数までたどれます。

どんな問いに使うか

ユークリッドの互除法は、2つの正整数の最大公約数を、割り算を繰り返して求める方法です。素因数分解がすぐにできない数でも、割る数と余りを順に小さくしていけます。最後に余りが0になったとき、その行で割った数が答えです。

出方の1つは、2つの数を与えられ、最大公約数を求める問題です。途中の割り算の式も書けば、どの数を次に使ったかを追えます。もう1つは、割り算の表の空欄を埋める問題です。行ごとに割られる数、割る数、商、余りを区別します。さらに、得られた式を最後から逆にたどり、最大公約数を元の2数を用いた式で表す準備を問う形もあります。

この説明では、正整数の組と、最後の余りを元の数で表すところまでを扱います。整数解を全部求める問題に進む前に、各行で同じ公約数が保たれる理由を押さえましょう。

余りを次に渡せる理由

正整数 a を正整数 b で割り、商を q、余りを r とすると、a = b × q + r と書けます。余りは 0以上 b未満です。r が0でない間、次は b を r で割ります。図1のように、前の割る数が次の割られる数、前の余りが次の割る数になります。商はその行の式を成立させるために使いますが、次の除数として渡しません。

図1の矢印でつないだ2つを比べると、各段階で割る数が小さくなることも見えます。余りは0以上の整数なので、正の余りがいつまでも小さくなり続けることはなく、やがて余り0で止まります。

なぜ最後の割る数が、元の2数の最大公約数なのでしょうか。a と b の両方を割り切る整数は、a − b × q も割り切るので r も割り切ります。逆に b と r の両方を割り切る整数は、b × q + r も割り切るので a も割り切ります。つまり a と b の公約数と、b と r の公約数は同じです。したがって最大公約数も変わりません。

この関係を各行に繰り返します。最後が u = v × q + 0 なら、v は u を割り切り、v と u の共通の約数のうち最大です。途中で最大公約数は変わらないので、v が最初の2数の最大公約数です。はじめから小さい数が大きい数を割り切る場合も、最初の行で余りが0になり、その割る数が答えです。

基本例題：表で順番を追う

問題　252 と 105 の最大公約数を、互除法を用いて正の整数で求めなさい。割り算の式も示しなさい。

まず大きい252を105で割ります。105を2倍すると210で、3倍すると315となり252を超えます。商は2、余りは252 − 210 = 42です。

252 = 105 × 2 + 42

図2のように、次は前の割る数105を、前の余り42で割ります。商2では84、商3では126なので、余りは21です。

105 = 42 × 2 + 21

次も同じ受け渡しです。42を21で割ると、余りが0になります。

42 = 21 × 2 + 0

図2の最後の行で割る数は21です。したがって、求める最大公約数は 21 です。途中の商はすべて2ですが、次の除数は42、21と移っています。商と余りを取り違えず、式の右端を見て次の行を書きます。

理由もたどりましょう。252と105の公約数は105と42の公約数と同じです。さらに105と42の公約数は42と21の公約数と同じです。42は21で割り切れるので、最大公約数は21です。答えを元の数に戻すと、252 = 21 × 12、105 = 21 × 5です。21が両方を割ることと、割り算の列が最大性を保証することを合わせて確認できます。

余りを求めたら、毎回、割られる数に戻るかも調べます。たとえば2行目は42 × 2 + 21 = 105で、余り21は割る数42より小さく0以上です。右辺が元の数に戻っても余りが割る数以上なら、商を増やして余りを直す必要があります。

逆向きにたどる準備

問題　119 と 34 の最大公約数を正の整数で求め、さらにその最大公約数を119と34の整数倍の和として表しなさい。

119を34で割ると、34 × 3 = 102なので、余りは17です。次に34を17で割ると余りは0です。

119 = 34 × 3 + 17

34 = 17 × 2 + 0

最後の割る数から、最大公約数は17です。逆向きに見ると、最初の式の余り17を左辺に移して、次の式を得ます。

17 = 119 − 34 × 3

これが求める表し方です。119は係数1、34は係数-3の整数倍として現れます。元の数を代入すると119 − 102 = 17です。また119 = 17 × 7、34 = 17 × 2なので、両方を割ることも確認できます。

今度は最後の正の余りが1つ前の余りそのものではなく、複数行を経て現れる場合を考えます。たとえば91と35では、91 = 35 × 2 + 21、35 = 21 × 1 + 14、21 = 14 × 1 + 7、14 = 7 × 2 + 0です。最大公約数は7です。最後の正の余りから、7 = 21 − 14と置き、14 = 35 − 21を代入すると、7 = 21 × 2 − 35です。さらに21 = 91 − 35 × 2を代入して、7 = 91 × 2 − 35 × 5となります。実際に182 − 175 = 7で、91と35はいずれも7で割れます。

このように、行が多いときは、最後の正の余りから1つずつ前の行の余りを置き換えます。数値だけを暗算で入れ替えず、括弧を付けて代入すると、引き算の符号を管理しやすくなります。最初から割り切れるときは、元の小さい数が最大公約数なので、その数を1倍し、もう一方を0倍すれば表せます。

商を持ち越した誤答を直す

基本例題の最初の行は252 = 105 × 2 + 42でした。ここで「次は105を商の2で割る」と進むのが誤答です。105 = 2 × 52 + 1となるため、さらに計算を続けると最大公約数を1と誤ってしまいます。しかし252と105はともに21で割れるので、1が最大という結論は元の条件と合いません。

図3のように、商2はその行で105を何倍したかを示す数です。次に使う42は、252から105の倍数を引いて残った数です。この差を使うからこそ、前の2数と次の2数の公約数が一致します。商を余りの代わりにすると、その根拠は使えません。

図3で正しい移動を確認したら、105 = 42 × 2 + 21からやり直します。42 = 21 × 2 + 0まで書けば、最後の割る数21に戻れます。表の空欄を埋めるときも、前の行の右端を指で追って次の除数に記入し、最後に各行の等式と余りの範囲を確かめます。

別の失敗は、余り0を答えにすることです。0は終了の合図であり、求める値はその直前に割る数として使った正の数です。また、余りが1になった時点で最大公約数は1と判断できますが、手順を明示するなら次の行で1によって割り切れることまで書くと、停止位置が明確です。

途中で困ったときの点検

割り算の商を決めにくいときは、割る数の倍数を小さい方から調べます。たとえば割られる数が80、割る数が23なら、23の3倍は69、4倍は92です。80を超えない最大の倍数は69なので、商は3、余りは11です。80 = 23 × 3 + 11であり、11は23未満です。次は23を11で割り、23 = 11 × 2 + 1、11 = 1 × 11 + 0と続けます。最大公約数1は、80と23に1以外の正の公約数がないことを意味します。

もし最初の計算を80 = 23 × 2 + 34と書くと、等式自体は成立します。しかし余り34が割る数23以上なので、その行は正しい商と余りを表していません。23をもう1つ引けることに気づけば、商を1増やし、余りを23減らして修正できます。逆に商を大きく取りすぎると余りは負になります。そのときは商を減らし、余りを割る数だけ増やします。

2数を与えられた順に割り始めても、小さい数を大きい数で割る最初の商は0で、余りは小さい数です。次の行では順序が入れ替わります。ただし計算を短く見せるため、最初から大きい方を小さい方で割ると整理しやすくなります。同じ正整数どうしなら最初に商1、余り0となり、その共通の数が最大公約数です。

表を書くとき、余りの列に数字を置いた後で、次の行の割る数の列へ移します。そこから商を決め、掛け算を引いた残りを新しい余りの列に書きます。欄が埋まっただけで終わらせず、各行を横に読んで元の割られる数に戻るかを確認すると、転記の誤りも見つけやすくなります。

練習：まず問題を解く

1. 198と72の最大公約数を、互除法を用いて正の整数で求めなさい。各行の商と余りも示しなさい。
2. 143と55の最大公約数を、互除法を用いて正の整数で求めなさい。さらに、その数を143と55の整数倍の和で表しなさい。
3. 168と24の最大公約数を、互除法を用いて正の整数で求めなさい。最初の割り算で終了するかも答えなさい。
4. 187と68について、187 = 68 × 2 + 51の次の行を完成させ、最大公約数を正の整数で求めなさい。

練習の答えと考え方

1. 198 = 72 × 2 + 54、72 = 54 × 1 + 18、54 = 18 × 3 + 0です。商と余りの組は順に2と54、1と18、3と0です。最後の割る数から最大公約数は18です。198 = 18 × 11、72 = 18 × 4と元の数に戻して確かめられます。各行で余りは割る数未満であり、公約数が保たれるので18より大きい公約数はありません。

2. 143 = 55 × 2 + 33、55 = 33 × 1 + 22、33 = 22 × 1 + 11、22 = 11 × 2 + 0です。最大公約数は11です。11 = 33 − 22に22 = 55 − 33を代入し、11 = 33 × 2 − 55とします。33 = 143 − 55 × 2を代入すると、11 = 143 × 2 − 55 × 5です。286 − 275 = 11で、143 = 11 × 13、55 = 11 × 5も成り立ちます。

3. 168 = 24 × 7 + 0です。最初の割り算で終了し、最大公約数は24です。168は24の7倍、24は24の1倍です。24自身を超える整数は24の正の約数になれないので、最大性も確かめられます。

4. 次の行では68を51で割ります。68 = 51 × 1 + 17、51 = 17 × 3 + 0となるので、最大公約数は17です。187 = 17 × 11、68 = 17 × 4で元の2数を割り切ります。最初の商2で割ると公約数を保つ操作にならないため、51を次の除数にします。

途中で計算が合わなくなった場合は、最後から推測して直すより、各行を右辺から計算し直します。等式が成立していても、余りが負だったり割る数以上だったりすれば、商と余りの組としては不適切です。両方の条件を満たした行から、次の割り算に進みましょう。

逆算では、代入先の式に同じ余りが複数回現れることもあります。その場合は同類の項をまとめる前に、代入した括弧をすべて書きます。例えば2倍された余りを置き換えるなら、括弧の中の各項も2倍します。引き算の後ろに括弧がある場合は、括弧を外すときに中の各項の符号が変わります。最後の等式を元の数値で計算しても合わなければ、途中の等式を上から戻って調べます。確認は答えを得るための手順とは別に、書いた結果が元の条件を満たすか調べる作業です。

手元に残す要点

• 割る数と余りを、次の割られる数と割る数に移します。
• 余りは0以上、割る数未満です。
• 余り0の行で割った数が最大公約数です。
• 逆算では最後の正の余りから前の式を代入します。

どこで止まったかを見分ける

商を次の除数に書いてしまうなら、まず1行だけを見て「割る数」「商」「余り」を別々に指せるか確かめます。続いて次の行に移る2つの数を口に出して説明し、移動の理由を公約数の関係と結び付けます。計算ミスが続く場合は、各行で掛け算と足し算を戻し、余りの範囲も検査します。

個別指導で逆算を確認するときは、最後の正の余りを表す式を本人に選んでもらい、どの余りにどの式を代入したかを説明してもらいます。符号が変わる箇所では括弧を残し、完成した式に元の数を代入します。余りを正しく渡すことが、長い計算を確かな一歩ずつに分けます。