ユークリッドの互除法

提供: miniwiki
移動先:案内検索

ユークリッドの互除法(ユークリッドのごじょほう、: Euclidean Algorithm

二つの自然数  a 1a 2の最大公約数(約数)を求めるための一つの方法。a 1a 2として,次の割り算を実行する。

a 1a 2 q 1a 3   q 1は商,a 3は余り
a 2a 3 q 2a 4   q 2は商,a 4は余り
…………   …………
an -1a n qn -1an +1   q n -1は商,a n +1は余り
a na n+1 q n   q nは商,余りはなし

最後に余りがなかったならば,この an +1が最初の 2数 a 1a 2の最大公約数である。(整数論ユークリッド