ユークリッドの互除法

最大公約数 (Greatest Common Divisor) を求める方法


二つの自然数を a, b とする。

ただし、 a >= b である。

a / b の剰余 を r とすると、
(式で書くと a = b * q + r である)
 a と b の最大公約数は、 b と r の最大公約数に等しいので、


b / r の剰余を r2 とする、
(式で書くと b = r * q 2+ r2 である)
 b と r の最大公約数は、 r と r2 の最大公約数に等しいので、
...(続く)...

剰余が0になった時の除数=分母が、最大公約数である。


例

1071 と 1029 の最大公約数を求める。

• 1071 を 1029 で割った余りは 42
• 1029 を 42 で割った余りは 21
• 42 を 21 で割った余りは 0

よって、最大公約数は21である。

補足

二つの自然数の代わりに、二つの数式としてもよい。

他の最大公約数を求める計算方法には、素因数分解が知られているが、
ユークリッドの互除法がはるかに早く求まる。（ラメの定理）

連分数展開で表現することもできる、例えば例は、

 数式作成デモ