不定方程式｜数A 数学と人間の活動（整数）

STEP 1

\(ax+by=0\) 型の整数解

解が1組だけに決まらず、無数の整数の組が答えになる方程式を「不定方程式」と呼ぶ。まずはいちばん基本の形、右辺が \(0\) の場合から見ていこう。

\(a,b\) が互いに素（最大公約数が \(1\)）な整数のとき、\(ax+by=0\) を満たす整数 \(x,y\) を求めよう。式を変形すると

\(ax = -by\)

左辺は \(a\) の倍数だから、右辺の \(-by\) も \(a\) の倍数でなければならない。ところが \(a\) と \(b\) は互いに素なので、\(-by\)（すなわち \(by\)）が \(a\) の倍数になるためには、\(b\) ではなく \(y\) 自身が \(a\) の倍数でなければならない。そこで \(y=-ak\)（\(k\) は整数）とおくと、

\(ax = -b\cdot(-ak) = abk\ \ \Longrightarrow\ \ x = bk\)

\(a,b\) が互いに素のとき、\(ax+by=0\) の整数解は
\(x = bk,\ \ y = -ak\)（\(k\) は整数）
とすべて表される。

例題　\(3x+5y=0\) を満たす整数 \(x,y\) をすべて求めよ。

解答を見る

\(3\) と \(5\) は互いに素だから、公式より \(x=5k,\ y=-3k\)（\(k\) は整数）

この直線上の点はすべて実数の解だが、そのうち \(x,y\) がともに整数になるのは \(k\) が整数のときの \((5k,\,-3k)\) だけ。等間隔に並ぶ点になっているのがわかる。

STEP 2

\(ax+by=c\) の特殊解を見つける

右辺が \(0\) でない場合は、まず1組でよいので整数解を見つける（これを「特殊解」と呼ぶ）。ここでは \(a,b\) が互いに素なときを考える。この場合、\(c\) がどんな整数であっても必ず整数解が存在する。

特殊解の見つけ方
・係数が小さいときは、\(x=0,1,2,\dots\) と順に代入して \(y\) が整数になるものを探す（目で見つける）。
・係数が大きいときは、ユークリッドの互除法を最後から逆にたどって \(1\) の作り方を組み立てる。

例題1　\(3x+5y=1\) の特殊解を1組求めよ。（係数が小さいので目で探す）

解答を見る

\(x=0\)：\(5y=1\) → 整数にならない。 \(x=1\)：\(3+5y=1 \to 5y=-2\) → 整数にならない。 \(x=2\)：\(3\cdot2+5y=1 \to 6+5y=1 \to 5y=-5 \to y=-1\) → 整数になった！ \((x,y)=(2,\,-1)\) は特殊解の1つ（\(3\cdot2+5\cdot(-1)=6-5=1\) を確認）

例題2　\(23x+16y=1\) の特殊解を1組求めよ。（係数が大きいのでユークリッドの互除法を利用する）

解答を見る

まずユークリッドの互除法で \(23\) と \(16\) の最大公約数を求める（同時に割り算の式を記録しておく）。 \(23 = 1\times16+7\) \(16 = 2\times7+2\) \(7 = 3\times2+1\) \(2 = 2\times1+0\) 最大公約数は \(1\)（最後の割る数）。ここから式を1つずつ「あまり \(=\) …」の形に整理し、下から上へ逆にたどって \(1\) を作る。 \(1 = 7-3\times2\)　……（3番目の式より） \(2 = 16-2\times7\) をこれに代入して \(1 = 7-3\times(16-2\times7) = 7\times7-3\times16\) \(7 = 23-1\times16\) をこれに代入して \(1 = 7\times(23-16)-3\times16 = 7\times23-10\times16\) したがって \(23\times7+16\times(-10)=1\) となり、 \((x,y)=(7,\,-10)\) は特殊解の1つ（検算：\(23\times7-16\times10=161-160=1\)）

