ユークリッドの互除法

ユークリッドの互除法は、2つの整数の最大公約数を求める方法である。 その基本アルゴリズムは、次のようなものである。 「2つの整数m, nの最大公約数は、その2つの数の差と小さい方の数との最大公約数を 求めることであり、この操作を2つの数字が等しくなるまで繰り返し、 等しくなったときの数が最大公約数である」

すなわち、整数m,nの最大公約数を求める関数をgcd(m,n)とすると、以下のように 記述することができる。

$gcd(m, n) = \left\{ \begin{array}{ll} gcd(m-n, n ) &if\;\; m > n \\ gcd(m , n-m) &if\;\; m < n \\ m &if\;\; m == n \end{array}\right.$