ユークリッドの互除法
提供: miniwiki
ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）
二つの自然数 a 1と a 2の最大公約数（約数）を求めるための一つの方法。a 1≧a 2として，次の割り算を実行する。
| a 1＝a 2 q 1＋a 3 | q 1は商，a 3は余り | |
| a 2＝a 3 q 2＋a 4 | q 2は商，a 4は余り | |
| ………… | ………… | |
| an -1＝a n qn -1＋an +1 | q n -1は商，a n +1は余り | |
| a n＝a n＋1 q n | q nは商，余りはなし |
最後に余りがなかったならば，この an +1が最初の 2数 a 1と a 2の最大公約数である。（整数論，ユークリッド）