→ 携帯版は別頁
.
== 1次不定方程式の整数解 ==

○この頁では,
a, b, cが整数であるとき,
1次方程式ax+by=c…(1)
を満たす整数x, yを求めよ
という形の問題を扱う.(不定方程式の整数解とも呼ばれる.)

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

この頁では,(1)の形の不定方程式の整数解を求める方法を2つ紹介する.
(T) 具体的な値をx, yに代入してみて1つの解を見つけ,それを利用して一般解を求める方法
(U) x, yのうちで係数が小さい方の変数について解くことを繰り返す方法

(T)
 例えば
3x=4yx, yは整数)…(2)
という問題では,右辺は4の倍数になっているが,左辺の34の倍数ではないからx4の倍数でなければならない.
x=4nnは整数)
このnを使って,元の方程式を書き直すと
12n=4y
y=3n
となって
x=4nnは整数)
y=3n

という一般解が得られる.具体的には次のような点になる.
n...−3−2−101234...
x...−12−8−40481216...
y...−9−6−3036912...
 また,
3(x−1)=4(y+2)x, yは整数)…(3)
のような問題でも事情は同様であり,平行移動するだけで解ける.
x−1=4n
y+2=3n
x=4n+1nは整数)
y=3n−2

 右辺に定数項がある場合
3x−4y=5x, yは整数)…(4)
のような問題では,具体的な値を幾つか代入してみて,1つの特別解を見つけると(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が互いに素でない(最大公約数が1でない)場合,左辺が2の倍数であるのに右辺が2の倍数でないのだから,そのような整数解はない.
 また,
6x+8y=10
のように,3つの係数がいずれも2で割り切れる場合には,両辺を2で割って
3x+4y=5
の形に直して問題を解くものとすればよい.

【要約】
a, bが互いに素な整数であるとき,
1次方程式ax+by=c
を満たす整数解x, yを求めるには,1つの特別解x0, y0を見つけて,辺々引き算をすれば定数項を消去でき,次にa, bが互いに素という性質を使うと一般解が得られる.
→右上に続く
【例題1】
 1次方程式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の倍数で,右辺の−35の倍数でないから,y+35の倍数でなければならない.
y+3=5n
y=5n−3nは整数)
このとき
5(x−2)=−15n
x−2=−3n
x=−3n+2
したがって
x=−3n+2nは整数)…(答)
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−1mは整数)…(答)
y=5m+2
となって見かけは異なるが,n, mがすべての整数をとるとき,これらが表すものは同じになる.原点がずれているだけである.
n=m+1になっている)
n...−2−10123...
x...852−1−4−7...
y...−13−8−32712...
m...−3−2−1012...
x...852−1−4−7...
y...−13−8−32712...
【例題2】
 1次方程式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+6nは整数)
このとき
x=−4n+2nは整数)…(答)
y=3n+6

 次に,x, yは正の整数だから,x>0, y>0となるnの範囲を求める.
x=−4n+2>0より
nは整数だからn≦0
y=3n+6>0よりn>−2
nは整数だからn≧−1
以上から,n=−1, 0
(x, y)=(6, 3), (2, 6)…(答)

各々の問題について,正しいものを選択肢から選んでください.
(※暗算では無理です.計算用紙を使って,計算してから答えてください.)
【問題1】
 1次方程式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
【問題2】
 1次方程式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
【問題3】
 1次方程式5x+8y=100
を満たす正の整数(x, y)の組は何通りありますか.


1 2 3 4 5
【問題4】
 1次方程式11x+13y=200
を満たす正の整数(x, y)の組は何通りありますか.


1 2 3 4 5

.
 とにかく1つの解が見つかる場合は,上で述べた(T)の方法で解を求めることができますが,問題によっては1つの特別解が容易に見つからないことがあります.例えば
751x+1163y=1433
のように大きな係数になっている場合は,目の子算(見た目の感じで適当に見当をつける計算方法)で1つの特別解を求めるのは難しい.このような場合は,係数の小さい方の変数について解くことを繰り返す方法(U)を利用することができます.
 手順を分かり易くするために,小さな係数の場合から考えてみます.
3x−4y=1…(5)
では,xの係数は3yの係数は−4,移項すれば4なので,係数が小さい方の変数xについて解くと

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

 ここでという分数は4÷3の割り算を分数で表したものなので,商と余りに分けることができます.
4÷3=1余り1
※どこかの会社の参考書に「分数式は富士の山」と書いてある変形のこと
 商は整数となって独立できるが,余りは分子から逃げられない
すなわち
4=1×3+1

に注意すると
…(7)
 ここで,xは整数だから
y+1=3n (nは整数)
y=3n−1
とおける.このとき

結局
x=4n−1nは整数)…(答)
y=3n−1

(6)の変形では解くことができずに(7)の変形で解けるポイントは,商と余りに分けて,分子に余りだけを残すところにあります.
【要約】
a, bが互いに素な整数であるとき,
1次方程式ax+by=c
を満たす整数解x, yを求めるには,
(A) x, yの係数のうち(絶対値が)小さい方の変数について解いた形に直す.
(B) 右辺の変数の部分を商と余りに分けて,分子を小さくする.
※1回の操作で分子の変数の係数が1にならなければ,以上の操作を繰り返します.
上で(T)の方法で解いた[例題1]の問題を,ここでは(U)の方法で解いてみます.
【例題1】
 1次方程式5x+3y=1
