高校数学A 互除法の逆算—余りの式を一段ずつ戻して一次結合を作る｜武蔵野個別指導塾

最後の非零の余りから式を逆にたどり、括弧と負号を保って最大公約数を元の2数の整数倍の和で表します。

よくあるのは、互除法の前の余りを代入するとき、括弧を外して符号を逆にしてしまう場面です。最大公約数までは求められたのに、元の2数を使う式に戻すと、左辺と右辺が一致しません。どの行で符号が変わったかを調べるには、代入する式を括弧で囲み、展開と係数の整理を別々の行に書きます。

ここで扱うのは、正整数2個の最大公約数を、それらの数の整数倍の和で表す一組の係数です。整数には負の数と0も含みます。数学Aの整数の学習範囲には、約数と倍数やユークリッドの互除法が含まれます。

何を求める問題か

出方の一つは、2数の最大公約数を求め、その値を2数の整数倍の和で表すものです。例えば係数が負なら、その項は引き算になります。正の数の足し算に限ると、元の2数より小さい最大公約数を表せないことがあります。

もう一つは、除法の式が途中まで与えられ、最後の非零の余りから元の数へ戻すものです。このとき、与えられた商を正しく移項することが最初の関門です。最後に余りが0となる行は最大公約数を見つけるために使い、逆算はその直前の非零の余りの式から始めます。

さらに、最大公約数が1でない場合もあります。1を作ろうとするのではなく、求めた最大公約数そのものを右辺に置きます。係数の一組を求めるのが目標なので、係数の組をすべて列挙する必要はありません。

余りを元の数へ戻す

整数 a、b の整数倍の和 ax + by を、a と b の一次結合と呼びます。ここで x、y は整数です。例えば x が負であっても、負の整数倍として扱えます。a、b を正整数、g をその最大公約数とすると、g は a と b の一次結合で表せます。

理由は互除法の式にあります。a = bq + r なら、r = a − bq です。したがって、余り r はその直前の2数の一次結合です。次の余りも同様に直前の2数で表し、そこに先の余りの式を代入すれば、さらに前の2数の一次結合に戻せます。最後の非零の余りから順に繰り返せば、元の a、b まで戻れます。

図1のように、除法では元の数から余りへ進み、逆算では余りを表す式を反対向きにたどります。矢印の向きを意識すると、どの式を次に代入するかを見失いにくくなります。

図1の下段では、余りを一度に消すのではなく、直前の式に置き換えます。右辺に残る余りが1段前のものへ変わったか、各行で確かめます。元の2数以外が残っているうちは、まだ係数を読み取る段階ではありません。

互除法が終わる理由も押さえます。正の割る数に対する余りは0以上で割る数より小さい整数なので、正の余りは次第に小さくなり、やがて0になります。各除法の前後で共通約数は変わらず、最後に0で割り切ったときの割る数が最大公約数です。この性質を利用し、逆算では最後の非零の余りの値を保ったまま式の右辺だけを書き換えます。

基本例題：括弧を残して1に戻す

正整数 83 と 53 の最大公約数を求め、それを 83x + 53y と表す整数 x、y の組を1組求めてください。負の整数と0も係数に使えます。

まず商と余りを順に求めます。各行で余りは割る数以上にならないようにします。

83 = 53・1 + 30
53 = 30・1 + 23
30 = 23・1 + 7
23 = 7・3 + 2
7 = 2・3 + 1
2 = 1・2 + 0

最後の非零の余りは1ですから、最大公約数は1です。図2のように、最後から2行目を移項して始め、余りを新しいものから順に消します。

1 = 7 - 2・3
  = 7 - (23 - 7・3)・3
  = 7 - 23・3 + 7・9
  = 7・10 - 23・3
  = (30 - 23)・10 - 23・3
  = 30・10 - 23・13
  = 30・10 - (53 - 30)・13
  = 30・23 - 53・13
  = (83 - 53)・23 - 53・13
  = 83・23 - 53・36

よって一組は x = 23、y = -36 です。図2の各行は、代入する余りを、その余りを作った除法の式で表しています。例えば 2 = 23 − 7・3 全体を括弧に入れてから、外側の -3 を両方の項に掛けています。

