Euclidの互除法
概要
Euclidの互除法（Euclidean algorithm）とは、整数 $a$ と正の整数 $b$ の最大公約数を、$a$ を $b$ で割り、次に割った数を余りで割る、ことを余りが $0$ になるまで繰り返して求める手続きであり、最後の $0$ でない余りが $\gcd(a,b)$ である。たとえば $252=2\cdot105+42$、$105=2\cdot42+21$、$42=2\cdot21$ から $\gcd(252,105)=21$ を得る。余りが真に減るので必ず止まり、割り算の回数は $b$ の 10 進桁数の 5 倍を超えない（Lamé の定理）。最悪の入力は隣り合う Fibonacci 数である。途中の計算を記録すると $ax+by=\gcd(a,b)$ となる整数 $x,y$ が求まる（拡張互除法）。実数 $\sqrt2$ と $1$ に同じ操作をすると止まらない。
前提知識: 整数, 約数, 除法の原理, 最大公約数
$252$ と $105$ の最大公約数を、どちらも素因数分解せずに求めてみる。大きいほうを小さいほうで割り、次は割った数を余りで割る、ということを余りが $0$ になるまで繰り返す。
$$
252=2\cdot105+42,\qquad 105=2\cdot42+21,\qquad 42=2\cdot21+0
$$
最後の $0$ でない余り $21$ が答であり、$\gcd(252,105)=21$ である（実際 $252=12\cdot21$、$105=5\cdot21$）。割り算は 3 回で済んだ。同じ方法で $\gcd(89,55)$ を求めると、最後の 1 回を除いて商が $1$ のまま余りが $34,21,13,8,5,3,2,1$ と Fibonacci 数をさかのぼり、9 回の割り算の末に答 $1$ が出る。この「隣り合う Fibonacci 数」が、数の大きさの割にいちばん手間のかかる入力である（thm-euclid-alg-lame）。
このように、割り算を繰り返して 2 つの整数の最大公約数を求める手続きを Euclidの互除法 という。Euclid『原論』第 VII 巻の命題 1・2 に現れる、記録に残る最古のアルゴリズムの 1 つである。素因数分解を使わないので、何百桁の数でもすぐに計算でき、手数は小さいほうの数の桁数の 5 倍を超えない。計算の途中経過を記録すると Bézoutの等式 $ax+by=\gcd(a,b)$ の係数が得られ、合同式の逆元、連分数展開、RSA暗号の鍵の計算など、初等整数論の計算の多くがこの手続きの上に立っている。
定義
整数 $a,b$ の少なくとも一方が $0$ でないとき、$a$ と $b$ をともに割り切る整数（公約数）のうち最大のものを $\gcd(a,b)$ と書く。$\gcd(a,0)=|a|$ であり、$\gcd(a,b)=\gcd(|a|,|b|)$ である（定義と基本性質は 最大公約数 の記事を参照）。
$a$ を整数、$b$ を正の整数とする。$r_0:=a$、$r_1:=b$ とおき、$i=1,2,\dots$ の順に、$r_i\neq0$ である限り $r_{i-1}$ を $r_i$ で割って
$$
r_{i-1}=q_ir_i+r_{i+1},\qquad 0\le r_{i+1}< r_i
$$
を満たす整数 $q_i,r_{i+1}$ を定める（除法の原理）。初めて $r_{n+1}=0$ となったところで止め、$r_n$ を出力する。この手続きを Euclidの互除法（Euclidean algorithm、Euclid's algorithm）といい、$q_1,q_2,\dots$ を商の列、$r_0,r_1,r_2,\dots$ を余りの列、$n$ を割り算の回数という。
$b=0$ の場合は割り算をせずに $\gcd(a,0)=|a|$ とし、$b<0$ の場合は $\gcd(a,b)=\gcd(a,-b)$ なので $-b$ を使えばよい。$0\le a< b$ のときは最初の割り算が $a=0\cdot b+a$ となり、$r_2=a$ で 2 つの数が入れ替わるだけである。したがって実質的には $a\ge b>0$ の場合を考えれば足りる。
各段の割り算 $r_{i-1}=q_ir_i+r_{i+1}$ は、「$r_{i-1}$ から $r_i$ を引けるだけ引く」ことを $q_i$ 回まとめて行ったものである。Euclid の原典は割り算ではなく、この「大きいほうから小さいほうを引き続ける」形で書かれている（rem-euclid-alg-history）。
直感
縦 $105$、横 $252$ の長方形を、できるだけ大きな正方形で切り取っていく。まず一辺 $105$ の正方形が $2$ 枚取れ、横 $42$・縦 $105$ の長方形が残る。次に一辺 $42$ の正方形が $2$ 枚取れて $42\times21$ の長方形が残り、最後に一辺 $21$ の正方形 $2$ 枚でちょうど埋まる。各段で取れる正方形の枚数が商 $q_i=2,2,2$ であり、最後の正方形の一辺が最大公約数 $21$ である。
一辺 $21$ の正方形が元の長方形を隙間なく敷き詰めることは、切り取りを逆にたどれば分かる。$42\times21$ は $21$ の正方形 $2$ 枚であり、$42\times105$ の長方形はそれに一辺 $42$ の正方形（$21$ の正方形 $4$ 枚）を 2 枚足したものであり、以下同様である。逆に、一辺が整数 $s$ の正方形が元の長方形を隙間なく敷き詰めるなら、縦横それぞれに $s$ がちょうど何枚か並ぶので $s$ は $252$ と $105$ の公約数であり、したがって $42=252-2\cdot105$ も $21=105-2\cdot42$ も割り切る。これが thm-euclid-alg-correct の内容を図で見たものである。
長方形の辺の比 $252/105$ で言えば、この操作は比の連分数展開 $\frac{252}{105}=2+\cfrac{1}{2+\cfrac{1}{2}}$ を求めることと同じであり、商の列 $2,2,2$ が部分商になる。辺の比が無理数なら、この操作は永遠に終わらない（ex-euclid-alg-sqrt2）。
例と反例
- $a=35$、$b=91$ とすると、最初の割り算は $35=0\cdot91+35$ で、2 数が入れ替わる。以下
$$ 91=2\cdot35+21,\quad 35=1\cdot21+14,\quad 21=1\cdot14+7,\quad 14=2\cdot7+0 $$
であり、$\gcd(35,91)=7$ である（割り算は入れ替えを含めて 5 回）。実際 $35=5\cdot7$、$91=13\cdot7$ である。 - $a=-84$、$b=36$ とすると、余りを $0$ 以上にとるので $-84=(-3)\cdot36+24$ であり、以下 $36=1\cdot24+12$、$24=2\cdot12+0$ から $\gcd(-84,36)=12$ である。これは $\gcd(84,36)=12$ と一致する（$84=2\cdot36+12$、$36=3\cdot12+0$）。
def-euclid-alg と同じ操作を、正の実数 $x_0:=\sqrt2$、$x_1:=1$ に行う。すなわち $x_i>0$ である限り、$q_i:=\lfloor x_{i-1}/x_i\rfloor$（床関数）、$x_{i+1}:=x_{i-1}-q_ix_i$ とおく（$0\le x_{i+1}< x_i$ である）。$1<\sqrt2<2$ なので $q_1=1$、$x_2=\sqrt2-1$ である。
$i\ge1$ について $x_i=(\sqrt2-1)^{i-1}$ であることを帰納法で示す。$i=1,2$ では上で見た。$x_i=(\sqrt2-1)^{i-1}$、$x_{i+1}=(\sqrt2-1)^{i}$ とすると $x_i/x_{i+1}=1/(\sqrt2-1)=\sqrt2+1$ は $2$ と $3$ の間にあるので $q_{i+1}=2$ であり、
$$
x_{i+2}=x_i-2x_{i+1}=(\sqrt2-1)^{i-1}\bigl(1-2(\sqrt2-1)\bigr)=(\sqrt2-1)^{i-1}(3-2\sqrt2)=(\sqrt2-1)^{i+1}
$$
となる（$(\sqrt2-1)^2=3-2\sqrt2$）。よって $x_i$ はどれも $0$ にならず、操作は止まらない。商の列は $1,2,2,2,\dots$ であり、これは $\sqrt2=[1;2,2,2,\dots]$ という連分数展開にあたる。
この例は、thm-euclid-alg-correct の 1「有限回で止まる」が入力が整数であるという仮定に依存していることを示す。実数では余りが真に減っても $0$ に達するとは限らない。逆にこの例から $\sqrt2$ が有理数でないことが分かる。$\sqrt2=m/k$（$m,k$ は正の整数）なら、$x_0,x_1$ を $k$ 倍した整数 $m,k$ に互除法を施すと商と余りはちょうど $k$ 倍の関係のまま同じ列をたどるので、手続きは止まらないことになり、thm-euclid-alg-correct に反する。同じ論法で正方形の辺と対角線が通約できないことを示す議論が、Euclid『原論』第 X 巻の命題 2 とその Heath の注にある（Hea08）。
性質
停止と正しさ
$a$ を整数、$b$ を正の整数とし、def-euclid-alg の記号を使う。
- 手続きは有限回で止まる。すなわち $r_{n+1}=0$ となる $n\ge1$ があり、$n\le b$ である。
- 各 $i=1,\dots,n$ について、$r_{i-1}$ と $r_i$ の公約数の全体は、$a$ と $b$ の公約数の全体に等しい。
- $a$ と $b$ の公約数の全体は、ちょうど $r_n$ の約数の全体である。特に $r_n=\gcd(a,b)$ であり、$a,b$ の任意の公約数は $\gcd(a,b)$ を割り切る。
- $r_1=b$ であり、余りの条件から $r_1>r_2>r_3>\cdots\ge0$ である。整数の真に減少する列なので $r_i\le b-(i-1)$ であり、$r_i\neq0$ が続くのは $i\le b$ の間だけである。よって $r_{n+1}=0$ となる最初の $n$ は存在して $1\le n\le b$ を満たす。
- $1\le i\le n$ について、$r_{i-1}=q_ir_i+r_{i+1}$ から、$c$ が $r_{i-1}$ と $r_i$ を割り切れば $r_{i+1}=r_{i-1}-q_ir_i$ も割り切り、$c$ が $r_i$ と $r_{i+1}$ を割り切れば $r_{i-1}=q_ir_i+r_{i+1}$ も割り切る。したがって $(r_{i-1},r_i)$ の公約数全体と $(r_i,r_{i+1})$ の公約数全体は一致する（除法の原理 の記事の命題「余りへの置き換え」）。これを $i=1,2,\dots$ と繋げると、$(r_0,r_1)=(a,b)$ の公約数全体は、各 $(r_{i-1},r_i)$ の公約数全体に等しい。
- 2 の証明の議論を最後の段の割り算 $r_{n-1}=q_nr_n+r_{n+1}$ に使うと、$(r_{n-1},r_n)$ の公約数全体は $(r_n,r_{n+1})=(r_n,0)$ の公約数全体に等しい。2 と合わせて、$a,b$ の公約数全体は $r_n$ と $0$ の公約数全体、すなわち $r_n$ の約数全体に等しい（すべての整数は $0$ を割り切る）。$r_n>0$ なので、そのうち最大のものは $r_n$ であり、$r_n=\gcd(a,b)$ である。$\square$
3 の後半「公約数は最大公約数を割り切る」は、最大公約数が大きさだけでなく割り切る関係についても最大であることを述べている。Bézoutの等式 の記事の定理「Bézoutの等式」の 3 は同じことを線形結合の最小性から示しているが、上の証明は割り算の繰り返しだけを使う。1 の上界 $n\le b$ は粗く、実際の回数ははるかに小さい（thm-euclid-alg-lame）。
拡張互除法
各段の余り $r_i$ を $a$ と $b$ の整数係数の和 $as_i+bt_i$ として記録しながら互除法を進めると、最後に $\gcd(a,b)=as_n+bt_n$ となる係数が得られる。これを 拡張互除法（extended Euclidean algorithm）という。
$a$ を整数、$b$ を正の整数とし、def-euclid-alg の商 $q_i$ を使って
$$
(s_0,t_0):=(1,0),\quad (s_1,t_1):=(0,1),\qquad s_{i+1}:=s_{i-1}-q_is_i,\quad t_{i+1}:=t_{i-1}-q_it_i\quad(1\le i\le n)
$$
と定める。$d:=\gcd(a,b)$ とする。
- $0\le i\le n+1$ について $r_i=as_i+bt_i$ である。特に $as_n+bt_n=d$ である。
- $0\le i\le n$ について $s_it_{i+1}-t_is_{i+1}=(-1)^i$ である。特に各 $i$ で $s_i$ と $t_i$ は互いに素である。
- $(s_{n+1},t_{n+1})=\pm(b/d,\,-a/d)$ である。
1 は $i$ に関する帰納法で示される（Bézoutの等式 の記事の命題「互除法による係数の計算」とその証明）。
2 を $i$ に関する帰納法で示す。$i=0$ では $s_0t_1-t_0s_1=1\cdot1-0\cdot0=1$ である。$1\le i\le n$ で $i-1$ の場合が正しいとすると
$$
s_it_{i+1}-t_is_{i+1}=s_i(t_{i-1}-q_it_i)-t_i(s_{i-1}-q_is_i)=s_it_{i-1}-t_is_{i-1}=-(s_{i-1}t_i-t_{i-1}s_i)=-(-1)^{i-1}=(-1)^i
$$
である。$s_i$ と $t_i$ の公約数は左辺を割り切るので $\pm1$ を割り切り、$s_i,t_i$ は互いに素である（$i=n+1$ についても、$i=n$ の等式に $s_{n+1},t_{n+1}$ が現れるので同じことが言える）。
3. $A:=a/d$、$B:=b/d$ とおくと、$A,B$ は整数で $B\ge1$、互いに素である（$A$ と $B$ の公約数 $c$ について $cd$ は $a,b$ の公約数なので $|cd|\le d$、よって $c=\pm1$）。1 と $r_{n+1}=0$ から $as_{n+1}+bt_{n+1}=0$、両辺を $d$ で割って $As_{n+1}=-Bt_{n+1}$ である。$B$ は $As_{n+1}$ を割り切り、$A$ と互いに素なので $B\mid s_{n+1}$ である（互いに素 の記事の命題「互いに素な因子の消去」）。$s_{n+1}=Bu$ と書くと $ABu=-Bt_{n+1}$、$B\neq0$ なので $t_{n+1}=-Au$ である。$u$ は $s_{n+1}$ と $t_{n+1}$ の公約数なので、2 により $u=\pm1$ である。$\square$
冒頭の計算 $252=2\cdot105+42$、$105=2\cdot42+21$、$42=2\cdot21+0$（$q_1=q_2=q_3=2$）に prop-euclid-alg-extended を適用すると次の表を得る。
| $i$ | $r_i$ | $q_i$ | $s_i$ | $t_i$ |
|---|---|---|---|---|
| $0$ | $252$ | $1$ | $0$ | |
| $1$ | $105$ | $2$ | $0$ | $1$ |
| $2$ | $42$ | $2$ | $1$ | $-2$ |
| $3$ | $21$ | $2$ | $-2$ | $5$ |
| $4$ | $0$ | $5$ | $-12$ |
したがって $252\cdot(-2)+105\cdot5=-504+525=21$ である。最後の行は $(5,-12)=(105/21,\,-252/21)$ で、prop-euclid-alg-extended の 3 のとおりである。同じく $(89,55)$ では $89\cdot(-21)+55\cdot34=-1869+1870=1$ が得られる。
係数が求まると、$\gcd(a,n)=1$ のときの合同式 $ax\equiv1\pmod n$ の解（法 $n$ での $a$ の逆元）が $x=s_n$ として計算でき（Bézoutの等式 の記事の節「合同式の逆元」）、中国剰余定理の解も具体的に構成できる。prop-euclid-alg-extended の 2 は、隣り合う係数の組 $(s_i,t_i)$ と $(s_{i+1},t_{i+1})$ を並べた $2\times2$ 行列の行列式が $\pm1$ であることを述べており、連分数の近似分数の関係式 $p_nq_{n-1}-p_{n-1}q_n=\pm1$ と同じ構造である。
割り算の回数
互除法の手数は、Fibonacci数 $F_1=F_2=1$、$F_{k+2}=F_{k+1}+F_k$ で評価できる。
$a$ を整数、$b$ を正の整数とし、互除法の割り算の回数を $n$ とする。このとき $0\le j\le n-1$ について $r_{n-j}\ge F_{j+2}$ である。特に $b\ge F_{n+1}$ である。さらに $a>b$ ならば $a\ge F_{n+2}$ である。
$j$ に関する帰納法で示す。$j=0$ では $r_n\ge1=F_2$ である。$n\ge2$ のとき $j=1$ では、$r_n$ は $r_{n-2}$ を $r_{n-1}$ で割った余りなので $r_{n-1}>r_n\ge1$ であり、$r_{n-1}\ge2=F_3$ である。$2\le j\le n-1$ とし、$j-1$、$j-2$ の場合が正しいとする。$i:=n-j+1$ とおくと $2\le i\le n-1$ で、$r_{i-1}=q_ir_i+r_{i+1}$ である。$i\ge2$ なので $r_{i-1}>r_i$ であり、商 $q_i$ は $1$ 以上である。よって
$$
r_{n-j}=r_{i-1}\ge r_i+r_{i+1}=r_{n-j+1}+r_{n-j+2}\ge F_{j+1}+F_j=F_{j+2}
$$
である。$j=n-1$ として $b=r_1\ge F_{n+1}$ を得る。
$a>b$ のとき、$a=q_1b+r_2$ で $q_1\ge1$ である。$n\ge2$ なら $a\ge r_1+r_2\ge F_{n+1}+F_n=F_{n+2}$ である（$r_2\ge F_n$ は $j=n-2$ の場合）。$n=1$ なら $b\mid a$ かつ $a>b\ge1$ なので $a\ge2b\ge2=F_3$ である。$\square$
$n\ge1$ とする。$a=F_{n+2}$、$b=F_{n+1}$ に互除法を施すと、割り算はちょうど $n$ 回であり、商は $q_1=\dots=q_{n-1}=1$、$q_n=2$ である。したがって、$n$ 回の割り算を要する入力 $a>b>0$ のうちで、$b$ も $a$ もこれが最小である。
$1\le i\le n$ について $r_{i-1}=F_{n+3-i}$、$r_i=F_{n+2-i}$ であることを示す。$i=1$ では定義どおりである。$i\le n-1$ なら $n+1-i\ge2$ なので $0< F_{n+1-i}< F_{n+2-i}$（$k\ge2$ で $F_k< F_{k+1}$）であり、$F_{n+3-i}=1\cdot F_{n+2-i}+F_{n+1-i}$ は除法の原理による表示である。よって $q_i=1$、$r_{i+1}=F_{n+1-i}$ となり、次の段も同じ形になる。$i=n$ では $r_{n-1}=F_3=2$、$r_n=F_2=1$ で、$2=2\cdot1+0$ なので $q_n=2$、$r_{n+1}=0$ である。最小性は lem-euclid-alg-fibonacci から従う。$\square$
冒頭の $(89,55)=(F_{11},F_{10})$ は $n=9$ の場合である。Fibonacci数 の記事の定理「Fibonacci数の最大公約数」$\gcd(F_m,F_n)=F_{\gcd(m,n)}$ の証明も、添字の組に互除法を施す形をしている。
$a$ を整数、$b$ を正の整数とし、$b$ の 10 進法での桁数を $k$ とする。互除法の割り算の回数 $n$ は
$$
n\le1+\frac{\log b}{\log\varphi}<5k+1
$$
を満たす。ここで $\varphi=\frac{1+\sqrt5}{2}$ は黄金比である。特に $n\le5k$ であり、$a\ge b$ のとき（$b$ が小さいほうの数のとき）割り算の回数は小さいほうの数の桁数の 5 倍を超えない。
まず $m\ge1$ について $F_{m+1}\ge\varphi^{m-1}$ を示す。$F_2=1=\varphi^0$、$F_3=2\ge\varphi$ であり、$\varphi^2=\varphi+1$ なので、$F_m\ge\varphi^{m-2}$、$F_{m+1}\ge\varphi^{m-1}$ なら
$$
F_{m+2}=F_{m+1}+F_m\ge\varphi^{m-1}+\varphi^{m-2}=\varphi^{m-2}(\varphi+1)=\varphi^m
$$
となる。
lem-euclid-alg-fibonacci により $b\ge F_{n+1}\ge\varphi^{n-1}$ なので、対数をとって $n-1\le\log b/\log\varphi$ である。次に、$\varphi^2=\varphi+1$ を繰り返し使うと $\varphi^5=5\varphi+3=\frac{11+5\sqrt5}{2}$ であり、$5\sqrt5>9$（両辺を 2 乗して $125>81$）なので $\varphi^5>10$ である。$b$ は $k$ 桁なので $b<10^k<\varphi^{5k}$ であり、$\varphi^{n-1}\le b<\varphi^{5k}$ から $n-1<5k$、すなわち $n\le5k$ を得る。$\square$
prop-euclid-alg-worst-case により、$b=F_{n+1}$、$a=F_{n+2}$ で割り算はちょうど $n$ 回である。
- $b=8=F_6$（1 桁）、$a=13$ では $13=1\cdot8+5$、$8=1\cdot5+3$、$5=1\cdot3+2$、$3=1\cdot2+1$、$2=2\cdot1+0$ の 5 回で、thm-euclid-alg-lame の上界 $5\cdot1$ に一致する。
- $b=89=F_{11}$（2 桁）、$a=144$ では 10 回、$b=987=F_{16}$（3 桁）、$a=1597$ では 15 回で、いずれも上界 $5k$ に一致する。
- 4 桁の $b$ では、lem-euclid-alg-fibonacci により 20 回の割り算には $b\ge F_{21}=10946$ が必要なので、回数は 19 回以下である。19 回は $b=F_{20}=6765$、$a=F_{21}=10946$ で実現される。したがって上界 $5k$ は 4 桁ではちょうどは達成されない。
割り算 1 回の手間は数の桁数に応じて増えるが、商が大きい段ほど余りが大きく減るので、全体の計算量はビット長で測って $a,b$ の長さの積の程度に収まる（Sho08 の PDF 版 Theorem 4.2、PDF p. 94）。
補足
- 割り算の代わりに引き算だけを使う形（大きいほうから小さいほうを引き続ける）でも同じ最大公約数が得られる。これは Euclid の原典の形であるが、$a=10^{6}$、$b=1$ のように商が大きいと引き算の回数が商の和だけかかる。
- 2 進法で表された数に対しては、2 で割ることと引き算だけを使う方法（binary gcd）もある（Sho08 の PDF 版 Exercise 4.6、PDF p. 95）。
- 体上の多項式環では、次数を下げる割り算を繰り返す同じ手続きで最大公約多項式が求まる。一般に割り算が「大きさ」を真に下げるEuclid整域では、同じ手続きで最大公約元が計算できる（Euclid整域 の記事の命題「互除法による最大公約元の計算」）。Gauss整数の環 $\mathbb{Z}[i]$ がその例である。
Euclid『原論』第 VII 巻の命題 1 は「小さいほうを大きいほうから引き続けて単位 $1$ が残るなら、2 数は互いに素である」ことを、命題 2 は互いに素でない 2 数の最大公約数（最大公約量）を同じ手続きで求めることを述べ、命題 2 の系として「2 数を割り切る数は最大公約数を割り切る」を導いている（Hea08 第 VII 巻 命題 1・2、Heath 訳 Vol. II pp. 296–299）。割り算の回数の評価は G. Lamé が 1844 年に Fibonacci 数を用いて与えた（Comptes Rendus Paris 19 巻、pp. 867–869。Dic19 Chapter XVII、原本 p. 394 とその脚注による）。現代的な扱いは Sho08 の PDF 版 §4.1（Theorem 4.1、PDF pp. 92–93。$n\le1+\log b/\log\varphi$ の形の評価を含む）と §4.2（Theorem 4.3、拡張互除法）、Ste17 の PDF 版 Algorithm 1.1.13（PDF pp. 12–13）と Algorithm 2.3.7（PDF p. 40）、Cri24 の Algorithm 2.3.3（PDF pp. 36–37）を参照。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
