更新日2022/05/01

ユークリッドの互除法

自然数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

次の2つの整数の最大公約数を, 互除法を用いて求めよ。
603, 46967 1088, 45917 864, 40527 972, 58812
Copyright©2016 SyuwaGakuin AllRightsReserved