508
基本 例題128 1次不定方程式の整数解 (2)
ax+by=c
次の方程式の整数解をすべて求めよ。
4(1) 7x+6y=40
メ (2) 37x-90y=4
基本 127
演習131
指針>O ax+by=c の整数解
が第一の方針。 の
ない。そこで,(2)では, 次の方針による解答を考えてみよう。
1 aとbの最大公約数を 互除法によって求め.その計算過程を逆にたどる。
1組の解(b, q) を見つけて a(xー)+6(y-q)=0
しかし,(1)は比較的見つけやすいが,(2) は簡単に見つから
…特に、1=ap+bq の形が導かれたら,両辺をc倍して a(cp)+6(cq)=c
2 係数を小さくして (本書では 係数下げ と呼ぶ), 1組の解を見つけやすくする。
なお, 検討 として, 3 合同式を利用する
解法も取り上げた。 味
ージ糖
解がすぐに見つからなければ
互除法 または係数下げ
CHART 不定方程式の整数解
うにと
解答
(1) x=4, y=2 は7x+6y=40 の整数解の1つである。
7(x-4)+6(y-2)=0
7(x-4)=D-6(y-2)
7と6は互いに素であるから, kを整数として
(7x+6y=40 から
7x=2(20-3y)
よって, x は2の倍数であ
る。このようにして, 方程
式を満たす整数解を見つけ
る目安を付けるとよい。
ゆえに,方程式は
すなわち
x-4=6k, -(y-2)=7k
と表される。
x=6k+4, y=-7k+2(k は整数)
よって,解は