actions

ユークリッドの互除法

2019/4/27/ (土) 23:08時点におけるAdmin (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)

ユークリッドの互除法(ユークリッドのごじょほう、: 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の最大公約数である。(整数論ユークリッド