１次の不定方程式

== １次の不定方程式 ==
○この頁では，

a, b, cが整数であるとき，

１次方程式ax+by=c…(1)

を満たす整数x, yを求める

という形の問題を扱う．（不定方程式の整数解とも呼ばれる．）

○中学校以来習ってきたように(1)の形の方程式はxy平面上の直線を表しており，その直線上の点(x, y)はすべて方程式(1)の解となっているから，解は無限にある．すなわち不定解になる．
　この頁では，x, yは整数という条件を付けたときに(1)の解がどのような式で表されるかを調べる．

この頁では，(1)の形の不定方程式の整数解を求める方法を２つ紹介する．

（Ⅰ）具体的な値をx, yに代入してみて１つの解を見つけ，それを利用して一般解を求める方法
（Ⅱ）x, yのうちで係数が小さい方の変数について解くことを繰り返す方法
（Ⅲ）ユークリッドの互除法を使って１つの解を見つけ，（Ⅰ）に持ち込む方法

（Ⅰ）　具体的な値をx, yに代入してみて１つの解を見つけ，それを利用して一般解を求める方法

　例えば

3x=4y（x, yは整数）…(2)

という問題では，右辺は4の倍数になっているが，左辺の3は4の倍数ではないからxが4の倍数でなければならない．
x=4n（nは整数）
このnを使って，元の方程式を書き直すと
12n=4y
y=3n
となって

x=4n（nは整数）
y=3n

という一般解が得られる．具体的には次のような点になる．

n	...	−3	−2	−1	1	2	3	4	...
x	...	−12	−8	−4	4	8	12	16	...
y	...	−9	−6	−3	3	6	9	12	...

　また，

3(x−1)=4(y+2)（x, yは整数）…(3)

のような問題でも事情は同様であり，平行移動するだけで解ける．

x−1=4n⇒
y+2=3n

x=4n+1（nは整数）
y=3n−2

　右辺に定数項がある場合

3x−4y=5（x, yは整数）…(4)

のような問題では，具体的な値を幾つか代入してみて，１つの特別解を見つけると(3)の形に直して解くことができる．
　例えば，なんとか試行錯誤して
3×3−4×1=5…(4')
という特別解を見つけると

3x−4y=5…(4)

−)3×3−4×1=5…(4')

3(x−3)−4(y−1)=0
3(x−3)=4(y−1)
となって(3)の形の方程式に帰着させることができる．

※ただし，ax+by=cの形の不定方程式が常に解を持つとは限らない．例えば
6x+8y=5
のようにa, bが互いに素でない（最大公約数が１でない）場合，左辺が２の倍数であるのに右辺が２の倍数でないのだから，そのような整数解はない．
　また，
6x+8y=10
のように，3つの係数がいずれも２で割り切れる場合には，両辺を２で割って
3x+4y=5
の形に直して問題を解くものとすればよい．

【要約】
a, bが互いに素な整数であるとき，

１次方程式ax+by=c

を満たす整数解x, yを求めるには，１つの特別解x0, y0を見つけて，辺々引き算をすれば定数項を消去でき，次にa, bが互いに素という性質を使うと一般解が得られる．

【例題１】
　１次方程式5x+3y=1
を満たす整数x, yの一般解を求めてください．

（解答）
x=2, y=−3は方程式を満たすから
5x+3y=1

−)5×2+3×(−3)=1

5(x−2)+3(y+3)=0
5(x−2)=−3(y+3)
左辺は5の倍数で，右辺の−3は5の倍数でないから，y+3が5の倍数でなければならない．
y+3=5n
y=5n−3（nは整数）
このとき
5(x−2)=−15n
x−2=−3n
x=−3n+2
したがって

x=−3n+2（nは整数）…（答）
y=5n−3

※初めに偶然見つけた解が，x=−1, y=2の場合は
5x+3y=1

−)5×(−1)+3×2=1

5(x+1)+3(y−2)=0
5(x+1)=−3(y−2)

x=−3m−1（mは整数）…（答）
y=5m+2
となって見かけは異なるが，n, mがすべての整数をとるとき，これらが表すものは同じになる．原点がずれているだけである．
（n=m+1になっている）

n	...	−2	−1	0	1	2	3	...
x	...	8	5	2	−1	−4	−7	...
y	...	−13	−8	−3	2	7	12	...

