高校数学A 一次不定方程式の非負整数解—パラメータの上下限をそろえて個数を数える｜武蔵野個別指導塾

整数パラメータの端点を調べ、0を許す場合と正の場合の個数の違いを追いながら、解なしも判断する手がかりは非負整数解です。

よくあるのは、高校生が整数の一般解を求めた後、不等式の端に0を含めるか決めないまま個数を数える場面です。式が合っていても、0を許すかどうかで端の組が残ったり消えたりします。パラメータの範囲を実数の区間として出し、その中の整数を拾うまでを一続きの作業にしましょう。

何を数える問題か

一次不定方程式は、複数の未知数について整数解を探す方程式です。ここでは正整数の係数を持つ一次式を扱い、未知数は問題ごとに0を含むかどうかを指定します。数学Aの整数に関する学習には、約数や倍数、互除法などがあります。

出方の1つは、非負整数解の組をすべて求め、その個数を数える問題です。もう1つは、同じ式について正整数解の個数を比べる問題です。さらに、式の整数解は存在しても、指定された範囲には1組も残らない場合があります。式に解があるかという問いと、範囲内に解があるかという問いを分けて考えます。

組を数えるときは、xの値だけでなく、対応するyも確認します。一般解でパラメータが1増えるたびにxが変わる形なら、異なるパラメータは異なる組を与えます。この対応を確かめてから、整数の個数を組の個数として数えます。

境界を整数の目盛りに移す

非負整数とは0以上の整数です。正整数は1以上の整数なので、整数に限れば、x > 0はx ≥ 1と同じです。0は非負ですが正ではありません。実数の不等式ではx ≥ 0とx > 0の違いを保ったまま変形し、最後に整数を選んでも構いません。

図1のように、パラメータtが整数で、-2/3 ≤ t ≤ 7/3なら、左端以上の最小の整数は0、右端以下の最大の整数は2です。したがって候補は0、1、2です。左端を整数まで上げる操作を切上げ、右端を整数まで下げる操作を切捨てと呼びます。負の数でも、大小の順を数直線で見れば取り違えを防げます。

左端が整数なら、等号の有無が重要です。例えばt ≥ -1なら-1を含みますが、t > -1なら整数の候補は0からです。右端についてもt ≤ 2なら2を含み、t < 2なら1までです。切上げや切捨ての前に、等号があるかを残しておきます。

下限をL、上限をUとし、両方とも含む整数の範囲がL ≤ t ≤ Uになったとします。L ≤ Uなら整数は端を含めてU − L + 1個です。L > Uなら共通する整数はなく、個数は0です。負の数同士の引き算でも同じ式を使えますが、まず数直線上で端の順を確かめます。

例えば5x + 7y = 47の整数解は、1組(8, 1)を使ってx = 8 + 7t、y = 1 − 5tと表せます。一般解を得るには、任意の解とこの1組の差を取ります。5(x − 8) = -7(y − 1)となり、5と7は互いに素なので、x − 8は7の倍数です。その倍数を7tと置けば、y − 1 = -5tです。逆に整数tを代入すると元の式が成り立つため、漏れも余分もありません。以後も同じ形を使い、中心となる範囲の判断に進みます。

基本例題：0を許して端を数える

5x + 7y = 47を満たす非負整数の組(x, y)をすべて求め、個数を答えてください。

上で得た一般解に、x ≥ 0とy ≥ 0をそれぞれ課します。図2のように、2つの条件を別々に出してから共通部分を取ります。

x = 8 + 7t ≥ 0
7t ≥ -8
t ≥ -8/7

y = 1 - 5t ≥ 0
-5t ≥ -1
t ≤ 1/5

負の数-5で割る行では不等号の向きが逆になります。tは整数なので、最初の条件はt ≥ -1、次の条件はt ≤ 0です。共通範囲は-1 ≤ t ≤ 0となり、候補は-1と0です。

t = -1: (x, y) = (1, 6)
t = 0:  (x, y) = (8, 1)

答えは(1, 6)、(8, 1)の2組です。元の式へ戻すと5・1 + 7・6 = 47、5・8 + 7・1 = 47です。どちらも0以上の整数です。逆に、一般解の全パラメータのうち条件に合う整数を全部挙げたので、これ以外の組はありません。

