高校数学A 一次不定方程式の解の存在—最大公約数と右辺の関係で解ける条件を判定する｜武蔵野個別指導塾

係数の最大公約数で右辺を割れるかを調べ、割れない理由と整数解の作り方をたどり、解の存在を判定します。

よくあるのは、互除法を使って係数から1を作る練習をした後、右辺が1ではない式を見て手が止まる場面です。右辺が1でなくても、最大公約数の整数倍なら、その倍数を両辺に掛けて整数解を作れます。反対に、係数に共通する約数で右辺を割れなければ、どんな整数を代入しても等式は成立しません。まず存在を判定し、その後に必要な解を作る順で考えます。

何を判定する問題なのか

ここでは a、b を正整数、c を整数とし、ax + by = c を満たす整数 x、y が存在するかを調べます。x と y は負でも0でもかまいません。文字が2個あり、両方に整数という条件が付く方程式を一次不定方程式といいます。求めるのが「存在するか」なのか、「一組を示す」のかを読み分けましょう。

出方の一つは、具体的な係数と右辺を与えて、整数解の有無を判定する型です。解がないときは、試した数がたまたま失敗したことではなく、すべての整数が失敗する理由を示します。もう一つは、右辺に文字を含め、解が存在する値の条件を答える型です。さらに、作った一組が個数などの条件を満たすかまで問う型もあります。このとき、整数解の存在と非負整数解の存在は別の問いです。

数学Aの整数の学習では、約数や倍数、ユークリッドの互除法を使います。ここではそれらを、等式が成立するための条件と、実際に等式を作る手順に結び付けます。一般解の詳しい求め方や、個数に制限がある解の列挙は立ち入りすぎず、存在判定の意味を中心にします。

最大公約数が作る境界

a と b の最大公約数を g とします。g は a と b の両方を割る正整数なので、ある正整数 A、B を用いて a = gA、b = gB と書けます。図1のように、左辺は x、y をどの整数にしても g の倍数です。したがって右辺が g の倍数でなければ、整数解はありません。

図1の左側は必要条件です。整数解があるなら g は c を割ります。c が負でも、c = gk と書ける整数 k があれば g の倍数です。0 も g・0 なので g の倍数です。正の倍数だけを考えて負や0を除かないようにします。

逆向きも成り立ちます。互除法で得られる最後の0でない余りを前の等式に順に戻すと、整数 u、v により g = au + bv と表せます。これは最大公約数の一次結合です。途中の等式は整数の足し算、引き算、整数倍なので、戻して得た係数も整数です。

そこで c = gk と書けるなら、両辺に整数 k を掛けて c = a(ku) + b(kv) を得ます。x = ku、y = kv は整数で、元の方程式を満たします。つまり g が c を割ることは、解が存在するための十分条件でもあります。必要条件と十分条件を合わせると、整数解が存在することと、g が c を割ることは同値です。

この証明は一組を作れることまで示しますが、正の解や非負の解があることまでは示しません。また、g が1であれば任意の整数 c は1の倍数なので、どんな右辺でも整数解があります。g が1より大きいときも、右辺がその倍数なら解は作れます。右辺が1であること自体は条件ではありません。

基本例題：右辺へ一次結合を拡大する

正整数の係数を持つ 14x + 35y = 7 について、x、y を負や0を含む整数として、整数解の有無を判定し、あれば一組を示してください。

まず互除法で最大公約数を求めます。

35 = 14・2 + 7
14 = 7・2 + 0

最後の0でない余りは7です。右辺7は7で割り切れるので、整数解が存在します。最初の式を戻すと、次のように7を係数の一次結合で表せます。

7 = 35 - 14・2
  = 14・(-2) + 35・1

よって x = -2、y = 1 が一組です。図2のように、係数の組を式の元の位置へ戻して確かめます。

14・(-2) + 35・1 = -28 + 35
                        = 7

