数検準2級 整数の互除法—余りの式を戻して一次不定方程式の整数解を求める｜武蔵野個別指導塾

余りを逆に代入して一組を作り、共通の整数で全解と正の範囲を絞る方法が整数の互除法です。

よくあるのは、受験者が一次不定方程式の整数解を一組見つけ、そこで他の解はないとする場面です。代入して等式が成り立っても、それは見つけた組が答えの一部だと示した段階です。係数に合わせて一方を増やし、もう一方を減らすと、左辺を変えずに別の組を作れることがあります。

整数の互除法は、最大公約数を求めると同時に、その一組を作る道具になります。ここでは余りの式を逆にたどり、整数解を文字で表し、正の解が求められたときには範囲を絞るところまで追います。

何を求める問題か

整数を未知数とする一次の式では、通常の方程式のように片方をもう片方の式で表すだけでは、整数の条件が残ります。例えば 2x + 3y = 1 に実数の制限がなければ x は自由に選べますが、x と y を整数に限れば選び方に間隔が生まれます。答える対象が整数の組であることを、最初に問題文から拾います。

出方には、2つの整数の最大公約数を互除法で求める型、一次不定方程式の整数解を全組求める型、さらに個数などの条件から正の整数解を選ぶ型があります。いずれも自作の型であり、式の右辺や符号によって途中の判断は変わります。

特に見分けたいのは、最大公約数が右辺を割り切るかどうかです。割り切らなければ整数解はありません。割り切る場合でも、正の整数という追加条件があるなら、その範囲に入る組が存在するかを別に調べます。整数解があることと、場面に合う解があることは別の確認です。

余りを戻すと何が見えるか

整数 a を正の整数 b で割ると、商 q と余り r を使って a = bq + r と書けます。余りは 0 以上 b 未満です。この式から、a と b の共通の約数は r = a − bq も割り切ります。逆に b と r の共通の約数は a = bq + r も割り切るので、2組の最大公約数は同じです。

互除法では、割る数と余りを次の組にして割り算を続けます。余りが 0 になったら、その割り算の式の割る数が最大公約数です。最初の割り算で割り切れた場合も、同じ規則で読み取れます。途中で余りが 1 になれば、最大公約数は 1 です。例えば 13 = 5 × 2 + 3、5 = 3 × 1 + 2、3 = 2 × 1 + 1 と進みます。次に 2 = 1 × 2 + 0 となり、最大公約数は 1 です。

図1のように、割り算を進めてから余りを逆に置き換えます。1 = 3 − 2、2 = 5 − 3、3 = 13 − 5 × 2 を順に使えば、1 を 13 と 5 の整数倍の和として表せます。この戻す作業が、不定方程式の一組につながります。

図1の矢印は、計算の順序を進む向きと、余りを戻す向きを区別しています。最後の式の右辺が最大公約数になるため、右辺がその整数倍なら両辺を同じ整数倍して一組を得られます。

一組を得た後は、全解を表す別の理由が必要です。a と b が互いに素で、ax + by = c の一組が x = x₀、y = y₀ なら、差を取って a(x − x₀) = -b(y − y₀) です。a と b は共通の素因数を持たないので、x − x₀ は b の倍数です。整数 k を使い x − x₀ = bk と置くと、y − y₀ = -ak となります。逆にこの形のどの整数 k を代入しても増減が打ち消されます。したがって、漏れなく重なりなく整数解を表せます。

係数の最大公約数が 1 でないときは、まず右辺も含めてその数で割ります。右辺が割り切れない場合、左辺は必ず最大公約数の倍数なのに右辺はそうでないため、整数解はありません。無理に小数の係数で続けず、そこで結論を出します。

基本例題：一組から全組へ

整数 x、y について 13x + 5y = 1 を満たす整数解を全組求めてください。答えは整数を表す文字を用いて示します。

まず最大公約数を調べます。割り算の式を余りが 0 になるまで書きます。

13 = 5 × 2 + 3

5 = 3 × 1 + 2

3 = 2 × 1 + 1

2 = 1 × 2 + 0

最後の 0 でない余りは 1 です。右辺も 1 なので整数解があります。次に 1 を最初の2数で表すため、下の式から戻します。

1 = 3 − 2

= 3 − (5 − 3)

= 2 × 3 − 5

= 2 × (13 − 5 × 2) − 5

= 2 × 13 − 5 × 5