注意（存在条件）　\(ax+by=c\) が整数解をもつのは、\(a,b\) の最大公約数が \(c\) を割り切るときに限る。\(a,b\) が互いに素（最大公約数が \(1\)）ならこの条件は自動的に満たされるので、本ページで扱う問題はどれも必ず特殊解が存在する。逆に、最大公約数が \(1\) でなく、それが \(c\) を割り切らない場合は整数解が存在しない。

STEP 3

一般解の書き方

特殊解が1組見つかれば、そこから整数解を「すべて」表す一般解が作れる。STEP1の結果をそのまま使う。

\((x_0,y_0)\) を \(ax+by=c\) の特殊解とし、\((x,y)\) を同じ方程式の別の整数解とする。2つの式

\(ax+by=c,\ \ \ ax_0+by_0=c\)

を辺々引くと \(a(x-x_0)+b(y-y_0)=0\)。これは STEP1 で学んだ「右辺が \(0\)」の形に \((x-x_0,\,y-y_0)\) を代入したものなので、\(a,b\) が互いに素なら

\(x-x_0 = bk,\ \ y-y_0 = -ak\)（\(k\) は整数）

一般解の公式
\(ax+by=c\)（\(a,b\) は互いに素）の整数解全体は、特殊解 \((x_0,y_0)\) を1組使って
\(x = x_0+bk,\ \ y = y_0-ak\)（\(k\) は整数）
とすべて表される。

例題　\(3x+5y=1\) の整数解をすべて表せ。（STEP2例題1で特殊解 \((2,-1)\) を見つけた）

解答を見る

\(a=3,\ b=5\)、特殊解 \((x_0,y_0)=(2,-1)\) なので、公式にあてはめて \(x = 2+5k,\ \ y = -1-3k\)（\(k\) は整数）

手順のまとめ　手順1　特殊解 \((x_0,y_0)\) を1組見つける（小さい数は目で、大きい数は互除法を逆にたどる）。手順2　\(x=x_0+bk,\ y=y_0-ak\) の形にあてはめる。この \(k\) を動かすと、整数解のすべてが過不足なく出てくる。

STEP 4

文章題への応用

「代金の合計」や「個数」の文章題では、答えは整数（それも多くは正の整数）に限られる。方程式を立てたあと、一般解の \(k\) の範囲を絞り込むところが最後のポイント。

例題　1本150円のボールペンと1本200円のシャープペンシルを、あわせて何本か買って、代金の合計をちょうど2000円にしたい。買い方は何通りあるか。ただし、どちらも1本以上買うものとする。

解答を見る

ボールペンを \(x\) 本、シャープペンシルを \(y\) 本とすると \(150x+200y=2000\) 両辺を \(50\) で割って（係数を小さくする） \(3x+4y=40\) \(x=0\) とすると \(4y=40 \to y=10\)。これが特殊解 \((x_0,y_0)=(0,10)\)。一般解は \(x=0+4k=4k,\ y=10-3k\)（\(k\) は整数）。 \(x\ge1\)（ボールペン1本以上）：\(4k\ge1 \to k\ge1\) \(y\ge1\)（シャープペンシル1本以上）：\(10-3k\ge1 \to k\le3\) よって \(k=1,2,3\) の3通り。それぞれ \((x,y)=(4,7),(8,4),(12,1)\)。買い方は3通り：（ボールペン4本・シャープペン7本）、（8本・4本）、（12本・1本）

文章題のコツ　個数や枚数は0以上の整数（多くは1以上）という制約がつく。一般解を作ったあと、その制約を \(k\) についての不等式に書きかえて範囲を絞り込めば、答えの組がすべて求まる。

練習問題（全16問）

答えを入力して「採点」を押すと○×が出るぞ。分数は「-1/2」、複数の値はコンマ区切りで入力。
わからないときは「解説を見る」で解き方を確認しよう。

基本（1〜7）

ax+by=0型

\(2x+3y=0\) を満たす整数 \(x,y\) を、\(x=\)ア\(\,k,\ y=\)イ\(\,k\)（\(k\) は整数）の形で表せ。ただし、アは正の数とする。

ア　イ

解説を見る

\(2\) と \(3\) は互いに素。公式 \(x=bk,\ y=-ak\) より \(a=2,b=3\) を代入する。ア\(=3\)、イ\(=-2\)