m	...	−3	−2	−1	0	1	2	...
x	...	8	5	2	−1	−4	−7	...
y	...	−13	−8	−3	2	7	12	...

【例題２】
　１次方程式3x+4y=30
を満たす正の整数x, yの組をすべて求めてください．

（解答）

初めに整数の範囲で一般解を求めておき，
次にx>0, y>0の条件を満たすnの範囲を絞ります

x=2, y=6は方程式を満たすから
3x+4y=30

−)3×2+4×6=30

3(x−2)+4(y−6)=0
3(x−2)=−4(y−6)
y−6=3n
y=3n+6（nは整数）
このとき

x=−4n+2（nは整数）…（答）
y=3n+6

　次に，x, yは正の整数だから，x>0, y>0となるnの範囲を求める．
x=−4n+2>0より $n\lt \frac{1}{2}$
nは整数だからn≦0
y=3n+6>0よりn>−2
nは整数だからn≧−1
以上から，n=−1, 0
(x, y)=(6, 3), (2, 6)…（答）

各々の問題について，正しいものを選択肢から選んでください．
（※暗算では無理です．計算用紙を使って，計算してから答えてください．）

【問題１】
　１次方程式5x−7y=6
を満たす整数x, yの一般解を求めてください．

（nは整数とする）解説

x=5n+2, y=7n+4 x=7n+4, y=5n+2

x=5n−2, y=7n−4 x=7n−2, y=5n−4

１つの解はx=4, y=2
5(x−4)−7(y−2)=0
5(x−4)=7(y−2)より
x−4=7n, y−2=5n
x=7n+4, y=5n+2…（答）

※初めの１つの解をx=11, y=7などと他に可能な値を選んだ場合，x=7m+11, y=5m+7のような形になるが，m, nがすべての整数をとるときこれらが表しているもの全体は同じ組になる．上記の選択肢の中で，解答となるのは１つだけ

→閉じる←

【問題２】
　１次方程式7x+8y=11
を満たす整数x, yの一般解を求めてください．

（nは整数とする）解説

x=−8n+5, y=7n−3 x=8n+5, y=7n−3

x=8n−5, y=7n+3 x=8n−5, y=7n−3

１つの解はx=5, y=−3
7(x−5)+8(y+3)=0
7(x−5)=−8(y+3)より
x−5=−8n, y+3=7n
x=−8n+5, y=7n−3…（答）

※初めの１つの解をx=−3, y=4などと他に可能な値を選んだ場合，x=−8m−3, y=7m+4のような形になるが，m, nがすべての整数をとるときこれらが表しているもの全体は同じ組になる．上記の選択肢の中で，解答となるのは１つだけ

→閉じる←

【問題３】
　１次方程式5x+8y=100
を満たす正の整数(x, y)の組は何通りありますか．

解説

1 2 3 4 5

１つの解はx=20, y=0
5(x−20)+8y=0
5(x−20)=−8yより
x−20=−8n, y=5n
x=−8n+20, y=5n

次に，x>0, y>0となる条件を求めると

x=−8n+20>0 → $n\lt \frac{20}{8}=2.5$ → n≦2
y=5n>0 → n≧1
ゆえに，n=1, 2
(x, y)=(12, 5), (4, 10) → ２通り…（答）
→閉じる←

【問題４】
　１次方程式11x+13y=200
を満たす正の整数(x, y)の組は何通りありますか．

解説

1 2 3 4 5

１つの解はx=−100, y=100
11(x+100)+13(y−100)=0
11(x+100)=−13(y−100)より
x+100=−13n, y−100=11n
x=−13n−100, y=11n+100

次に，x>0, y>0となる条件を求めると

x=−13n−100>0 → $n\lt -\frac{100}{13}=-7.6..$ → n≦−8
y=11n+100>0 → $n\gt -\frac{100}{11}=-9.0..$ → n≧−9
ゆえに，n=−9, −8
(x, y)=(17, 1), (4, 12) → ２通り…（答）
→閉じる←

（Ⅱ）x, yのうちで係数が小さい方の変数について解くことを繰り返す方法

