manapedia
ユークリッドの互除法
著作名: OKボーイ
10,000 views
とある自然数aを、自然数bで割った時の余りをrとすると、aとbの最大公約数は、bとrの最大公約数に等しくなります。

この性質を利用して2つの自然数の最大公約数を求める方法を、ユーグリッドの互除法と言います。
例えば

例えば、322259の最大公約数を求めてみましょう。

322=259+63
259=63×4+7

なので、「322」と「259」の最大公約数は、「259」と「63」の最大公約数と等しくなります。また、「259」と「63」の最大公約数は、「63」と「7」の最大公約数と等しくもなります。

63は7で割り切れるので、「7」が322と259の最大公約数です。

このようにして求めることができます。

このテキストを評価してください。
役に立った
う~ん・・・
※テキストの内容に関しては、ご自身の責任のもとご判断頂きますようお願い致します。