用語集
ユークリッドの互除法ゆーくりっどのごじょほう
2 つ の 自然数 の 最大公約数 を 繰り返し 割り算 で 求める アルゴリズム。
2 つ の 自然数 の 最大公約数 を 繰り返し 割り算 で 求める アルゴリズム。
ユークリッドの互除法とは、2つの自然数（）の最大公約数を、 を で割った余り を使って と置き換える操作をくりかえすアルゴリズムです。
| ステップ | 計算 |
|---|---|
| 1 | ： |
| 2 | ： |
| 3 | ： |
| 結果 | 余り の直前の割る数 |
たとえば です。素因数分解しにくい大きな数でも速く求まります。
試験では 大きな数の最大公約数や、 の特殊解を求めるときに使う。余りが になる「直前の割る数」が答え。