ユークリッドの互除法

自然数a,bについて
aをbで割ったときの余りをrとすると
aとbの最大公約数は
bとrの最大公約数に等しい

1079と913の最大公約数を求めよ。

割り切れるまで割り算を繰り返し
割り切れたときの割る数が最大公約数になる。

1079 = 913・1 + 166 1079を913で割ると余りが166
913 = 166・5 + 83 913を166で割ると余りが83
166 = 83・2 166は83で割り切れるので最大公約数は83