ユークリッドの互除法

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

二つの自然数  a ₁と a ₂の最大公約数（約数）を求めるための一つの方法。a ₁≧a ₂として，次の割り算を実行する。

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は商，余りはなし

最後に余りがなかったならば，この a_{n +1}が最初の 2数 a ₁と a ₂の最大公約数である。（整数論，ユークリッド）