本例題T22 1次不定方程式の整数解(2)
次の方程式の整数解をすべて求めよ。
(1) 3x-7y=1
(2) 22x+37y=2
b.423 基本事項2,基本 121
CHARTO
基
OLUTION
現
1次不定方程式 ax+by=c の整数解
(1) 係数が小さいから, 1組の解が見つけやすい。
ax+by=1 の整数解 x=p, y=q を互除法を用いて求める。
② ap+bq=1 から, 両辺にcを掛けて
の手順で進める。最後の式と ax+by=c から a(x-cp)+6(y-can
a(cp)+6(cg)=c
解答
3x-7y=1
x=5, y=2 は, ① の整数解の1つである。
よって
3·5-7·2=1
| O-2 から
3(x-5)-7(y-2)30
すなわち
3(x-5)=7(y-2)
3
3と7は互いに素であるから,③より
の断りは重要。
x-5が7の倍数と
から x-5=7k
③ に代入すると
3-7k=7(y-2)
x-5=7k, y-2=3k (kは整数)
したがって, ①のすべての整数解は
x=7k+5, y=3k+2 (kは整数)
22x+37y=2
x=-5, y=3 は, 22x+37y=1 の整数解の1つである。
22-(-5)+37·3=1
の
x=-5, y=3 の求め
よって
は,下のini」を参照
両辺に2を掛けると
四 0-2 から
22.(-10)+37·6=2
22(x+10)+37(y-6)=0
22(x+10)=-37yー6)
22 と37 は互いに素であるから,、③より
すなわち
3)
の断りは重要、
x+10=37k,"yー6=-22k (kは整数)
したがって, ① のすべての整数解は
x=37k-10, =-22k+6 (kは整数)
22 と 37 に互除法を用いると
22=15·1+7-→7=22-15·1. 15=7-2+1-→1315-72
inf.
37=22·1+15-
15=37-22-1.
よって
1=15-7-2=15-
5:3