よって x = 2、y = -5 は一組です。実際に 13 × 2 + 5 × (-5) = 26 − 25 = 1 と元の式に戻ります。ただし、この一組だけを答えるのは早すぎます。

任意の整数解とこの一組の差を取ると、13(x − 2) + 5(y + 5) = 0 です。13 と 5 は互いに素なので、x − 2 は 5 の倍数になります。整数 k を使って x − 2 = 5k と置くと、y + 5 = -13k です。したがって全整数解は次の形です。

x = 2 + 5k、y = -5 − 13k（k は整数）

図2のように、k が 1 増えると x は 5 増え、y は 13 減ります。左辺の増加分 13 × 5 と減少分 5 × 13 は等しいので、和は変わりません。k = -1 の組は x = -3、y = 8 で、-39 + 40 = 1 です。k = 0 の組も元の式を満たします。

図2は解の移動を表します。移動できることは別の解の存在を示しますが、それだけでは全解の証明にはなりません。差を取って x − 2 が必ず 5 の倍数だと示したことが、ほかの間隔の解を取りこぼさない理由です。

条件を加えた例題：正の整数に絞る

8個入りの袋と 11個入りの袋があります。それぞれを少なくとも1袋使い、合計を 96個にします。8個入りを x 袋、11個入りを y 袋として、条件を満たすすべての組を整数で求めてください。袋を途中で分けず、袋数は正の整数とします。

条件を式にすると 8x + 11y = 96 です。まず 11 = 8 × 1 + 3、8 = 3 × 2 + 2、3 = 2 × 1 + 1、2 = 1 × 2 + 0 から、8 と 11 の最大公約数は 1 です。右辺は 1 の倍数なので整数解があります。

余りを逆に戻すと、1 = 3 − 2 = 3 − (8 − 3 × 2) = 3 × 3 − 8 = (11 − 8) × 3 − 8 = 11 × 3 − 8 × 4 です。96倍すれば一組 x = -384、y = 288 が得られます。ただし大きな数を扱い続ける必要はありません。解を移して x = 1、y = 8 という扱いやすい一組を得られます。元の式でも 8 × 1 + 11 × 8 = 96 と確かめられます。

差を取ると 8(x − 1) + 11(y − 8) = 0 です。8 と 11 は互いに素なので、整数 k により全整数解は x = 1 + 11k、y = 8 − 8k と表せます。ここから初めて、袋数が正という条件を使います。

x > 0 より 1 + 11k > 0、つまり k > -1/11 です。k は整数なので k は 0 以上です。一方、y > 0 より 8 − 8k > 0、つまり k < 1 です。整数 k は 0 以下に限られます。両方を満たすのは k = 0 ですから、答えは x = 1、y = 8 です。

正の条件を式の途中で忘れると、k = 1 から y = 0 を含めてしまいます。逆に正の整数解が見つからない場合も、範囲に入る整数 k がないと示せば結論になります。端が整数のときは、不等号に等号が付くかどうかを特に確かめます。今回は少なくとも1袋なので 0 は含めません。

誤答から直す：一組を全解と思い込む

基本例題で「x = 2、y = -5 を得た。よってこれが唯一の整数解」とする答えを考えます。代入の計算は正しいものの、唯一とする根拠がありません。x を 5 減らし、y を 13 増やした x = -3、y = 8 も元の式を満たすため、この結論は誤りです。

原因は、一組を作る作業と、ほかの組がないか調べる作業を同じものとして扱ったことです。余りを戻して得た等式は出発点です。任意の解との差を取る行を追加し、両方の変化が同じ整数 k で結ばれることを示します。

図3のように、修正後は x = 2 + 5k、y = -5 − 13k と書きます。2つに別々の文字を使うと増減が対応せず、元の式を満たさない組まで含みます。最後にこの式を元の左辺に代入すると、13 × 2 + 5 × (-5) と、互いに打ち消す k の項が残り、どの整数 k でも 1 になります。

図3の修正は、解をいくつか試すだけの方法とも異なります。試した組が正しいことと、試していない組がないことは別の問題です。差の式から必要な形を導き、その形を代入して十分であることも確かめます。

別の失敗として、最大公約数を求めた後、右辺が割り切れるかを見ずに代入を始めることがあります。例えば 6x + 9y = 10 の左辺は 3 の倍数ですが、10 は 3 の倍数ではありません。整数解はなく、正の整数解もありません。一組を探す時間をかけても見つからない理由を、最初の割り切れ方で説明できます。

