Euclidの互除法とBezoutの補題

Euclidの互除法

与えられた $2$ つの数の最大公約数を実際に求めるには、Euclidの互除法という高速な計算方法がある。前ページの命題1 より与えられた $2$ つの数の最小公倍数は最大公約数を用いてあらわすことができるから、与えられた $2$ つの数の最小公倍数を求める実用的な計算方法も得られたことになる。

Euclidの互除法

与えられた2つの整数 $a \geq b > 0$ について $a_{0} = a, a_{1} = b$ とし
$\begin{aligned} a_{0} = & q_{1} a_{1} + a_{2} (0 \leq a_{2} < a_{1}), \\ a_{1} = & q_{2} a_{2} + a_{3} (0 \leq a_{3} < a_{2}), \\ \dots \\ a_{k - 1} = & q_{k} a_{k} + a_{k + 1} (0 \leq a_{k + 1} < a_{k}), \\ \dots \end{aligned}$
となる整数 $q_{1}, a_{2}, q_{2}, a_{3}, \dots$ を $a_{s + 1} = 0$ となるまで繰り返しとっていくと、 $a_{s - 1} = q_{s} a_{s}$ , $a_{s + 1} = 0$ となる $s$ が必ず存在する、さらにその場合 $a_{s} = gcd (a, b)$ となる。

$a_{n + 1} = 0$ となる $n$ が存在しないと仮定すると
$b = a_{1} > a_{2} > \dots \geq 0$
より、 $0 \leq a_{b + 2} \leq b + 1 - (b + 2) < 0$ となり、矛盾するから、 $a_{n + 1} = 0$ となる $n$ は必ず存在する。

そこでそのような最小の $n$ を $s$ とおくと $a_{s - 1} = q_{s} a_{s}$ より $a_{s} ∣ a_{s - 1}$ となる。
$1 \leq k \leq s$ かつ $a_{s} ∣ a_{k}, a_{k + 1}, \dots, a_{s}$ とすると $a_{k - 1} = q_{k} a_{k} + a_{k + 1}$ も $a_{s}$ の倍数だから数学的帰納法より $a = a_{0}, b = a_{1}, \dots, a_{s}$ はすべて $a_{s}$ の倍数となる。とくに $a_{s}$ は $a, b$ の公約数である。

一方、 $a_{0} = a, a_{1} = b$ は $gcd (a_{0}, a_{1}) = gcd (a, b)$ で割り切れる。
$a_{0}, a_{1}, \dots, a_{k}$ が $gcd (a, b)$ で割り切れるとき
$a_{k + 1} = a_{k - 1} - q_{k} a_{k}$ も $gcd (a, b)$ で割り切れる。
よって数学的帰納法より $a = a_{0}, b = a_{1}, \dots, a_{s}$ はすべて $gcd (a, b)$ の倍数となる。とくに $a_{s}$ は $gcd (a, b)$ の倍数である。

以上のことより $a_{s} = gcd (a, b)$ となる。

Bezoutの補題

Euclidの互除法にあらわれる各 $a_{i} (0 \leq i \leq s)$ は $m_{i} a + n_{i} b (m_{i}, n_{i} \in Z)$ の形にあらわすことができる。さらに $m_{k}, n_{k}$ は $q_{1}, q_{2}, \dots, q_{k - 1}$ から計算できる。実際 $a_{0} = a, a_{1} = b$ で、かつ $a_{0}, a_{1}, \dots, a_{k}$ が $m_{i} a + n_{i} b (m_{i}, n_{i} \in Z)$ の形にあらわすことができたとき
$a_{k + 1} = a_{k - 1} - q_{k} a_{k} = (m_{k - 1} a + n_{k - 1} b) - q_{k} (m_{k} a + n_{k} b) = (m_{k - 1} - q_{k} m_{k}) a + (n_{k - 1} - q_{k} n_{k}) b$
となる。とくに $gcd (a, b) = m a + n b$ となる整数 $m, n$ がとれる。

より一般に、次のBezoutの補題（代数曲線の交点に関するBezoutの定理とは別の定理である）が成り立つ。

Bezoutの補題

