アルゴリズム論特論（塩田）第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)$
となります。
２変数関数 $\gcd$ が、$630$, $168$ より小さい引数 $168$, $126$ で計算できる訳です。
ユークリッドのアルゴリズム
Algorithm 6 (ユークリッドのアルゴリズム)
- 入力：$a$, $b$
- 出力：$\gcd(a,b)$
- 数列 $\{\,r_n\,\}$ を宣言する
- $r_0 \leftarrow a$, $r_1 \leftarrow b$, $n \leftarrow 0$ とおく
- $r_{n+1}=0$ ならば $|\,r_n\,|$ を出力
- $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)=$？
答え
$r_0=1357,\quad$
$r_1=246,\quad$
$r_2=127,\quad$
$r_3=119,\quad$
$r_4=8,\quad$
$r_5=7,\quad$
$r_6=1,\quad$
$r_7=0$.
$r_n$ が $0$ になる直前を見て $\gcd(1357,246)=1$.