ユークリッドの互除法：最大公約数を求める古典的アルゴリズム

変種、性質と計算量

同じ考え方にはいくつかの形がある。減算に基づく方法では、大きい数を小さい数との差で繰り返し置き換える。二進GCD法（スタインのアルゴリズム）は、シフトと減算だけを用いる。このアルゴリズムは効率的であり、除算の回数は入力値の桁数におおむね応じて増加するため、現代の計算で扱われる大きな整数に対しても高速である。

拡張アルゴリズムと応用

拡張ユークリッドの互除法は、ax + by = gcd(a, b) を満たす整数 x、y を求める。この追加の出力は、一次不定方程式の解法、法に関する逆元の計算、多くの暗号処理に不可欠である。たとえば公開鍵方式でも利用される。繰り返し適用すれば、二つを超える数の最大公約数も求められる。

歴史と意義

この手続きは古代数学にさかのぼり、ユークリッドの『原論』には現代のコードではなく論証として現れる。長く使われ続けてきたことは、その基本的な役割を示している。分数の約分、代数構造における計算、ならびにアルゴリズムや数論的応用における効率的な整数演算を支えている。