manapedia
ユークリッドの互除法
著作名: OKボーイ
8,049 views
マナペディア(manapedia)とは、中学校・高等学校で勉強する科目に特化した、マナビを共有し合う場です。たくさんのテキストの中からあなたにあったマナビを探したり、あなたが学習・勉強してきたマナビを形に残したりすることができます。テキストの内容に関しては、他の参考文献をご覧になり、ご自身の責任のもとご判断・ご利用頂きますようお願い致します。

とある自然数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の最大公約数です。

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

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