範囲を出した後、端だけを代入して終わらないようにします。この例では端に挟まる整数が他にありませんが、幅が広ければ間の整数も解になります。個数だけを問われた場合も、端の整数が条件を満たし、隣の整数が範囲外であることを確かめると数え間違いを見つけやすくなります。

標準例題：非負と正を比べる

7x + 5y = 70について、非負整数解と正整数解をそれぞれすべて求め、個数を答えてください。両方ともxとyは整数とします。

(0, 14)は整数解です。任意の整数解との差を取ると7x = 5(14 − y)です。7と5は互いに素なのでxは5の倍数です。整数tを使えば、すべての整数解は次の形です。

x = 5t
y = 14 - 7t

実際、7・5t + 5(14 − 7t) = 70なので、整数tをどれにしても元の式を満たします。まず非負の場合です。

5t ≥ 0
t ≥ 0
14 - 7t ≥ 0
t ≤ 2

よってt = 0、1、2で、組は(0, 14)、(5, 7)、(10, 0)の3組です。両端ではそれぞれxまたはyが0です。元の式の左辺は順に70、35 + 35、70となり、いずれも右辺に戻ります。

正整数の場合には、0を許しません。整数であることを利用して、両方を1以上とします。

5t ≥ 1
t ≥ 1/5
14 - 7t ≥ 1
-7t ≥ -13
t ≤ 13/7

整数tは1だけです。正整数解は(5, 7)の1組で、7・5 + 5・7 = 70です。非負の場合の両端を消した結果と一致しますが、常に両端が消えるわけではありません。端の組が0を含むかどうかを、個々の問題で調べる必要があります。

発展例題：非負条件で残る解と消える解を比べる

7x + 11y = 32を満たす非負整数の組(x, y)が存在するか調べ、存在するならすべて答えてください。存在しない場合は個数を0と答えてください。

まず整数解を探すと、7・(-8) + 11・8 = 32です。7と11は互いに素なので、この組からすべての整数解を表せます。

x = -8 + 11t
y = 8 - 7t

任意の整数tについて、7(-8 + 11t) + 11(8 − 7t) = 32です。逆に任意の整数解との差を取れば、x + 8は11の倍数となり、この形に尽くされます。ここでは整数解の存在だけでは、非負条件を満たすとは言えません。

-8 + 11t ≥ 0
t ≥ 8/11
8 - 7t ≥ 0
t ≤ 8/7

整数に限るとt ≥ 1かつt ≤ 1です。したがってt = 1、(x, y) = (3, 1)の1組です。7・3 + 11・1 = 32となり、両方とも非負です。元の条件へ戻す作業は、一般解の式を検算する作業とは別に必要です。

一方、右辺を32から3へ変えて、7x + 11y = 3とするとどうでしょう。整数解は(2, -1)であり、一般解はx = 2 + 11t、y = -1 − 7tです。非負条件はt ≥ -2/11、t ≤ -1/7となります。実数の共通区間はありますが、整数ではt ≥ 0かつt ≤ -1となり、共通する値がありません。したがって非負整数解は0組です。区間が空である場合だけでなく、区間に整数が入らない場合も解なしになります。

誤答を境界まで戻して直す

7x + 5y = 70の非負整数解を数えるとき、「0 < t < 2だからt = 1の1組」とする誤答を考えます。一般解そのものは合っていますが、非負という条件を正という条件にすり替えています。図3のように、端のt = 0とt = 2では未知数の一方が0になり、非負条件には適合します。

修正するときは、x ≥ 0、y ≥ 0を元の一般解へそのまま書き込みます。得られる0 ≤ t ≤ 2は等号つきですから、0、1、2の3個を数えます。正整数解を求めるときだけ、端の組が除かれます。

別の誤りは、-1/7を切り捨てると0になると考えることです。0は-1/7より大きいので、t ≤ -1/7を満たしません。右端以下の最大の整数は-1です。反対にt ≥ -2/11なら、左端以上の最小の整数は0です。符号だけを見ず、元の不等式に候補を代入しましょう。

また、個数をU − Lとすると両端を数え落とします。たとえば0から2までは、差が2でも整数は0、1、2の3個です。個数の式を使う前に、上下限の順と等号を確認してください。候補が存在しなければ、負の個数を書かず0組と判断します。