　とにかく１つの解が見つかる場合は，上で述べた（Ⅰ）の方法で解を求めることができますが，問題によっては１つの特別解が容易に見つからないことがあります．例えば
751x+1163y=1433
のように大きな係数になっている場合は，目の子算（見た目の感じで適当に見当をつける計算方法）で１つの特別解を求めるのは難しい．このような場合は，係数の小さい方の変数について解くことを繰り返す方法（Ⅱ）を利用することができます．
　手順を分かり易くするために，小さな係数の場合から考えてみます．

3x−4y=1…(5)

では，xの係数は3，yの係数は−4,移項すれば4なので，係数が小さい方の変数xについて解くと
$x=\frac{4y+ 1}{3}$
この形にしてから，xは整数でなければならないことを考えると，右辺の分数が約分できて分母がとれなければならないことになります．だから，分子4y+1は3の倍数でなければなりませんが，このままの形で
4y+1=3n…(6)
とおいても，元の問題をすり替えただけで何も解決になっていないことに注意しましょう．というのは(6)式は
3n−4y=1
と同じで，元の問題(5)のxの話をnの話に置き替えただけで一歩も進んでいません．
　そうではなく，（Ⅱ）の方法では「係数の小さい方の変数について解く」ので，右辺で定数項はほっておいて変数yの係数だけを見ると必ず仮分数（分子が分母よりも大きな数）になるのです．
$\frac{4y}{3}$
　ここで $\frac{4}{3}$ という分数は4÷3の割り算を分数で表したものなので，商と余りに分けることができます．
4÷3=1余り1

※どこかの会社の参考書に「分数式は富士の山」と書いてある変形のこと
　商は整数となって独立できるが，余りは分子から逃げられない

すなわち
4=1×3+1
$\frac{4}{3}=1+ \frac{1}{3}$
に注意すると
$x=y+ \frac{y+ 1}{3}$ …(7)
　ここで，xは整数だから
y+1=3n　（nは整数）
y=3n−1
とおける．このとき
$x=(3n-1)+ n=4n-1$
結局

x=4n−1（nは整数）…（答）
y=3n−1

(6)の変形では解くことができずに(7)の変形で解けるポイントは，商と余りに分けて，分子に余りだけを残すところにあります．

【要約】
a, bが互いに素な整数であるとき，

１次方程式ax+by=c

を満たす整数解x, yを求めるには，
（Ａ）　x, yの係数のうち（絶対値が）小さい方の変数について解いた形に直す．
（Ｂ）　右辺の変数の部分を商と余りに分けて，分子を小さくする．
※１回の操作で分子の変数の係数が１にならなければ，以上の操作を繰り返します．

上で（Ⅰ）の方法で解いた［例題１］の問題を，ここでは（Ⅱ）の方法で解いてみます．

【例題１】
　１次方程式5x+3y=1
を満たす整数x, yの一般解を求めてください．

（解答）

負の数を割ったときの余りはどうなるのかなどと難しく考えずに，気楽に正の数で考えるとよい
$\frac{5}{3}=1+ \frac{2}{3}$
だから
$\frac{-5x}{3}=-x-\frac{2x}{3}$

　係数が小さい方の変数yについて解く．
$y=\frac{-5x+ 1}{3}$
　定数項のことは気にせずに，xの部分を商と余りに分ける．
$=-x+ \frac{-2x+ 1}{3}$
yは整数だから，
−2x+1=3n（nは整数）
とおける．

これだけではまだ，xが整数という条件を満たしていない．（例えば，−2x+1=0, 6, ...ではxは整数にならない）
係数の小さい方が１になるまで繰り返す．（必要に応じて整数を表す文字をn,m,p,q,r,..などと増やしていく）

　係数が小さい方の変数xについて解く．
$x=\frac{-3n+ 1}{2}=-n+\frac{-n+ 1}{2}$
　xは整数だから，
−n+1=2m（mは整数）
n=−2m+1
これで解決したので，x, yも順次mで表す．
$x=\frac{-3n+ 1}{2}$
$=\frac{-3(-2m+ 1)+ 1}{2}=3m-1$
$y=\frac{-5x+ 1}{3}$
$=\frac{-5(3m-1)+ 1}{3}=-5m+ 2$

x=3m−1（mは整数）…（答）
y=−5m+2

この結果は上記の（Ⅰ）の答

x=−3n+2（nは整数）…（答）
y=5n−3

