ユークリッドの互除法の基本

割り算からわかること

割り算の一般式は次の方法で表記できることがわかっている。

$$a=bq+r \tag{1-1}$$

$a, q$ は整数（さらに $q$ は式の商）、$b$ は正の整数、$r$ は整数とし、$0 \leq r < b$ とする。
この式を変形して、次の形にするととあることがわかる。

$$a – bq = r \tag{1-2}$$

$a \geq b$ とする。
$r$ は割り算でいうところの余りなので、$r=0$ となると $a, b$ の最大公約数は $b$ となる（$q$ は商なので単なる $b$ を倍加しているに過ぎない）。このことを踏まえて、(1-2)式からわかることとして $a, b$ が公約数 $e$ を持つとして、さらに式を変形していくと

$$e(a_{0} – b_{0}q) = er_{0} \tag{1-3}$$

$a_{0}, b_{0}, r_{0}$ は $e$ の商とする。
このことから、$a, b$ の最大公約数においても $a, b$ は最大公約数で割り切れ、同時に $r$ もそれで割り切れるので、$a, b$ の最大公約数は $b, r$ の最大公約数と一致することがわかる。

2つの値の最大公約数の特定

先程の性質を利用することで、$a, b \to b, r \to r, r_{1} \to \dots \to r_{n}, 0$ と繰り返すことで、$a, b$ の最大公約数 $r_{n}$ を特定することが可能である。例として1053と432の最大公約数の特定をしていこう。

$$1053 – 432q = r$$
$$1053 = 432q + r$$

となる。この時 $r$ が最小の正の整数になるような組み合わせを考える。そうすると $q=2, r=189$ となる。まだ余りが出るので、再度式を作ると

$$432 = 189 \times 2 + 54$$

となる。まだ余りがあるので

$$189 = 54 \times 3 + 27$$
$$54 = 27 \times 2 + 0$$

27が出た時点で余りが0になった。よって1053と432の最大公約数は27となる。

最大公約数の性質

先程求めた式を用いて、次に最大公約数が持つ性質についてみていく。

$$1053 = 432 \times 2 + 189$$
$$432 = 189 \times 2 + 54$$
$$189 = 54 \times 3 + 27$$
$$54 = 27 \times 2 + 0$$

これらの式を「余り＝」の形にすると

$$189 = 1053 – 432 \times 2 \tag{3-1}$$
$$54 = 432 – 189 \times 2 \tag{3-2}$$
$$27 = 189 – 54 \times 3 \tag{3-3}$$

そして、(3-3)式に(3-2)式を代入し、その式に(3-1)式を代入してみると

$$27 = 1053 \times 7 + 432 \times (-17) \tag{3-4}$$

となる。ここからわかることとして

$$27 = 1053r + 432s$$

という感じで、適当な数字 $r, s$ で示すことができ、この式を満たす1組が $(r, s) = (7, -17)$ であることがわかった。
このことから、0でない2つの整数 $a, b$ の最大公約数を $d$ とし、$r, s$ を適当な整数とすると

$$d = a \times r + b \times s$$

で示すことができ、これを満たす $r, s$ が存在することがわかる。
また、$a, b$ が互いに素であると

$$1 = a \times r + b \times s$$

となり、この時も式を満たす $r, s$ が存在することもわかる。

参考書