練習：範囲を先に決める

各問のx、yは整数です。組は(x, y)の順で答え、個数も示してください。問題を一通り解いてから、後の解答と照合しましょう。

1. 3x + 7y = 28の非負整数解をすべて求めてください。
2. 5x + 9y = 45の正整数解をすべて求めてください。存在しなければ0組と答えてください。
3. 7x + 9y = 63の非負整数解をすべて求めてください。
4. 11x + 7y = 5の非負整数解をすべて求めてください。存在しなければ0組と答えてください。
5. 3x + 11y = 77について、非負整数解のうちx ≥ 4、y ≥ 2を満たす組をすべて求めてください。

練習の解答と解き方

1

(0, 4)から、一般解はx = 7t、y = 4 − 3tです。3と7は互いに素なので、この形で整数解を尽くします。

7t ≥ 0 から t ≥ 0
4 - 3t ≥ 0 から t ≤ 4/3

整数tは0、1です。答えは(0, 4)、(7, 1)の2組です。元の式に戻すと、それぞれ3・0 + 7・4 = 28、3・7 + 7・1 = 28です。0も許されるため最初の組を残します。

2

(0, 5)を使うと、整数解はx = 9t、y = 5 − 5tです。正整数の条件を1以上として表します。

9t ≥ 1 から t ≥ 1/9
5 - 5t ≥ 1 から t ≤ 4/5

整数ではt ≥ 1かつt ≤ 0ですから、正整数解は0組です。実数の区間は残りますが、その中に整数はありません。端を含むかどうかだけでなく、整数が存在するかを調べます。

3

(0, 7)を使うと、整数解はx = 9t、y = 7 − 7tです。

9t ≥ 0 から t ≥ 0
7 - 7t ≥ 0 から t ≤ 1

整数tは0、1なので、(0, 7)、(9, 0)の2組です。7・0 + 9・7 = 63、7・9 + 9・0 = 63です。どちらも片方が0ですが、非負という条件に合います。

4

(3, -4)は11・3 + 7・(-4) = 5を満たします。一般解はx = 3 + 7t、y = -4 − 11tです。

3 + 7t ≥ 0 から t ≥ -3/7
-4 - 11t ≥ 0 から t ≤ -4/11

整数ではt ≥ 0、t ≤ -1です。共通する整数はなく、非負整数解は0組です。出発点の整数解があることと、求める範囲の解があることは別です。

5

(22, 1)は3・22 + 11・1 = 77を満たします。一般解はx = 22 + 11t、y = 1 − 3tです。追加の条件は非負条件より強いため、直接使います。

22 + 11t ≥ 4 から t ≥ -18/11
1 - 3t ≥ 2 から t ≤ -1/3

整数tは-1だけです。答えは(11, 4)の1組で、3・11 + 11・4 = 77です。11 ≥ 4、4 ≥ 2も確認できます。一般解を作って終えると、指定された下限を見落とすので、最後に元の条件へ戻します。

手元に残す要点

非負は0以上、正は整数なら1以上です。
各変数の条件を別々にtの不等式へ直します。
共通区間の端を、等号に注意して整数へ移します。
整数がLからUまでならU − L + 1個、共通する整数がなければ0個です。
組を元の式と範囲に戻して確認します。

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

一般解を代入できるのに個数が合わない場合は、まず0を含める条件を言葉で説明してもらいます。次に負の係数で割る行を指し、不等号がなぜ逆向きになるかを確認します。最後に、求めた範囲の端とその隣の整数を代入して、採用と除外の理由を比べます。

個別指導で確かめたいのは、答えの組だけでなく、一般解の各tが異なる組を与えることと、範囲外のtがどの条件に反するかです。端点を元の条件へ戻す習慣が、非負整数解の数え漏れを防ぎます。

同じ方程式でも特殊解の選び方を変えると、パラメータの端の数値は変わります。たとえば基本例題で(1, 6)を出発点にすると、x = 1 + 7s、y = 6 − 5sです。このときs = 0、1が対象で、先ほどのtとはs = t + 1の関係です。数える整数の名前や端が変わっても、得られる組が一致するかを確認できます。