ユークリッドの互除法
手続き的に記述すると、次のようになる。
入力を m, n (m ≧ n) とする。
n = 0 なら、 m を出力してアルゴリズムを終了する。
m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。
上記の手順は「n, m に対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。
割って余りを取るという操作を最悪でも小さいほうの十進法での桁数の約 5 倍繰り返せば、最大公約数に達する(ラメの定理)。
最大公約数を求めるのに素因数分解すればよいと思うかもしれないが、この定理は(m, n が大きいときには)素因数分解をするよりもユークリッドの互除法によるほうがはるかに速いということを述べている。
実際、計算複雑性理論においては最大公約数を求めることは「容易な問題」として知られており、素因数分解は「困難な問題」であろうと考えられている。 入力された2つの整数のうち小さいほうの整数 n の桁数を d とすれば、ユークリッドの互除法では O(d) 回の除算で最大公約数が求められる。桁数 d は O(log n) なので、ユークリッドの互除法では O(log n) 回の除算で最大公約数が求められる。