と見かけ上は同じではないが，n, mが整数全体の値をとるとき

x=3m−1（mは整数）…（答）
y=−5m+2

が表す値の全体とは一致している．（m=−n+1の関係で，符号と原点がずれているだけ）

【例題３】
　１次方程式5x−17y=13
を満たす整数x, yの一般解を求めてください．

（解答）
$x=\frac{17y+ 13}{5}=3y+ 2 + \frac{2y+ 3}{5}$

定数項は気にしなくてもよいが，この答案のように「ついでに小さくしておく」こともできる．
結果を表す式の原点がずれるだけである

xは整数だから
2y+3=5n（nは整数）
とおける．
$y=\frac{5n-3}{2}=2n+ \frac{n-3}{2}$
yは整数だから
n−3=2m（mは整数）
n=2m+3
とおける．
　以上により，mを用いてx, yを表すと
$y=\frac{5n-3}{2}=\frac{5(2m+ 3)-3}{2}=5m+ 6$
$x=\frac{17y+ 13}{5}=\frac{17(5m+ 6)+ 13}{5}=17m+ 23$

x=17m+23（mは整数）…（答）
y=5m+6

【例題４】
　１次方程式29x+13y=1000
を満たす正の整数解x, yは何通りありますか．

この問題のように，１つの特別解が簡単には見つからないときは，解法（Ⅱ）が有利になります

（解答）
$y=\frac{-29x+ 1000}{13}=-2x+ 76 + \frac{-3x+ 12}{13}$
yは整数だから
−3x+12=13n（nは整数）
とおける．
$x=\frac{-13n+ 12}{3}=-4n + 4 + \frac{-n}{3}$
xは整数だから
n=3m（mは整数）
とおける．
$x=\frac{-13(3m)+ 12}{3}=-13m+ 4$
$y=\frac{-29(-13m + 4)+ 1000}{13}=29m + 68$
　次に，x, yが正の数となる条件を求める．
x=−13m+4>0より $m\lt \frac{4}{13}$
mは整数だからm≦0
y=29m+68>0より $m\gt -\frac{68}{29}=-2.3...$
mは整数だからm≧−2
　したがって，m=−2, −1, 0
正の整数解は(x, y)=(30, 10), (17, 39),(4, 68)の３通り…（答）

【問題５】
　１次方程式71x−11y=43
を満たす正の整数解(x, y)のうちでxの最小値を求めてください．

解説

1 2 3 4 5

$y=\frac{71x-43}{11}=6x-3 + \frac{5x-10}{11}$
yは整数だから
5x−10=11n（nは整数）
とおける．
$x=\frac{11n+ 10}{5}=2n + 2 + \frac{n}{5}$
xは整数だから
n=5m（mは整数）
とおける．
$x=\frac{11(5m)+ 10}{5}=11m+ 2$
$y=\frac{71(11m + 2)-43}{11}=71m + 9$
　次に，x, yが正の数となる条件を求める．
x=11m+2>0より $m\gt -\frac{2}{11}=-0...$
mは整数だからm≧0
y=71m+9>0より $m\gt -\frac{9}{71}=-0....$
mは整数だからm≧0
　したがって，m≧0
　xが最小となるのはm=0のときでx=2 (y=9)…（答）
→閉じる←

【問題６】
　１次方程式94x+29y=500
を満たす正の整数解(x, y)は何通りありますか．

解説

1 2 3 4 5

$y=\frac{-94x+ 500}{29}=-3x+ 17 + \frac{-7x+ 7}{29}$
yは整数だから
−7x+7=29n（nは整数）
とおける．
$x=\frac{-29n+ 7}{7}=-4n + 1 + \frac{-n}{7}$
xは整数だから
n=7m（mは整数）
とおける．
$x=\frac{-29(7m)+ 7}{7}=-29m+ 1$
$y=\frac{-84(-29m + 1)+ 500}{29}=94m + 14$
　次に，x, yが正の数となる条件を求める．
x=−29m+1>0より $m\lt \frac{1}{29}$
mは整数だからm≦0
y=94m+14>0より $m\gt -\frac{14}{94}=-0.14..$
mは整数だからm≧0
　したがって，m=0の1通り…（答）
→閉じる←