元の条件へ戻すと、83・23 + 53・(-36) = 1909 − 1908 = 1 です。両方の係数は整数で、右辺は最大公約数に一致します。除法の各行も、商と割る数の積に余りを足せば左辺に戻ることを確かめられます。

この方法では、途中の余りを小さい順に適当に選ぶのではありません。今の式に現れる最後の余りを、その一つ前の除法の式で置き換えます。どの2数を残すかを決めて進むと、係数が大きくなっても整理できます。

標準例題：最大公約数が1以外

正整数 187 と 77 の最大公約数を求め、それを 187x + 77y と表す整数 x、y の組を1組求めてください。係数には負の整数と0を含めます。

187 = 77・2 + 33
77 = 33・2 + 11
33 = 11・3 + 0

最後の非零の余りは11なので、最大公約数は11です。1ではなく11を左辺に残して逆算します。

11 = 77 - 33・2
   = 77 - (187 - 77・2)・2
   = 77 - 187・2 + 77・4
   = 187・(-2) + 77・5

したがって一組は x = -2、y = 5 です。元に戻すと、187・(-2) + 77・5 = -374 + 385 = 11 となります。11は187と77の両方を割り、互除法の最後の非零の余りとも一致します。

この2数はともに11の倍数なので、整数倍の和も11の倍数です。したがって右辺を1にすることはできません。最大公約数が1でない場合に、手順を機械的に1から始めると、そもそも成立しない式を探すことになります。

発展例題：逆算した係数を使う

正整数 97 と 57 について、最大公約数 g を 97x + 57y と表す整数 x、y の組を1組求め、続いて 97u + 57v = 3 を満たす整数 u、v の組を1組求めてください。いずれも負の整数と0を係数に含めます。

まず最大公約数を求めます。

97 = 57・1 + 40
57 = 40・1 + 17
40 = 17・2 + 6
17 = 6・2 + 5
6 = 5・1 + 1
5 = 1・5 + 0

よって g = 1 です。各余りを直前の2数で表して、1から戻します。

1 = 6 - 5
  = 6 - (17 - 6・2)
  = 6・3 - 17
  = (40 - 17・2)・3 - 17
  = 40・3 - 17・7
  = 40・3 - (57 - 40)・7
  = 40・10 - 57・7
  = (97 - 57)・10 - 57・7
  = 97・10 - 57・17

一組は x = 10、y = -17 です。両辺を3倍すると、次の式が得られます。

3 = (97・10 - 57・17)・3
  = 97・30 + 57・(-51)

したがって u = 30、v = -51 は求める一組です。元の条件では 97・30 + 57・(-51) = 2910 − 2907 = 3 です。最初の組も 970 − 969 = 1 と戻して確かめます。

右辺が1から3に変わったとき、片方の係数だけを3倍してはいけません。和全体を3倍するので、両方の項に3を掛けます。ここでは一組を作るところまでを扱い、整数解全体の表し方には踏み込みません。

負号を落とした行を見つける

基本例題の途中で、次のように括弧を外す誤りを考えます。

1 = 7 - (23 - 7・3)・3
誤り: 1 = 7 - 23・3 - 7・9

図3のように、括弧の前の負の係数は括弧の中の両方に掛かります。後ろの項には負と負が掛かるため、正になります。

誤りの右辺に 7 と 23 を戻すと、7 − 69 − 63 = -125 で、左辺の1と一致しません。正しくは 7 − 69 + 63 = 1 です。図3の2本の線の先で、それぞれの符号を決めてから同類項をまとめます。

別の失敗は、最後の余り0を最大公約数にすることです。割り切れた行では、その割る数が直前の非零の余りです。0から逆算を始めても、求めたい正の最大公約数の式にはなりません。終点の行に印を付け、その一つ前の式から戻すと区別できます。

途中で計算が合わなくなったら、最終行だけを何度も眺めず、各行に実際の余りを代入します。前の行までは同じ値で、次の行から値が変わるなら、その間の代入か分配に誤りがあります。括弧を省略せず、移項、代入、展開、整理を別々に書くのが修正の近道です。

