ユークリッドの互除法 - Wikipedia252と105のためのユークリッドの互除法のアニメーション。 クロスバーは、最大公約数（GCD）である21の倍数を表す。 それぞれのステップにおいて、1つの番号がゼロになるまで、より少ない数はより大きな数から引かれる。 残りの数は、GCD。 ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 明示的に記述された最古のアルゴリズムと
