本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため,多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
ユークリッドの互除法
自然数
このとき
となる。すなわち,
ユークリッドの互除法の肝は,素因数分解を行わなくても二つの整数の最大公約数を求めることができるアルゴリズムを確立した点にあります。このアルゴリズムは,紀元前300年頃にユークリッドによって書かれたとされている「ユークリッド原論」で記述されています。
証明
余りの性質から
となるため,
が得られます。
コメント