ax+by=0型

\(3x+7y=0\) を満たす整数 \(x,y\) を、\(x=\)ア\(\,k,\ y=\)イ\(\,k\)（\(k\) は整数）の形で表せ。ただし、アは正の数とする。

ア　イ

解説を見る

\(3\) と \(7\) は互いに素。公式より \(a=3,b=7\) を代入する。ア\(=7\)、イ\(=-3\)

特殊解を目で探す

\(2x+3y=1\) について、\(0 \le x_0 < 3\) の範囲にある特殊解 \((x_0,y_0)\) を求めよ。（\(x=0,1,2\) を順に代入して探すとよい）

\(x_0=\) 　\(y_0=\)

解説を見る

\(x=0\)：\(3y=1\) 整数にならない。\(x=1\)：\(2+3y=1 \to 3y=-1\) 整数にならない。\(x=2\)：\(4+3y=1 \to 3y=-3 \to y=-1\) 整数になった。 \(x_0=2,\ y_0=-1\)

特殊解を目で探す

\(5x+2y=1\) について、\(0 \le x_0 < 2\) の範囲にある特殊解 \((x_0,y_0)\) を求めよ。

\(x_0=\) 　\(y_0=\)

解説を見る

\(x=0\)：\(2y=1\) 整数にならない。\(x=1\)：\(5+2y=1 \to 2y=-4 \to y=-2\) 整数になった。 \(x_0=1,\ y_0=-2\)

特殊解から一般解へ

\(3x+2y=1\) の特殊解の1つは \(x_0=1,\ y_0=-1\) である（\(3\cdot1+2\cdot(-1)=1\) を確認せよ）。整数解全体を \(x=1+\)ア\(k,\ y=-1-\)イ\(k\)（\(k\) は整数）の形で表すとき、ア、イを求めよ。

ア　イ

解説を見る

公式 \(x=x_0+bk,\ y=y_0-ak\) で \(a=3,b=2\) を代入する。ア\(=2\)、イ\(=3\)

特殊解から一般解へ

\(2x+5y=3\) の特殊解の1つは \(x_0=4,\ y_0=-1\) である（\(2\cdot4+5\cdot(-1)=3\) を確認せよ）。整数解全体を \(x=4+\)ア\(k,\ y=-1-\)イ\(k\)（\(k\) は整数）の形で表すとき、ア、イを求めよ。

ア　イ

解説を見る

公式 \(x=x_0+bk,\ y=y_0-ak\) で \(a=2,b=5\) を代入する。ア\(=5\)、イ\(=2\)

一般解から組数を数える

\(3x+2y=1\) の整数解は \(x=1+2k,\ y=-1-3k\)（\(k\) は整数）と表される。このうち \(1 \le x \le 19\) を満たす整数の組 \((x,y)\) は何組あるか。

組数

解説を見る

\(1 \le 1+2k \le 19\) を解く。\(0 \le 2k \le 18\) より \(0 \le k \le 9\)。 \(k=0,1,2,\dots,9\) の \(10\) 個。 10組

標準（8〜13）　※パターンは自分で判定

\(5x+3y=2\) の整数解全体を \(x=x_0+\)ア\(k,\ y=y_0-\)イ\(k\)（\(k\) は整数）の形で表したい。\(0 \le x_0 < 3\) の範囲で特殊解 \((x_0,y_0)\) を求め、続けてア、イを求めよ。

\(x_0=\) 　\(y_0=\) 　ア　イ

解説を見る

\(x=0\)：\(3y=2\) 不可。\(x=1\)：\(5+3y=2 \to 3y=-3 \to y=-1\)。特殊解 \((1,-1)\)。公式 \(x=x_0+bk,\ y=y_0-ak\)（\(a=5,b=3\)）にあてはめる。 \(x_0=1,\ y_0=-1\)、ア\(=3\)、イ\(=5\)

\(4x+7y=-1\) の整数解全体を \(x=x_0+\)ア\(k,\ y=y_0-\)イ\(k\)（\(k\) は整数）の形で表したい。\(0 \le x_0 < 7\) の範囲で特殊解 \((x_0,y_0)\) を求め、続けてア、イを求めよ。