図2の矢印は係数と解の対応を表します。負の数を使っているため、これは整数解ですが、例えば x と y が物の個数である場合にはそのまま使えません。問題に整数とだけ書いてあるなら、負の解も正しく認めます。

同じ係数で右辺が -21 の場合は、7の一次結合を -3 倍できます。x = 6、y = -3 とすれば、14・6 + 35・(-3) = -21 です。右辺が0なら x = 0、y = 0 が一組になります。このように、右辺の符号によって存在判定の規則を変える必要はありません。

標準例題：割り切れなければ全候補が失敗する

正整数の係数を持つ 21x + 35y = 17 について、x、y は負や0を含む整数とします。整数解の有無を判定し、理由を述べてください。

35 = 21・1 + 14
21 = 14・1 + 7
14 = 7・2 + 0

最大公約数は7です。一方、17を7で割ると商は2、余りは3なので、7は17を割りません。よって整数解は存在しません。直接確かめるなら、左辺は次の形です。

21x + 35y = 7・3x + 7・5y
           = 7(3x + 5y)

x、y が整数なら括弧の中も整数です。左辺は必ず7の倍数ですが、右辺17は7の倍数ではありません。したがって等式は不可能です。いくつか代入して合わなかったから解がないのではなく、候補全体に共通する性質と右辺が食い違うから解がありません。

共通約数を一つ見つけて右辺が割り切れない場合も、不存在の証明には十分です。しかし、見つけた共通約数で右辺が割り切れたことだけから、存在は決まりません。最大公約数まで調べることで、存在と不存在の両方を判定できます。

発展例題：右辺に文字があるとき

正整数の係数を持つ 28x + 49y = n について、x、y と n はいずれも負や0を含む整数とします。整数解が存在する n の条件を述べ、n = -35 のときの解を一組示してください。

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

49 = 28・1 + 21
28 = 21・1 + 7
21 = 7・3 + 0

最大公約数は7です。したがって、求める条件は n が7の倍数であることです。必要性は左辺を 7(4x + 7y) と書けば明らかです。十分性のため、余りの式を戻します。

7 = 28 - 21
  = 28 - (49 - 28)
  = 28・2 - 49

n = 7k、k は整数とすると、両辺を k 倍して次を得ます。

n = 7k
  = 28・(2k) + 49・(-k)

よって x = 2k、y = -k が整数解の一組です。n = -35 なら k = -5 なので x = -10、y = 5 とできます。元に戻すと、28・(-10) + 49・5 = -280 + 245 = -35 です。n = 0 も k = 0 とすれば条件に含まれます。

一方、n が7の倍数でない場合に別の係数の選び方を探しても成功しません。x、y がどんな整数でも左辺が7の倍数であることは変わらないからです。存在する場合の構成と、存在しない場合の矛盾の両方がそろって、条件を言い切れます。

間違いをどこで直すか

「14x + 35y = 21 は右辺が1でないので互除法を使えない」という答えを考えます。原因は、互除法で得た最大公約数を、右辺に合わせて整数倍できることを見落とした点です。基本例題の一次結合を3倍すると次のようになります。

7 = 14・(-2) + 35・1
21 = 14・(-6) + 35・3

したがって (-6, 3) は整数解です。図3のように、右辺を最大公約数で割った商が整数なら、その商を両係数へ掛けます。

図3では3倍できることを示しています。逆に、整数でない倍率では整数の係数が得られるとは限らず、この構成は使えません。そもそも右辺が最大公約数の倍数でなければ、先に示した必要条件に反するので整数解はありません。

もう一つの誤りは、整数解があれば非負整数解もあると考えることです。例えば 7x + 14y = -7 には整数解 (-1, 0) があります。しかし x ≥ 0、y ≥ 0 を課すと左辺は0以上となり、右辺の -7 にはなりません。解の種類に新しい制限が付いたら、整数解の判定を入口として使い、制限を別に確認します。

練習問題

各問の文字は、特に断りがない限り負や0を含む整数です。整数解が存在するかを判定し、求められた場合は一組を示してください。