解がないときと範囲が空になるとき

解が見つからない理由は2種類に分けて考えます。例えば 4x + 6y = 7 では、左辺が必ず偶数である一方、右辺は奇数です。整数解そのものがありません。最大公約数 2 が 7 を割り切らないことと同じ判断です。負の整数や 0 を試しても、偶数の整数倍の和が偶数であることは変わりません。

これに対し 4x + 6y = 2 には整数解があります。両辺を 2 で割ると 2x + 3y = 1 で、x = -1、y = 1 は一組です。全整数解は x = -1 + 3k、y = 1 − 2k です。しかし x と y の両方が正なら k は 1 以上、同時に 0 以下でなければなりません。両方を満たす整数はなく、正の整数解はありません。整数解の存在と追加条件の成立を順に判定すると、どの段階で答えがなくなったかを説明できます。

練習問題

次の各問は独立した自作問題です。まず問題をまとめて解き、後の答えで、式と元の条件の両方を照らし合わせてください。

1. 17 と 12 の最大公約数を整数で求め、互除法の余りを戻して、その最大公約数を 17 と 12 の整数倍の和で1通り表してください。
2. 7x + 4y = 3 を満たす整数解を全組求め、整数を表す文字で答えてください。
3. 6x + 15y = 14 を満たす整数解があるか調べ、理由を述べてください。
4. 5枚入りの束と 7枚入りの束をそれぞれ少なくとも1束使って、紙を合計 41枚にします。束を分けないとき、それぞれの束数の組を整数ですべて求めてください。

練習問題の答えと解き方

1. 最大公約数は 1 です。17 = 12 × 1 + 5、12 = 5 × 2 + 2、5 = 2 × 2 + 1、2 = 1 × 2 + 0 と進めます。戻すと 1 = 5 − 2 × 2 = 5 − (12 − 5 × 2) × 2 = 5 × 5 − 12 × 2 = (17 − 12) × 5 − 12 × 2 = 17 × 5 − 12 × 7 です。最後の式は 85 − 84 = 1 と元の数で確かめられます。余りの最後が 1 であることが最大公約数の根拠です。

2. 一組は x = 1、y = -1 です。7 × 1 + 4 × (-1) = 3 と確かめます。任意の解との差から 7(x − 1) = -4(y + 1) となり、7 と 4 は互いに素なので x − 1 = 4k と置けます。よって全整数解は x = 1 + 4k、y = -1 − 7k（k は整数）です。代入すると 7 + 28k − 4 − 28k = 3 で、どの整数 k も条件を満たします。例えば k = -1 では x = -3、y = 6 となり、-21 + 24 = 3 です。

3. 整数解はありません。6 と 15 の最大公約数は 3 で、左辺は x、y がどの整数でも 3 の倍数です。14 は 3 で割り切れないため、等式は成り立ちません。正負の値を試しても、この割り切れ方は変わりません。

4. 5枚入りを x 束、7枚入りを y 束とすると 5x + 7y = 41、x > 0、y > 0 です。一組は x = 4、y = 3 です。5 と 7 は互いに素なので、差を取れば全整数解は x = 4 + 7k、y = 3 − 5k（k は整数）です。正の条件から k > -4/7、k < 3/5 となり、整数 k は 0 に限られます。答えは 5枚入りが 4束、7枚入りが 3束です。元の場面に戻すと 5 × 4 + 7 × 3 = 20 + 21 = 41 枚で、両方の束数も正です。

覚えておくこと

• 互除法は余り0で止め、最後の式の割る数を最大公約数として読みます。
• 右辺が最大公約数で割り切れなければ整数解はありません。
• 余りを逆に代入して一組を作り、差を取って全解を表します。
• 正の条件は共通の整数の範囲に直し、端も調べます。
• 得た組を元の式と場面に戻して確かめます。

つまずいた行から戻る

個別指導で答案を見るときは、最初に誤った結論ではなく、その直前の行を見ます。余りの符号が変わったなら、割り算の式を余りについて解き直します。一組は合っているのに全解が抜けたなら、任意の解との差を書く行へ戻ります。

正の組を漏らした場合は、文字の範囲を整数に絞る前の不等号を確認します。境界で 0 を許してよいかは、袋や束の条件で決まります。求めた値が式に合っても場面に合わないことがあるため、最後に数量を数え直します。整数の組を一組から全組へ広げる筋道が、答えの範囲を支えます。