\(x_0=\) 　\(y_0=\) 　ア　イ

解説を見る

\(x=0,1,2,3,4\) はいずれも \(7y=-1,-5,-9,-13,-17\) となり整数にならない。 \(x=5\)：\(20+7y=-1 \to 7y=-21 \to y=-3\)。特殊解 \((5,-3)\)。公式（\(a=4,b=7\)）にあてはめる。 \(x_0=5,\ y_0=-3\)、ア\(=7\)、イ\(=4\)

\(2x+5y=3\) の整数解は \(x=4+5k,\ y=-1-2k\)（\(k\) は整数）と表される。このうち \(-10 \le x \le 30\) を満たす整数の組 \((x,y)\) は何組あるか。

組数

解説を見る

\(-10 \le 4+5k \le 30\) を解く。\(-14 \le 5k \le 26\) より \(-2.8 \le k \le 5.2\)。整数 \(k\) は \(-2,-1,0,1,2,3,4,5\) の \(8\) 個。 8組

\(3x+4y=41\) を満たす正の整数の組 \((x,y)\) は何組あるか。

組数

解説を見る

\(0 \le x_0 < 4\) で特殊解を探す。\(x=3\)：\(9+4y=41 \to 4y=32 \to y=8\)。特殊解 \((3,8)\)。一般解は \(x=3+4k,\ y=8-3k\)。 \(x>0\)：\(3+4k>0 \to k\ge0\)。\(y>0\)：\(8-3k>0 \to k\le2\)。 \(k=0,1,2\) の3通り：\((3,8),(7,5),(11,2)\)。 3組

\(4x+6y=7\) を満たす整数 \(x,y\) は存在するか。存在すれば\(1\)、存在しなければ\(0\)を入力せよ。（ヒント：\(4\)と\(6\)の最大公約数に注目）

答え

解説を見る

\(4\) と \(6\) の最大公約数は \(2\)。左辺 \(4x+6y\) は必ず \(2\) の倍数になるが、右辺の \(7\) は \(2\) の倍数ではない。したがって、この式を満たす整数 \(x,y\) は存在しない。 0（存在しない）

\(5x+7y=3\) の整数解全体を \(x=x_0+\)ア\(k,\ y=y_0-\)イ\(k\)（\(k\) は整数）の形で表したい。\(0 \le x_0 < 7\) の範囲で特殊解 \((x_0,y_0)\) を求め、続けてア、イを求めよ。

\(x_0=\) 　\(y_0=\) 　ア　イ

解説を見る

\(x=0\)：\(7y=3\) 不可。\(x=1\)：\(5+7y=3 \to 7y=-2\) 不可。\(x=2\)：\(10+7y=3 \to 7y=-7 \to y=-1\)。特殊解 \((2,-1)\)。公式（\(a=5,b=7\)）にあてはめる。 \(x_0=2,\ y_0=-1\)、ア\(=7\)、イ\(=5\)

挑戦（14〜16）

文章題：代金の組み合わせ

1本120円のボールペンと1本200円のマーカーを、あわせて何本か買って代金の合計をちょうど2000円にしたい。買い方は何通りあるか。ただし、どちらも1本以上買うものとする。

通り数

解説を見る

ボールペン \(x\) 本、マーカー \(y\) 本とすると \(120x+200y=2000\)。両辺を \(40\) で割って \(3x+5y=50\)。 \(x=0\)：\(5y=50 \to y=10\)。特殊解 \((0,10)\)。一般解 \(x=5k,\ y=10-3k\)。 \(x\ge1\)：\(5k\ge1 \to k\ge1\)。\(y\ge1\)：\(10-3k\ge1 \to k\le3\)。 \(k=1,2,3\) の3通り：\((5,7),(10,4),(15,1)\)。 3通り

文章題：個数の組を全部求める

1個80円の消しゴムと1個50円のえんぴつを、あわせて何個か買ったところ、代金の合計がちょうど730円になった。消しゴムの個数として考えられる値をすべて、コンマ区切りで小さい順に答えよ。また、組み合わせは何通りあるか。ただし、どちらも1個以上買うものとする。

