基本例 136 1次不定方程式の整数解 (2)
...
ax+by=c
00000
次の方程式の整数解をすべて求めよ。
(1) 7x+6y=40
指針
(2)37x-90y=4
基本 135 140
① ax+by=cの整数解 1組の解(p, g) を見つけて a(x-p)+b(3-4)=0
が第一の方針。 しかし (1) は比較的見つけやすいが、(2)は簡単に見つからない。 そこ
で,(2)では,次の方針による解答を考えてみよう。
① a ともの最大公約数を 互除法によって求め、その計算過程を逆にたどる。
・・・・・ 特に, 1=ap+bg の形が導かれたら 両辺をc倍して a(cp)+b(cg) =c
2 (絶対値が) 大きい方の係数を小さい方の係数で割ることによって, 係数を小
さくし (本書では係数下げと呼ぶ)。 1組の解を見つけやすくする。
なお,検討として, 3 合同式を利用する 解法も取り上げた。
解がすぐに見つからなければ
CHART 不定方程式の整数解
互除法 または 係数下げ
(1) x=4,y=2は7x+6y=40の整数解の1つである。
解答
ゆえに、 方程式は
すなわち
7(x-4)+6(y-2)=0
<7x+6y=40 から
7x=2(20-3y)
7(x-4)=-6(y-2)
7と6は互いに素であるから, kを整数として
x-4=6k, -(y-2)=7k
と表される。
よって, 解は x=6k+4,y=-7k+2(kは整数)
よって, xは2の倍数で
ある。 このようにして、
方程式を満たす整数解を
見つける目安を付けると
よい。