$a_{1}, a_{2}, \dots, a_{k}$ を任意の $k$ 個の整数とする。このとき
$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{k} x_{k} = n$
となる整数 $x_{1}, x_{2}, \dots, x_{k}$ が存在する $⟺ gcd (a_{1}, a_{2}, \dots, a_{k}) ∣ n$ .

$d = gcd (a_{1}, a_{2}, \dots, a_{k}), a_{i} = d b_{i}$ とおく。
$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{k} x_{k} = n$
となる整数 $x_{1}, x_{2}, \dots, x_{k}$ が存在するとき、
$n = d (b_{1} x_{1} + b_{2} x_{2} + \dots + b_{k} x_{k})$
より $n$ は $d = gcd (a_{1}, a_{2}, \dots, a_{k})$ の倍数である。

$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{k} x_{k} = m, a_{1} y_{1} + a_{2} y_{2} + \dots + a_{k} y_{k} = n$
となる整数 $x_{1}, x_{2}, \dots, x_{k}, y_{1}, y_{2}, \dots, y_{k}$ が存在するとき、任意の整数 $s, t$ について
$a_{1} (s x_{1} + t y_{1}) + a_{2} (s x_{2} + t y_{2}) + \dots + a_{k} (s x_{k} + t y_{k}) = s m + t n$
となるから、
$a_{1} z_{1} + a_{2} z_{2} + \dots a_{k} z_{k} = s m + t n$
となる $z_{1}, z_{2}, \dots, z_{k}$ がとれる。よって倍数と約数:定理4 より
$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{k} x_{k} = n$
となる整数 $x_{1}, x_{2}, \dots, x_{k}$ が存在するような最小の正の $n$ を $n_{0}$ とおくと
$\exists x_{1}, x_{2}, \dots, x_{k} \in Z [a_{1} x_{1} + a_{2} x_{2} + \dots + a_{k} x_{k} = n] ⟺ n_{0} ∣ n$
となる。
$x_{i} = 1, x_{j} = 0 (j \neq i)$ のとき $a_{1} x_{1} + a_{2} x_{2} + \dots + a_{k} x_{k} = a_{i}$ となるから、 $n_{0}$ は $a_{1}, a_{2}, \dots, a_{k}$ の公約数である。しかし先に示したことから
$n_{0}$ は $gcd (a_{1}, a_{2}, \dots, a_{k})$ の倍数なので $n_{0} = gcd (a_{1}, a_{2}, \dots, a_{k})$ .

なお、Bezoutの補題から倍数と約数:定理6 を示すこともできる。
実際 $d = gcd (a, n)$ とおくと $s a + t n = d$ となる整数 $s, t$ がとれる。 $n ∣ a b$ のとき $a b = k n$ とおくと
$k d = k (s a + t n) = s k a + t k n = s k a + t a b = a (s k + t b)$
より $k$ は $a / d = a / gcd (a, n)$ の倍数であるから倍数と約数:定理2 より $b = k n / a$ は $(n a / d) / a = n / d$ の倍数である（逆に $b$ が $n / d$ の倍数ならば $a b = (a / d) n$ は $n$ の倍数である）。

参考文献

Bezoutの補題に関する議論は Trygve Nagell, Introduction to Number Theory, John Wiler & Sons, Inc. New York, 1951, Section 1.4, p.p.14--15 を参考とした。

参考文献

[1]

G. H. Hardy and E. M. Wright, revised by D. R. Heath-Brown and J. H. Silverman, An Introduction to the Theory of Numbers, 6th Ed., Oxford University Press, 2008

[2]

G. H. Hardy and E. M. Wright, 訳: 示野信一、矢神毅, 数論入門I 原書6版, 数学クラシックス, 丸善出版, 2022

[3]

G. H. Hardy and E. M. Wright, 訳: 示野信一、矢神毅, 数論入門II 原書6版, 数学クラシックス, 丸善出版, 2022

[4]

J. C. Morehead, Factors of Fermat's numbers, Bull. Amer. Math. Soc., 1906, 449

[5]

D. P. Parent, Exercises in Number Theory, Springer-Verlag, 1984

[6]

Trygve Nagell, Introduction to Number Theory, Reprint Edition, American Mathematical Society (original: John Wiler & Sons, Inc.), 2001

[7]

Paulo Ribenboim, The New Book of Prime Number Records (3rd ed. pbk.), Springer, 2013