5
10
15
20
1次不定方程式とユークリッドの互除法
aとbが互いに素であるとき, 1次不定方程式 ax+by=1の整数解は,
ユークリッドの互除法を用いて求めることができる。
例題
4 1次不定方程式 163x+78y=1の1組の整数解を求めよ。
解 ユークリッドの互除法により, 163 78 の最大公約数を調べる。
163 = 782+7
③ ④ に代入すると
1次不定方程式の整数解
78- (163-78・2)・11=1
78=7.11+1
7=1.7
よって, 163 78 は, 最大公約数が1であるから、 互いに素である。
ここで, ①, ② において、余り以外の項を移項すると
163-782=7
78-7・11=1
左辺を変形すると
・・・・・
どうしてこのようになるのか
①
2
163(11)+78・23=1
したがって, 1次不定方程式 163x+78y=1の1組の整数解は
x=-11
y = 23
③3③3