✨ ベストアンサー ✨
(a,b)=(b,r)という性質を使って最大公約数を求める方法です。
(a,b)=(b,r)を説明します。
まず、(a,b)はaとbの最大公約数を表します。
( gcd(a,b)と書く方が一般的かもしれませんが
省略させていただきます。 ）
たとえば、(15,10)=5 は
15と10の最大公約数が5であることを意味します。
そして、rはaをbで割った時の余りです。
つまり、aとbの最大公約数は、bと余りrの最大公約数に等しいということです。
簡単に証明しておきます。
まず、aをbで割る操作は
a=bq+r（q:商、r:余り）と表せる。
(b,r)でaは割り切れるので
(a,b)>=(b,r)
また、r=a-bqとも表せるので、
同様に
(b,r)>=(a,b)
よって(a,b)=(b,r)
ということで
(5)は
(667,437)=(437,230)
=(230,207)
=(207,23)
=23. (∵207は23で割り切れる)
これがユークリッドの互除法の仕組みです。
( , )という記号を使ったので難しく感じられるかもしれませんが、仕組みは見やすくなるはずです。
ユークリッドの互除法は、割り算を繰り返すことで、小さい数の最大公約数に帰着させるという点でかなり有効な手段です。
ぜひ、納得して使っていただきたいです。
お礼が遅くなってしまいすみません🙇♂️
こんなに詳しく…🤭ありがとうございます！
とてもわかりやすいです！