（参考）
　上記に述べた解法（Ⅱ）は，ユークリッドの互除法による最大公約数の求め方に対応しています．
　定数項には手を付けずに最後まで引きずっていくものとし，x, yの係数（符号は無視）だけに着目すると
例題１では，(5, 3)組からスタートして，順次大きい方の数を小さい方の数で割った余りに書き換えていくと
(5, 3)→(2, 3)→(2, 1)」→(0, 1)
　この頁の解説では」の所で係数が１の文字が登場したら止めていますが，ユークリッドの互除法の教科書的な説明では，(0, 1)のように余りが0となる変数が登場したら終わりと考えます．
例題３では，
(5, 17)→(5, 2)→(1, 2)」→(1, 0)
例題４では，
(29, 13)→(3, 13)→(3, 1)」→(0, 1)
解法（Ⅱ）の初めに述べた
751x+1163y=1433
の例では
(751,1163)→(751,412)→(339,412)→(339,73)
→(47,73)→(47,26)→(21,26)→(21,5)→(1,5)
の順に係数が登場し８回の操作で解にたどり着きます．

（Ⅲ）　ユークリッドの互除法を使う解き方

(1) 整数a, bの最大公約数をdとするとき，１次不定方程式ax+by=dには，整数解x, yが存在する．
(2) 特に，整数a, bが互いに素であるとき，１次不定方程式ax+by=1には，整数解x, yが存在する．

　ユークリッドの互除法（詳細な解説はこのページ）を使えば，素因数分解を思いつきにくい２つの整数の最大公約数を求めることができます．
　その計算を逆にたどれば，１次不定方程式ax+by=dの１つの解を見つけることができます．

【例１】
19x−17y=1の１つの整数解を求めてください．

（解答）
　ユークリッドの互除法を使って，２つの係数19, 17の最大公約数を求める計算は，次のようになる．

19÷17=1余り2 → 19=17×1+2…(1)
17÷2=8余り1 → 17=2×8+1…(2)
(2÷1=2余り0)

0よりも大きい最後の余りが最大公約数だから，最大公約数は1
そこで(2)を次のように書くと，解の形をしていることが分かる．

17−2×8=1

(1)を用いて，途中経過に登場した余り2を消去して，問題文にある19, 17だけで表すと

17−(19−17×1)×8=1

したがって

19×(−8)+17×(1+8)=1

結局

19×(−8)−17×(−9)=1

したがって，x=−8, y=−9が１つの解…（答）

１つの解が求まると，後は（Ⅰ）の方法により一般解が求まる．

19x−17y=1
− )19×(−8)−17×(−9)=1

19(x+8)−17(y+9)=0
19(x+8)=17(y+9)
x+8=17t, y+9=19t
x=17t−8, y=19t−9

【例２】
527x−403y=31の１つの整数解を求めてください．

（解答）
　ユークリッドの互除法を使って，２つの係数527, 403の最大公約数を求める．

527÷403=1余り124 → 527=403×1+124…(1)
403÷124=3余り31 → 403=124×3+31…(2)
(124÷31=4余り0)

0よりも大きい最後の余りが最大公約数だから，最大公約数は31
この値が，元の不定方程式の右辺になっていることを確認する．
（右辺が最大公約数になっていれば整数解が存在する．そうでなければ整数解は存在しない）
　次に最大公約数を右辺とする最後の式から順にさかのぼって書いて行き，途中経過だけに登場した余りを消去して，問題文にあった係数だけで表す．

403−124×3=31
403−(527−403×1)×3=31
527×(−3)−403×(−1−3)=31
527×(−3)−403×(−4)=31…（答）

したがって，x=−3, y=−4が１つの解

１つの解が求まると，後は（Ⅰ）の方法により一般解が求まる．

527x−403y=31
− )527×(−3)−403×(−4)=31

527(x+3)−403(y+4)=0
17×31×(x+3)=13×31×(y+4)
x+3=13t, y+4=17t
x=13t−3, y=17t−4

【まとめ】
(1) ユークリッドの互除法を使って，2つの係数の最大公約数を求める．
(2) 求めた最大公約数が右辺の定数と一致することを確かめる．（一致しなければ解けない）
(3) ０でない最後の余りの式から逆にさかのぼって，途中経過の余りを消去すると１つの整数解が得られる．