消しゴムの個数　組み合わせの数

解説を見る

消しゴム \(x\) 個、えんぴつ \(y\) 個とすると \(80x+50y=730\)。両辺を \(10\) で割って \(8x+5y=73\)。 \(x=1\)：\(8+5y=73 \to 5y=65 \to y=13\)。特殊解 \((1,13)\)。一般解 \(x=1+5k,\ y=13-8k\)。 \(x\ge1\)：\(k\ge0\)。\(y\ge1\)：\(13-8k\ge1 \to k\le1.5 \to k\le1\)。 \(k=0,1\) の2通り：\((1,13),(6,5)\)。消しゴムの個数は \(1\) と \(6\)。消しゴムの個数：1,6　組み合わせの数：2通り

互除法を使って一般解を求める

\(7x+11y=1\) の整数解全体を、ユークリッドの互除法を利用して \(x=x_0+\)ア\(k,\ y=y_0-\)イ\(k\)（\(k\) は整数）の形で求めよ。ただし \(0 \le x_0 < 11\) とする。

\(x_0=\) 　\(y_0=\) 　ア　イ

解説を見る

互除法：\(11=1\times7+4\)、\(7=1\times4+3\)、\(4=1\times3+1\)、\(3=3\times1+0\)。最大公約数は \(1\)。逆にたどる：\(1=4-1\times3\)。\(3=7-1\times4\) を代入して \(1=4-(7-4)=2\times4-7\)。 \(4=11-1\times7\) を代入して \(1=2\times(11-7)-7=2\times11-3\times7\)。つまり \(7\times(-3)+11\times2=1\) より \((x,y)=(-3,2)\) が1つの特殊解。 \(0\le x_0<11\) にするため \(k=1\) 分ずらす：\(x_0=-3+11=8,\ y_0=2-7=-5\)（検算：\(7\times8+11\times(-5)=56-55=1\)）。公式（\(a=7,b=11\)）にあてはめる。 \(x_0=8,\ y_0=-5\)、ア\(=11\)、イ\(=7\)

応用問題（プリント限定）

ここから先はPDF限定の腕試し。3変数への拡張、因数分解を使う不定方程式、本格的な文章題に挑戦しよう。

応1

3変数への拡張

\(x+2y+3z=11\) を満たす正の整数の組 \((x,y,z)\) は何組あるか。（\(z\) の値で場合分けして、\(x+2y=\) の形の2変数の式に帰着させるとよい）

組数

解説を見る

\(z\) を固定して \(x+2y=11-3z\) の正の整数解を数える（3変数のままだと扱いにくいので、1つの文字を固定して2変数の問題に帰着させるのがコツ）。 \(z=1\)：\(x+2y=8\)。\(y=1,2,3\)（\(x=6,4,2\)）の3組。 \(z=2\)：\(x+2y=5\)。\(y=1,2\)（\(x=3,1\)）の2組。 \(z=3\)：\(x+2y=2\)。\(x,y\ge1\) だと最小でも \(x+2y=1+2=3>2\) となり不可能。0組。 \(z\ge4\)：\(11-3z\le -1<0\) となり不可能。合計 \(3+2+0=5\) 組。 5組

応2

因数分解型の不定方程式

\(xy=x+y+3\) を満たす正の整数の組 \((x,y)\) は何組あるか。また、\(x=y\) となる組では \(x\) はいくつか。

組数　\(x=y\) のときの \(x\)

解説を見る

\(xy=x+y+3\) を整理すると \(xy-x-y=3\)。左辺に \(1\) を足すと因数分解できる形になる。 \(xy-x-y+1=4 \ \Longrightarrow\ (x-1)(y-1)=4\) \(x,y\) は正の整数だから \(x-1\ge0,\ y-1\ge0\)。積が \(4\)（正の数）になるには、両方とも正の整数でなければならない（どちらかが \(0\) だと積は \(0\) になってしまう）。よって \(x-1,y-1\) は積が \(4\) になる正の整数の組：\((1,4),(2,2),(4,1)\)。これより \((x,y)=(2,5),(3,3),(5,2)\) の3組。 \(x=y\) となるのは \((3,3)\) のときで \(x=3\)。組数：3組　\(x=y\) のとき \(x=3\)

