アルゴリズム論特論(塩田)第3回 (3) ユークリッドのアルゴリズム

Key Lemma

 ここでは、ユークリッドのアルゴリズムでキーとなる命題を示します。
Lemma 5 $a=b\,q+r$ が成り立つとき、
$\gcd(a,b) = \gcd(b,r).$
証明 $d = \gcd(a,b)$, $e = \gcd(b,r)$ とおいて、$d = e$ を示しましょう。

(1) まず、$b$, $r$ は $e$ の倍数ゆえ、

$a = b\,q + r$
から
$a$ は $e$ の倍数
∴ $e$ は $a$ の約数
∴ $e$ は $a$, $b$ の公約数
∴ $e \leqq \gcd(a,b) = d$
(2) 他方、$a$, $b$ は $d$ の倍数ゆえ、
$r = a - b\,q$
から
$r$ は $d$ の倍数
∴ $d$ は $r$ の約数
∴ $d$ は $b$, $r$ の公約数
∴ $d \leqq \gcd(b,r) = e$
(1), (2) より $d = e$. (証明終)

 Ex.2 では $630 = 168 \times 3 + 126$ より
$\gcd(630,168) = \gcd(168, 126)$
となります。 2変数関数 $\gcd$ が、$630$, $168$ より小さい引数 $168$, $126$ で計算できる訳です。

ユークリッドのアルゴリズム

Algorithm 6 (ユークリッドのアルゴリズム)
  • 入力:$a$, $b$
  • 出力:$\gcd(a,b)$
  1. 数列 $\{\,r_n\,\}$ を宣言する
  2. $r_0 \leftarrow a$, $r_1 \leftarrow b$, $n \leftarrow 0$ とおく
  3. $r_{n+1}=0$ ならば $|\,r_n\,|$ を出力
  4. $r_{n+2} \leftarrow (\,r_n \div r_{n+1}$ の余り ), $n \leftarrow n+1$ として 3° へ
証明 (1) 出力が $\gcd(a, b)$ であること
$\because$ L'a 5 より全ての $n$ について
$\gcd(r_n, r_{n+1}) = \gcd(r_{n+1}, r_{n+2})$
が成り立ち、$n=0$ のときは
$\gcd(r_0, r_1) = \gcd(a, b)$
です。また 3. の終了条件 $r_{n+1}=0$ が満たされるときには
$\gcd(r_n, r_{n+1}) = \gcd(r_n, 0) = |\,r_n\,|$
ゆえ、出力される $|\,r_n\,|$ は $\gcd(a, b)$ に等しくなります。
(2) アルゴリズムが有限回のステップで終了すること
$\because$ 数列 $\{\,r_n\,\}$ は順番に余りを取って定めていますので、 非負整数からなる単調減少列であり、 有限回で $r_{n+1}=0$ となります。(証明終)
Ex.7 Alg.6 を用いて $\gcd(13579, 2468)$ を求めましょう。 $\{\,r_n\,\}$ を求めると、
$r_0=13579,\quad$ $r_1=2468,\quad$ $r_2=1239,\quad$ $r_3=1229,\quad$
$r_4=10,\quad$ $r_5=9,\quad$ $r_6=1,\quad$ $r_7=0$
となり、$r_n$ が 0 になる直前を見て $\gcd(13579,2468)=|\,r_6\,|=1$ となります。
Rem.8 L'a 5 の余り $r$ は負であっても良いので、 Ex.7 は負の余りも使って
$r_0=13579,\quad$ $r_1=2468,\quad$ $r_2=1239,\quad$ $r_3=-10,\quad$
$r_4=-1,\quad$ $r_5=0\quad$
として、$\gcd(13579,2468)=|\,r_4\,|=1$ でも構いません。
やってみよう $\gcd(1357, 246)=$?