【問題７】

(1)
　１次方程式47x−59y=1の１つの整数解を求めてください．

解説を見る解説を隠す

ユークリッドの互除法を使って，２つの係数47, 59の最大公約数を求める．

59÷47=1余り12 → 59=47×1+12…(1)
47÷12=3余り11 → 47=12×3+11…(2)
12÷11=1余り1 → 12=11×1+1…(3)
(11÷1=11余り0)

0よりも大きい最後の余りが最大公約数だから，最大公約数は1
（この値が，元の不定方程式の右辺になっていることを確認する．）

(3)→12−11=1
(2)→12−(47−12×3)=1
(1)→(59−47)−(47−(59−47)×3)=1
59−47−47+59×3−47×3)=1

したがって
47×(−5)−59×(−4)=1
1つの解はx=−5, y=−4
（※1つの解だから，他に多くの答え方が可能です）

(2)
　１次方程式133x−301y=7の１つの整数解を求めてください．

解説を見る解説を隠す

ユークリッドの互除法を使って，２つの係数133, 301の最大公約数を求める．

301÷133=2余り35 → 301=133×2+35…(1)
133÷35=3余り28 → 133=35×3+28…(2)
35÷28=1余り7 → 35=28×1+7…(3)
(28÷7=4余り0)

0よりも大きい最後の余りが最大公約数だから，最大公約数は7
（この値が，元の不定方程式の右辺になっていることを確認する．）

(3)→35−28=7
(2)→35−(133−35×3)=7
(1)→(301−133×2)−(133−(301−133×2)×3)=7
133×(−9)−301×(−4)=7

1つの解はx=−9, y=−4
（※1つの解だから，他に多くの答え方が可能です）

...（携帯版）メニューに戻る

...（PC版）メニューに戻る

■［個別の頁からの質問に対する回答］[１次不定方程式の整数解について／18.6.16］

【問題２】　１次方程式7x+8y=11 を満たす整数x, yの一般解を求めてください．の問題で、x=－3,y=4を代入した結果、回答がx＝－8n－3,y=7n+4になりました。これも正解でいいのでしょうか？
＝＞［作者］：連絡ありがとう．解答，解説の本文でなく，傍論の参考の部分で定数項の符号が逆になっていましたので，訂正しました．

■［個別の頁からの質問に対する回答］[１次の不定方程式について／18.2.15］

いつも分かりやすい解説をありがとうございます。お世話になっております。問題5の答えについてですが、 m=0の時のyの値は9ではないでしょうか。
＝＞［作者］：連絡ありがとう．入力ミスですのでで訂正しました．

■［個別の頁からの質問に対する回答］[１次の不定方程式について／17.11.27］

問題4の答え違ってませんか？
＝＞［作者］：連絡ありがとう．解答としては違っていませんが，細かな訂正が幾つかありました．

■［個別の頁からの質問に対する回答］[１次不定方程式の整数解について／17.6.4］

整数x, yの一般解を求めてください．というのは整数解全てを求めなさいという言い方もできるのでしょうか？
＝＞［作者］：連絡ありがとう．世間一般の言い方として，それら２つはほとんど同じ意味につかわれていると考えてもよいのですが，この頁では「解が無限個あって書き並べることができない場合に，一般解を求めよ」と述べ，「解が有限個になって書き並べることができる場合に，すべて求めよ」と述べています．

■［個別の頁からの質問に対する回答］[１次不定方程式の整数解について／17.4.25］

問題５の解説について１０行目が間違っているように思います。y=71m+9 では？解答には直接影響しないとは思いますが。
＝＞［作者］：連絡ありがとう．確かに怪しい計算になっていましたので，訂正しました．

■［個別の頁からの質問に対する回答］[１次不定方程式の整数解について／17.2.3］

問題６の解答解説が間違っていませんか。上から１０行目は y=94m+14 になります。 406ではなく406/29のはずです。したがって問題の解答の方も、 -29m+1>0 94m+14>0 を共に満たすmが0のみですから、与式を満たす整数解は1つということになると思います。ちなみに、同じく10行目の、-84という部分がありますが、これは-94の間違いでしょう。検証して下さい。
＝＞［作者］：連絡ありがとう．長い答案になると最後の方で疲れが出てしまうようで，訂正しました．