ユークリッドの互除法――最大公約数の計算

目次

インタラクティブ

余りが 0 になるまで (a, b) を (b, a mod b) に置き換える

割る自動リセット

a

252

b

105

除法の過程

#	a	b	q	r

「割る」を押して最初の除法を行います。

a = q·b + r, 0 ≤ r < b · gcd(a, b) = gcd(b, r)

入力が大きくなると、約数を一つずつ調べて最大公約数を求めるのは大変である。ユークリッドの互除法は、公約数を保ったまま2数をより小さな組に置き換え、答えが分かるまで繰り返す。ここでは非負整数について$\gcd(0,0)=0$とする。

組を置き換えても最大公約数が変わらない理由

$b>0$である非負整数$a,b$を考える。ユークリッドの除法により、一意な整数$q,r$が存在して

$a=bq+r,\qquad 0\le r<b$

となる。このとき

$\gcd(a,b)=\gcd(b,r)$

である。$a,b$の両方を割る整数は$a-bq=r$も割る。逆に、$b,r$の両方を割る整数は$bq+r=a$も割る。したがって2つの組の公約数は完全に一致し、最大の非負公約数も等しい。

計算例と停止

$252$と$105$を割ると、次のようになる。

$252=2\cdot105+42,\qquad105=2\cdot42+21,\qquad42=2\cdot21+0.$

各段階で最大公約数は変わらないので、

$\gcd(252,105)=\gcd(105,42)=\gcd(42,21)=\gcd(21,0)=21$

である。余りが正なら直前の除数より小さいため、非負の余りは狭義に減少し、必ず0に至る。最後の0でない値が最大公約数となる。すべての非負整数$a$について$\gcd(a,0)=a$であり、この規約には$\gcd(0,0)=0$も含まれる。

2つの入力が正のとき、除算回数は$O(\log\min(a,b))$である。最も遅い場合でも余りは連続するフィボナッチ数ほどの大きさで減るため、2段階ごとに小さい方の入力が一定割合で小さくなる。これは整数の演算回数についての評価であり、任意精度整数のビット演算コストを表すものではない。

反復型C++実装

次の関数が受け取るのは、intで表現できる非負のint値に限る。負数に対するC++の剰余演算に依存しないための事前条件である。非負の最大公約数を返し、gcd(0, 0) == 0となる。

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)$に変わっても最大公約数は変わらない。bが0になったとき、aが答えである。