自分で戻してみる5問

各問の文字は整数で、負の整数と0を含みます。最大公約数を求め、指定された一次結合の係数の組をそれぞれ1組求めてください。数は各問のために設定したものです。

1. 正整数 161、69 の最大公約数を 161x + 69y と表してください。
2. 正整数 107、67 の最大公約数を 107x + 67y と表してください。
3. 正整数 143、91 の最大公約数を 143x + 91y と表してください。
4. 正整数 173、63 の最大公約数を 173x + 63y と表してください。
5. 正整数 221、119 の最大公約数を 221x + 119y と表し、その式から 221u + 119v = 34 を満たす組も1組求めてください。

解答と考え方

1. 除法と逆算は次のとおりです。

161 = 69・2 + 23
69 = 23・3 + 0
23 = 161 - 69・2

最大公約数は23、一組は x = 1、y = -2 です。元の式で 161 − 138 = 23 となり、23は両方を割ります。最後の0ではなく、その直前の23を使います。

2. 余りを順に出し、1から戻します。

107 = 67 + 40
67 = 40 + 27
40 = 27 + 13
27 = 13・2 + 1
13 = 1・13 + 0
1 = 27 - 13・2
  = 27 - (40 - 27)・2
  = 27・3 - 40・2
  = (67 - 40)・3 - 40・2
  = 67・3 - 40・5
  = 67・3 - (107 - 67)・5
  = 107・(-5) + 67・8

最大公約数は1、一組は x = -5、y = 8 です。元の式へ代入すると -535 + 536 = 1 です。負号を含む括弧を展開した後に、67の係数をまとめます。

3. 最後の非零の余りと、その逆算を示します。

143 = 91 + 52
91 = 52 + 39
52 = 39 + 13
39 = 13・3 + 0
13 = 52 - 39
   = 52 - (91 - 52)
   = 52・2 - 91
   = (143 - 91)・2 - 91
   = 143・2 - 91・3

最大公約数は13、一組は x = 2、y = -3 です。286 − 273 = 13 と元の条件に戻ります。共通の約数13を1に取り違えないようにします。

4. 余り15を使うところから1を戻します。

173 = 63・2 + 47
63 = 47 + 16
47 = 16・2 + 15
16 = 15 + 1
15 = 1・15 + 0
1 = 16 - 15
  = 16 - (47 - 16・2)
  = 16・3 - 47
  = (63 - 47)・3 - 47
  = 63・3 - 47・4
  = 63・3 - (173 - 63・2)・4
  = 173・(-4) + 63・11

最大公約数は1、一組は x = -4、y = 11 です。元に戻すと -692 + 693 = 1 です。最後の代入では、括弧の外の -4 を2項に分配します。

5. 除法と逆算は次のとおりです。

221 = 119 + 102
119 = 102 + 17
102 = 17・6 + 0
17 = 119 - 102
   = 119 - (221 - 119)
   = 221・(-1) + 119・2
34 = 221・(-2) + 119・4

最大公約数は17で、x = -1、y = 2 が一組です。式全体を2倍して u = -2、v = 4 を得ます。元の条件は -221 + 238 = 17、-442 + 476 = 34 となり、どちらも指定の右辺に戻ります。

手元に残す要点

• 最後の非零の余りが最大公約数です。
• その余りから始め、直前の余りを逆順に代入します。
• 負号のある代入は括弧を付け、両項に分配します。
• 元の2数に戻ったら、係数を読み取り元の式で検算します。

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

最大公約数は合っているのに係数が合わない場合、除法と逆算を別々に点検します。除法の行が復元できるなら、代入前後に同じ値が保たれているかを調べます。特に括弧の中の2項へ外側の数を掛けた行を声に出して説明すると、符号を落とした位置が見えます。

個別指導で確かめるなら、まず本人に最後の非零の余りを指してもらい、次にどの余りを消すか、その根拠となる除法の行を選んでもらいます。最後に求めた整数係数を最初の式へ戻し、左辺と右辺が一致する理由まで自分の言葉で説明します。逆算の各行が同じ値を保つことが、係数を信頼する根拠です。