Check
989 と 899 の最大公約数は
ア
であり,方程式 989x+899y=|
の整数
ア
解の一つは, x=イウ
エオ]である。
ソ=
解答
989 = 899·1+90
899 = 90-9+89
90 = 89-1+1 ①
余りが1になった時点で最大公約数が
1であるとわかるので, 慣れていれば
割り算をので終了すればよい。
89 = 1·89+0
よって, 989 と 899 の最大公約数は1である。
また,①から変形を繰り返すと
ユークリッドの互除法の計算を逆にた
どって「余りを, 割られる数と割る数
と商の式に置き換える」 操作を繰り返
1= 90-89-1
= 90-(899-90·9)·1
す。
= 90·10-899·1
= (989-899-1)·10-899·1
989·10+899·(-11)
方程式 989x+899y = 1 の整数解の1つは x310, y=-11
よって、