1. 6x + 15y = 9 の整数解を一組求めてください。
2. 8x + 20y = 11 の整数解の有無を、割り切れる関係を使って判定してください。
3. 9x + 16y = -5 の整数解を一組求めてください。
4. 18x + 30y = m について、整数解が存在する整数 m の条件を求め、m = 24 のとき一組を示してください。
5. 8 cm の棒を x 本、12 cm の棒を y 本使い、合計を4 cmにしたいとします。x、y は負や0を含む整数として式の整数解の有無を判定し、さらに実際の本数として x、y が非負整数のときに実現できるか答えてください。

練習問題の解答と解き方

1. 最大公約数を3倍する

15 = 6・2 + 3
6 = 3・2 + 0
3 = 15 - 6・2
9 = 15・3 - 6・6

最大公約数は3で、9はその3倍です。したがって整数解があり、x = -6、y = 3 が一組です。元に戻すと 6・(-6) + 15・3 = -36 + 45 = 9 です。右辺の9まで復元できています。

2. 共通の約数と右辺を比べる

20 = 8・2 + 4
8 = 4・2 + 0
8x + 20y = 4(2x + 5y)
11 = 4・2 + 3

左辺は常に4の倍数ですが、右辺11は4の倍数ではありません。整数解は存在しません。x、y を負にしても括弧内は整数のままなので、この結論は変わりません。

3. 1を作って負の倍数を掛ける

16 = 9・1 + 7
9 = 7・1 + 2
7 = 2・3 + 1
1 = 7 - 2・3
  = 7 - (9 - 7)・3
  = 7・4 - 9・3
  = (16 - 9)・4 - 9・3
  = 16・4 - 9・7
-5 = 16・(-20) + 9・35

最大公約数は1です。したがって x = 35、y = -20 が一組で、9・35 + 16・(-20) = 315 − 320 = -5 と元の右辺に戻ります。

4. 文字の条件と具体例を分ける

30 = 18・1 + 12
18 = 12・1 + 6
12 = 6・2 + 0
6 = 18 - 12
  = 18 - (30 - 18)
  = 18・2 - 30

最大公約数は6です。整数解が存在する条件は m が6の倍数であることです。必要性は左辺が 6(3x + 5y) と書けることから、十分性は上の一次結合を整数倍できることから従います。m = 24 では4倍し、x = 8、y = -4 を得ます。18・8 + 30・(-4) = 144 − 120 = 24 なので、指定した右辺に戻ります。

5. 式の解と本数を区別する

12 = 8・1 + 4
8 = 4・2 + 0
4 = 12 - 8

最大公約数は4で、右辺4はその倍数です。x = -1、y = 1 は整数解で、8・(-1) + 12・1 = 4 です。しかし負の本数は使えません。非負整数の本数では、両方0なら合計は0 cm、少なくとも一方が正なら合計は8 cm以上です。したがって4 cmを実際に作ることはできません。整数解があるという判定と、場面の条件を満たすという判定の差がここにあります。

覚えておきたい判定

a、b が正整数、c が整数のとき、整数解の存在条件は最大公約数 g が c を割ることです。
g の一次結合を c/g 倍すれば、存在するときの解を一組作れます。
右辺が g の倍数でなければ、左辺の倍数性に反するので解はありません。
正や非負などの追加条件は、整数解の存在とは別に確かめます。

どこで立ち止まっているか

判定が止まるときは、まず「g が c を割る」と「c が g を割る」を取り違えていないか、商を書いて確かめます。解がない説明で数個の代入だけを挙げているなら、左辺を g の倍数としてくくる式に戻ります。解がある説明で判定だけを書いて終えた場合は、一次結合を右辺に合わせて何倍したかを追います。

個別指導では、整数の範囲に負と0が入ることを本人の言葉で確認し、求めた一組を元の式へ代入してもらいます。さらに、同じ式に本数の条件が加わったら何を調べ直すかを尋ねます。係数の最大公約数と右辺の関係が、解の存在を判断する境目です。