Question

まっひー

イコールの意味を崩して説明してほしいです。
全く理解できません。出来るだけ早く知りたいです！

49
第1節 ユークリッドの互除法
練習1 次の2数の最大公約数を求めよ.
(1) 520,112
(2) 1173,2139
◇ 互除法と最大公約数
例によって455 119 の最大公約数は7であるが、 互除法の計算における各割り算において,割り
算の式を書き換えれば
455 = 1193 + 98
98455-119.3
書き換えて
書き換えて
981 + 21
~21=119-98.1
119 =
98 =
214 + 14
書き換えて
1498-21:4
21
=
14.1 +7/
書き換えて
7=21-14.1
となる.したがって
ここがで結ない。
7=21-14･1
= 21 - (98-21.4)・1 = 98(-1) + 21.5
れる意味が
= 98(-1) + (119-981)5119.5 +98(-6))
分からない!!
=119.5- (455-1193)6455 (6) + 119.23
が成り立つ。 故に 455 と 119 の最大公約数7は
7 = 455 (-6) + 119.23
と表すことができる.
一般に次のことが成り立つ.
最大公約数の表現
整数aとbの最大公約数が g のとき
ax+by=g
AND
を満たす整数x, y
が存在する.
練習 2 次の自然数a, bに対して, それらの最大公約数g を求め, 整数 x, y を用いて g = ax + by の形
で表せ.
a=572,6=120
(2) a=182,6=165
例2 整数aとbの最大公約数をg とするとき
ax+by = g
を満たす整数x,yが存在する. いまc をaとbの公約数とすればa=dc, b=bc と表されるから
a d'or I bou