Question

ひな

ユークリッドの互除法についてです。
aとb、bとcが互いに素になる理由が分からないので教えてほしいです。

ここで11242の最大公約数をg とすると,
112=ag, 42=bg (a, b は互いに素)
と表せるので、 ①に代入すると, (a-26)g=28
よって, 28=cg と表せ, bとcは互いに素だから~~とから
(この証明は背理法を用います。
gは42と28の最大公約数といえます。
)
この事実は一般的には,ポイントのように表すことができます.
そこで,もう一度同じことをくりかえすとも!
42=28×1+14 より gは14と28の最大公約数といえます。
もう一度、くりかえすと
28142･･･0
余りが0になったときのわる数14 が最大公約数です.
|28=14.2, 14=14.1