Question

＾＾

ユークリッド互除法の
｢aとbの最大公約数は、bと余りrの最大公約数に等しい。｣というのは暗記ですか？

Answer 1

Crystal Clear

まあそうです.

以下補足です.理解しなくても構いません.
aとbの最大公約数をgcd(a,b)と書く.
gcd(a,b)=gcd(a-b,b)
が成り立つ.(証明略)

これを繰り返し用いると、
gcd(a,b)
=gcd(a-b,b)
=gcd(a-2b,b)
=gcd(a-3b,b)
=gcd(a-4b,b)
=…
=gcd(a-qb,b) (aをbで割ったときの商をqとした.)
=gcd(r,b)
と示すことができます.