ユークリッドの互除法は、2つの非負整数を、共通の約数を保ったままより小さい組へと繰り返し置き換え、最大公約数（gcd）を求める方法である。
基本となる等式
$b>0$である非負整数$a,b$を考える。ユークリッドの除法により、次を満たす整数$q,r$が一意に存在する。
\[a=bq+r,\qquad 0\le r<b.\]重要な性質は次の等式である。
\[\gcd(a,b)=\gcd(b,r).\]これを証明するため、2つの組の共通の約数を比較する。整数$d$が$a$と$b$の両方を割り切るなら、差$a-bq=r$も割り切るため、$d$は$b$と$r$の両方を割り切る。逆に、$d$が$b$と$r$の両方を割り切るなら、$bq+r=a$も割り切るため、$a$と$b$の両方を割り切る。したがって、$(a,b)$と$(b,r)$の共通の約数は完全に一致し、特に最大公約数も等しい。
繰り返し適用する
$r>0$なら、$(b,r)$に同じ等式を適用する。各余りは直前の除数より小さい非負整数なので、余りは狭義に減少し、やがて0になる。例えば、
\[252=105\cdot2+42,\qquad 105=42\cdot2+21,\qquad 42=21\cdot2+0.\]よって、
\[\gcd(252,105)=\gcd(105,42)=\gcd(42,21)=\gcd(21,0)=21.\]非負整数$a$について、終了条件は$\gcd(a,0)=a$である。すべての非負整数は0を割り切り、$a$と0の最大の非負公約数は$a$だからである。この定義では$\gcd(0,0)=0$となる。したがって、最初の入力で$b=0$の場合もそのまま処理できる。
反復型C++実装
次の関数が受け取るのは非負のint値に限る。2つの引数がともに非負で、intで表現できることを事前条件とし、$\gcd(0,0)=0$の場合も含めて最大公約数を返す。
1
2
3
4
5
6
7
8
9
int gcd(int a, int b) {
// 事前条件: a >= 0 かつ b >= 0。
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
各反復でremainderは$a=bq+r$の$r$に当たるため、組が$(b,r)$に変わっても$\gcd(a,b)$は変わらない。bが0になった時点でaが最大公約数である。