を満たす整数x, yの一般解を求めてください.
(解答)
負の数を割ったときの余りはどうなるのかなどと難しく考えずに,気楽に正の数で考えるとよい

だから

 係数が小さい方の変数yについて解く.

 定数項のことは気にせずに,xの部分を商と余りに分ける.

yは整数だから,
−2x+1=3nnは整数)
とおける.
これだけではまだ,xが整数という条件を満たしていない.(例えば,−2x+1=0, 6, ...ではxは整数にならない)
係数の小さい方が1になるまで繰り返す.(必要に応じて整数を表す文字をn,m,p,q,r,..などと増やしていく)
→右上に続く
 係数が小さい方の変数xについて解く.

 xは整数だから,
−n+1=2mmは整数)
n=−2m+1
これで解決したので,x, yも順次mで表す.




x=3m−1mは整数)…(答)
y=−5m+2
この結果は上記の(T)の答
x=−3n+2nは整数)…(答)
y=5n−3
と見かけ上は同じではないが,n, mが整数全体の値をとるとき
x=3m−1mは整数)…(答)
y=−5m+2
が表す値の全体とは一致している.(m=−n+1の関係で,符号と原点がずれているだけ)
【例題3】
 1次方程式5x−17y=13
を満たす整数x, yの一般解を求めてください.
(解答)

定数項は気にしなくてもよいが,この答案のように「ついでに小さくしておく」こともできる.
結果を表す式の原点がずれるだけである
xは整数だから
2y+3=5nnは整数)
とおける.

yは整数だから
n−3=2mmは整数)
n=2m+3
とおける.
 以上により,mを用いてx, yを表すと


x=5m+6mは整数)…(答)
y=17m+23
【例題4】
 1次方程式29x+13y=1000
を満たす正の整数解x, yは何通りありますか.
この問題のように,1つの特別解が簡単には見つからないときは,解法(U)が有利になります
(解答)

yは整数だから
−3x+12=13nnは整数)
とおける.

xは整数だから
n=3mmは整数)
とおける.


 次に,x, yが正の数となる条件を求める.
x=−13m+4>0より
mは整数だからm≦0
y=29m+68>0より
mは整数だからm≧−2
 したがって,m=−2, −1, 0
正の整数解は(x, y)=(30, 10), (17, 39),(4, 68)の3通り…(答)

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


1 2 3 4 5
【問題6】
 1次方程式94x+29y=500
を満たす正の整数解(x, y)は何通りありますか.


1 2 3 4 5

.
(参考)
 上記に述べた解法(U)は,ユークリッドの互除法による最大公約数の求め方に対応しています.
 定数項には手を付けずに最後まで引きずっていくものとし,x, yの係数(符号は無視)だけに着目すると
例題1では,(5, 3)組からスタートして,順次大きい方の数を小さい方の数で割った余りに書き換えていくと
(5, 3)→(2, 3)→(2, 1)」→(0, 1)
 この頁の解説では」の所で係数が1の文字が登場したら止めていますが,ユークリッドの互除法の教科書的な説明では,(0, 1)のように余りが0となる変数が登場したら終わりと考えます.
例題3では,
(5, 17)→(5, 2)→(1, 2)」→(1, 0)
例題4では,
(29, 13)→(3, 13)→(3, 1)」→(0, 1)
解法(U)の初めに述べた
751x+1163y=1433
の例では
(751,1163)→(751,412)→(339,412)→(339,73)→(47,73)→(47,26)→(21,26)→(21,5)→(1,5)
の順に係数が登場し8回の操作で解にたどり着きます.
(そのまま出せば通常の時間内に問題が解けないのでその問題は実際には解いていません)
...メニューに戻る
■[個別の頁からの質問に対する回答][1次不定方程式の整数解について/17.6.4]
整数x, yの一般解を求めてください.というのは整数解全てを求めなさいという言い方もできるのでしょうか?
=>[作者]:連絡ありがとう.世間一般の言い方として,それら2つはほとんど同じ意味につかわれていると考えてもよいのですが,この頁では「解が無限個あって書き並べることができない場合に,一般解を求めよ」と述べ,「解が有限個になって書き並べることができる場合に,すべて求めよ」と述べています.
■[個別の頁からの質問に対する回答][1次不定方程式の整数解について/17.4.25]
問題5の解説について 10行目が間違っているように思います。y=71m+9 では? 解答には直接影響しないとは思いますが。
=>[作者]:連絡ありがとう.確かに怪しい計算になっていましたので,訂正しました.
■[個別の頁からの質問に対する回答][1次不定方程式の整数解について/17.2.3]
問題6の解答解説が間違っていませんか。 上から10行目は y=94m+14 になります。 406ではなく406/29のはずです。 したがって問題の解答の方も、 -29m+1>0 94m+14>0 を共に満たすmが0のみですから、与式を満たす整数解は1つということになると思います。 ちなみに、同じく10行目の、-84という部分がありますが、これは-94の間違いでしょう。 検証して下さい。
=>[作者]:連絡ありがとう.長い答案になると最後の方で疲れが出てしまうようで,訂正しました.