Question

のんの

ユークリッドの互除法の計算の仕方を教えてください！

282 1) 24と19 に互除法の計算を行うと, 次の

ようになる。
24ニ19・1+5 移項すると 5=24一19・1

19=5・3十4  移項すると 4=19一5・3
5=4:1+1 移項すると 1=5一4<1
よって ]テ5一4・1
=5一(19一5・3)・1
=(24 19・1)・4二19・(1)
=24・4 十19・(一5)
したがって, 求める整数 x。 yの組の 1 つは
 ャニー5

Answer 1

ねけう

まず、24を19で割る
1あまり5と分かる
なので、24=19×1+5 と書ける
次は、19を5で割る
3あまり4と分かる
なので、19=5×3+4 と書ける
次は、5を4で割る
1あまり1と分かる
なので、5=4×1+1
次は4÷1を考えたいが、あまりが0になるので考えない

整数a,bに対して、ある整数c,d (b>d)が存在して
a=b×c+d
と書け、このとき、aとbのGCDはbとdのGCDに等しいことが知られています
これを繰り返し使ったのがユークリッドの互除法です