応3

文章題の本格版：条件つきで最小を探す

ある遊園地の入園料は、おとな1人1200円、こども1人700円である。ある日、おとなとこどもがあわせて何人か入園し、入園料の合計がちょうど33800円になった。おとなの人数がこどもの人数より多くなるような入園者の組み合わせのうち、おとなの人数が最も少ないものを求めよ。

おとな人　こども人

解説を見る

おとな \(a\) 人、こども \(b\) 人とすると \(1200a+700b=33800\)。両辺を \(100\) で割って \(12a+7b=338\)。 \(0\le a_0<7\) の範囲で特殊解を探す。\(a=6\)：\(72+7b=338 \to 7b=266 \to b=38\)。特殊解 \((6,38)\)。一般解は \(a=6+7k,\ b=38-12k\)。 \(a>0\)：\(k\ge0\)。\(b>0\)：\(38-12k>0 \to k<3.17 \to k\le3\)。よって \(k=0,1,2,3\)。 \(k=0\)：\((a,b)=(6,38)\)　\(a<b\) で条件に合わない。 \(k=1\)：\((13,26)\)　\(a<b\) で不適。 \(k=2\)：\((20,14)\)　\(a>b\) で条件に合う。 \(k=3\)：\((27,2)\)　\(a>b\) で条件に合う。条件を満たすうち \(a\) が最小なのは \(k=2\) の \((20,14)\)。検算：\(1200\times20+700\times14=24000+9800=33800\)。おとな20人、こども14人

応4

文章題：組み合わせをすべて求める

50円切手と80円切手を組み合わせて、ちょうど990円分にしたい。買い方は何通りあるか。また、80円切手の枚数として考えられる値を、コンマ区切りで小さい順に答えよ。ただし、どちらも1枚以上使うものとする。

通り数　80円切手の枚数

解説を見る

50円切手 \(x\) 枚、80円切手 \(y\) 枚とすると \(50x+80y=990\)。両辺を \(10\) で割って \(5x+8y=99\)。 \(0\le x_0<8\) の範囲で特殊解を探す。\(x=7\)：\(35+8y=99 \to 8y=64 \to y=8\)。特殊解 \((7,8)\)。一般解は \(x=7+8k,\ y=8-5k\)。 \(x\ge1\)：\(k\ge0\)。\(y\ge1\)：\(8-5k\ge1 \to k\le1.4 \to k\le1\)。 \(k=0\)：\((7,8)\)。\(k=1\)：\((15,3)\)。 2通りで、80円切手の枚数は \(8\) と \(3\)（小さい順に \(3,8\)）。通り数：2通り　80円切手の枚数：3,8

応5

文章題：一方を最大にする

1個150円のりんごと1個90円のみかんを、予算3000円ちょうどで買いたい。りんごの個数をできるだけ多くしたいとき、りんごとみかんはそれぞれ何個か。ただし、どちらも1個以上買うものとする。

りんご個　みかん個

解説を見る

りんご \(x\) 個、みかん \(y\) 個とすると \(150x+90y=3000\)。両辺を \(30\) で割って \(5x+3y=100\)。 \(0\le x_0<3\) の範囲で特殊解を探す。\(x=2\)：\(10+3y=100 \to 3y=90 \to y=30\)。特殊解 \((2,30)\)。一般解は \(x=2+3k,\ y=30-5k\)。 \(x\ge1\)：\(k\ge0\)。\(y\ge1\)：\(30-5k\ge1 \to k\le5.8 \to k\le5\)。よって \(k=0,1,\dots,5\)。りんごの個数 \(x=2+3k\) を最大にするには \(k\) を最大の \(5\) にとればよい。 \(k=5\)：\(x=2+15=17,\ y=30-25=5\)。検算：\(150\times17+90\times5=2550+450=3000\)。りんご17個、みかん5個