拡張Euclidの互除法
Abstract
拡張Euclidの互除法 (Extended Euclid's algorithm) は, $ a, bの少なくとも一方が0でない整数のとき, $ ax + by = \gcd(a, b)の整数解$ (x, y)の一つと$ \gcd(a, b)を求めるアルゴリズム.
Explanation
Bézoutの補題
まず, 次の Bézoutの補題 により, $ ax + by = \gcd(a, b)の整数解の存在は保証される. 少なくとも一方が0でない整数$ a, b \in \mathbb{Z}に対し, $ g = \gcd(a, b)とする.
次の1次不定方程式 (Bézoutの等式)
$ ax + by = g
には整数解$ (x, y) \in \mathbb{Z}^2(Bézout係数) が存在する.
また, $ gは整数の組$ (x, y) \in \mathbb{Z}^2を用いて$ ax + byで表される正整数のうち最小のものである. すなわち,
$ g = \min \{ ax + by \mid (x, y) \in \mathbb{Z}^2, ax + by > 0 \}
が成り立つ.
Proof
一般性を失うことなく, $ a \neq 0とする.
($ gの最小性)
集合$ T(a, b)を次のとおり定める:
$ T(a, b) := \{ ax + by \mid (x, y) \in \mathbb{Z}^2, ax + by > 0 \}
$ a > 0のとき, $ a \cdot 1 + b \cdot 0 = a \in T(a, b)であり, $ a < 0のとき$ a \cdot (-1) + b \cdot 0 = -a \in T(a, b)であるから,
$ \mathbb{Z}_{>0} \supseteq T(a, b) \neq \varnothing
である. よって, 整列可能原理 から, $ T(a, b)には最小元$ mが存在する. これを $ m = au + bv
と表す. $ aを$ mで割った商と余りを$ q, rとすると,
$ a = mq + r \quad (0 \le r < m)
と表せるので,
$ r = a - mq = a - (au + bv)q = a(1 - u) + b(-vq).
$ r > 0とすると, $ r \in T(a, b)となり, $ r < mなので$ mの最小性に反す. よって$ r = 0となり$ m \mid a.
$ bについても同様に$ m \mid aがわかる. これより, $ mは$ a, bの公約数であり, $ gが最大公約数であったから$ m \le g.
一方, $ m = au + bvであり, $ a, bは$ gで割り切れるので$ g \mid m. ゆえに$ g \le m.
以上より, $ g = m = \min \{ ax + by \mid (x, y) \in \mathbb{Z}^2, ax + by > 0 \}.
(整数解の存在)
上の証明における$ (u, v)は$ m = g = au + bvを満たすので, 確かに整数解$ (x, y) = (u, v)をもつ.$ \blacksquare
以上の証明では, 整数解の存在が示されたものの, その整数解が実際にどのように表せるか (i.e., 証明中の$ (u, v)が$ a, bからどのように求まるか) については何も述べていない.
Euclidの互除法を利用した整数解の構成
TODO 書く
Algorithm (XX)
Input:
XXXXXX
Output:
XXXXXX
1. XXXXXX
2. XXXXXX
3. XXXXXX
Implementation
Input
0でない整数 a, b
Output
$ a, bの最大公約数 g
1次不定方程式$ ax + by = \gcd(a, b)を満たす整数解の一つ x, y
Time complexity
$ O(\log \min(a, b))time. (Laméの定理 による.) code:python
def extended_euclid(a, b):
x1, y1, m = 1, 0, a
x2, y2, n = 0, 1, b
if b == 0: return x1, y1, m
while m % n != 0:
q, r = divmod(m, n)
x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
return x2, y2, n
Verification
References