ユークリッドの互除法の原理

ユークリッドの互除法

今回は 2000 年も昔から知られるユークリッドの互除法（Euclid’s Algorism）の原理という有名な定理を証明します。

【定理A12：ユークリッドの互除法の原理】
2 つの整数

a, b (a > b > 0)

について

a = b q + r (0 \leq r < b)

を満たすような

(q, r)

が唯一組存在し、

(a, b) = (b, r)

が成り立つ。

[証明] $a = b q + r (0 \leq r < b)$ を満たすような $(q, r)$ が唯一組だけ存在することは定理A1 で述べてあります。ここでは
$(a, b) = (b, r)$
が成り立つことを証明します。
$g_{1} = (a, b), g_{2} = (b, r 4)$
とおきます。 $a = b q + r$ なので
$r = a - b q$
と書き直すと、 $a, b$ ともに $g_{1}$ を約数にもつので、 $a, b$ の 1 次結合 $r$ もまた $g_{1}$ を約数にもちます。
$g_{1} | r$
です。 $g_{1}$ は $b$ と $r$ の公約数なので、 $b$ と $r$ の最大公約数以下となっているはずです。
$g_{1} \leq g_{2}$
同様に $a = b q + r$ において、 $b, r$ ともに $g_{2}$ を約数にもつので、その 1 次結合である $a$ も $g_{2}$ を約数にもちます。すなわち $g_{2}$ は $a$ と $b$ の公約数なので、 $a$ と $b$ の最大公約数以下となっているはずです。
$g_{1} \geq g_{2}$
$g_{1} \leq g_{2}$ かつ $g_{1} \geq g_{2}$ なので
$g_{1} = g_{2}$
が成り立ちます。すなわち
$(a, b) = (b, r)$
が成り立つことが示されました。（証明終）

$a_{1} > a_{2} > 0$ なる 2 整数について、除算アルゴリズムを次々に適用してみます。
$\begin{aligned} a_{1} = a_{2} q_{1} + a_{3} (0 \leq a_{3} < a_{2}) \\ a_{2} = a_{3} q_{2} + a_{4} (0 \leq a_{4} < a_{3}) \\ a_{3} = a_{4} q_{3} + a_{5} (0 \leq a_{5} < a_{4}) \\ ⋮ \end{aligned}$
$a_{1} > a_{2} > a_{3} > \dots$ なので、いつかは余りが 0 となって割り切れます。それが $n$ 回目であったとすると
$\begin{aligned} a_{3} = a_{4} q_{3} + a_{5} (0 \leq a_{5} < a_{4}) \\ \dots \dots \dots \dots \dots \dots \dots \dots \\ a_{n - 1} = a_{n} q_{n - 1} + a_{n + 1} (0 \leq a_{n + 1} < a_{n}) \\ a_{n} = a_{n + 1} q_{n} \end{aligned}$
となります。そこで定理 A12（ユークリッドの互除法の原理）を適用すると
$(a_{1}, a_{2}) = (a_{2}, a_{3}) = (a_{3}, a_{4}) = \dots = (a_{n}, a_{n + 1}) = a_{n + 1}$
となります。すなわち最後に $a_{n}$ を割り切った $a_{n + 1}$ が最大公約数であるということです。具体的な数でユークリッドの互除法を試してみましょう。556 と 208 の最大公約数を求めてみます。
$\begin{aligned} 556 & = 208 \times 2 + 140 \\ 208 & = 140 \times 1 + 68 \\ 140 & = 68 \times 2 + 4 \\ 68 & = 4 \times 17 \end{aligned}$
最後に 68 を割り切った 4 が 556 と 208 の最大公約数です。
　
ユークリッドの互除法を視覚化してみましょう。
例として、72 と 56 の最大公約数を求めます。

ユークリッドの互除法説明図

横が 72, 縦が 56 の長方形です。作業は簡単です。まず、この長方形からなるべく大きな正方形ができるように切込みを入れます。１辺の長さ 56 の青い正方形が１つとれましたね。もとの長方形の辺の長さを、この青い正方形の１辺を使って表すと、

72 = 56 × 1 + 16

となります。今度は青い正方形を切り離してしまって、右側の細長い長方形からなるべく大きな正方形がとれるように切込みを入れます。１辺の長さ 16 赤い正方形が 3 つとれます。式で表すと、

56 = 16 × 3 + 8

です。残ったのは１辺の長さ 16 の緑色の長方形で、これは

16 = 8 × 2

と 2 つに分けることができます。もとの長方形は１辺が 8 の正方形タイルできれいに敷き詰めることができます。つまり 72 と 56 の最大公約数は 8 だということです。これが最大公約数の図形的な意味です。上の計算式をまとめて書いてみます。

　　72 = 56 × 1 + 16
　　56 = 16 × 3 + 8
　　16 = 8 × 2

従って、8 が最大公約数であることがわかります。もう少し簡略化して書くと、

　　72 ÷ 56 = 1　[余り 16]
　　56 ÷ 16 = 3　[余り 8]
　　16 ÷ 8 = 2 　[余り 0]

のように計算します。手順は除数（割る数）を余りで割ることの繰返しです。

【次の記事】≫ 小さくない数と大きくない数

ユークリッドの互除法

エクセルや数学に関するコメントをお寄せください