アルゴリズム論特論（塩田）第3回 (4) 拡張ユークリッドアルゴリズム
拡張ユークリッドアルゴリズム
ユークリッドのアルゴリズムを改良すると
$ax+by=\gcd(a,b)$
を満たす $x$, $y$ も求めることができます。
Algorithm 9 (拡張ユークリッドアルゴリズム)
- 入力：$a$, $b$
- 出力：$d = \gcd(a,b)$ と、$ax+by=\gcd(a,b)$ を満たす $x$, $y$
- ３つの数列 $\{\,r_n\,\}$, $\{\,x_n\,\}$, $\{\,y_n\,\}$ を宣言する
- $r_0 \leftarrow a$, $r_1 \leftarrow b$,
$x_0 \leftarrow 1$, $x_1 \leftarrow 0$, $y_0 \leftarrow 0$, $y_1 \leftarrow 1$, $n \leftarrow 0$ とおく
- $r_{n+1}=0$ ならば 5° へ
- $q \leftarrow (\,r_n \div r_{n+1}$ の商 ),
$r_{n+2} \leftarrow r_n - q \times r_{n+1}$,
$x_{n+2} \leftarrow x_n - q \times x_{n+1}$,
$y_{n+2} \leftarrow y_n - q \times y_{n+1}$,
$n \leftarrow n+1$ として 3° へ
- $r_{n} \lt 0$ ならば $(r_n,x_n,y_n) \leftarrow (-r_n,-x_n,-y_n)$,
- $(d,x,y)=(r_n,x_n,y_n)$ を出力
証明 $\{\,r_n\,\}$ は
Alg.6 と同じものなので、
出力の $d$ が $\gcd(a, b)$ であることと、
有限回のステップで終了することは証明できています。
あとは、全ての番号 $n$ について
$r_n = a\, x_n + b\, y_n$
が成り立つことを帰納法で示します。
$n=0$, $1$ のときは、初期値設定から
$r_0 = a = a \times 1 + b \times 0 = a\, x_0 + b\, y_0,$
$r_1 = b = a \times 0 + b \times 1 = a\, x_1 + b\, y_1\,$
となって成り立っています。$n$, $n+1$ のとき正しければ
| $r_{n+2}$ | $=$ | $r_n - q \times r_{n+1}$ |
| $=$ | $(a\, x_n + b\, y_n) - q \times (a\, x_{n+1} + b\, y_{n+1})$ |
| $=$ | $a (x_n - q \times x_{n+1}) + b\, (y_n - q \times y_{n+1})$ |
| $=$ | $a\, x_{n+2} + b\, y_{n+2}$. |
(証明終)
実行例
$\require{color}$
Ex.10 $13579 x + 2468 y=1$ を満たす $x$, $y$ は？
| $n$ | $q$ | $r_n$ | $x_n$ | $y_n$ |
| $0$ | | $\textcolor{blue}{13579}$ | $\textcolor{blue}{1}$ | $\textcolor{blue}{0}$ |
| $1$ | | $\textcolor{green}{2468}$ | $\textcolor{green}{0}$ | $\textcolor{green}{1}$ |
| $2$ | $ \textcolor{red}{5}=\lfloor \textcolor{blue}{13579}/\textcolor{green}{2468}\rfloor$ | $\textcolor{brown}{1239}$ | $\textcolor{brown}{1}$ | $\textcolor{brown}{-5}$ |
| $3$ | $ 1=\lfloor 2468/1239\rfloor$ | $1229$ | $-1$ | $6$ |
| $4$ | $ 1=\lfloor 1239/1229\rfloor$ | $10$ | $2$ | $-11$ |
| $5$ | $ 122=\lfloor 1229/10\rfloor$ | $9$ | $-245$ | $1348$ |
| $6$ | $1=\lfloor 10/9\rfloor$ | $1$ | $247$ | $-1359$ |
| $7$ | $ 9=\lfloor 9/1\rfloor$ | $0$ | | |
$r_n$ が $0$ になる直前の行から
$\gcd(13579,2468)=1=13579 \times 247 + 2468 \times (-1359)$.
( 表の作り方：
$\textcolor{brown}{r_2} = \textcolor{blue}{r_0} - \textcolor{red}{5} \times \textcolor{green}{r_1} = \textcolor{blue}{13579} - \textcolor{red}{5} \times \textcolor{green}{2468} = \textcolor{brown}{1239}$
に合わせて
$\textcolor{brown}{x_2} = \textcolor{blue}{x_0} - \textcolor{red}{5} \times \textcolor{green}{x_1} = \textcolor{blue}{1} - \textcolor{red}{5} \times \textcolor{green}{0} = \textcolor{brown}{1}\phantom{0}$
$\textcolor{brown}{y_2} = \textcolor{blue}{y_0} - \textcolor{red}{5} \times \textcolor{green}{y_1} = \textcolor{blue}{0} - \textcolor{red}{5} \times \textcolor{green}{1} = \textcolor{brown}{-5}$
のように計算します。)
Ex.10' $13579 x + 2468 y=1$ を満たす $x$, $y$ を、負の余りも使うパターンでも計算してみましょう。
| $n$ | $q$ | $r_n$ | $x_n$ | $y_n$ |
| $0$ | | $13579$ | $1$ | $0$ |
| $1$ | | $2468$ | $0$ | $1$ |
| $2$ | $ 6=\mbox{round}( 13579/2468)$ | $-1229$ | $1$ | $-6$ |
| $3$ | $ -2=\mbox{round}(2468/(-1229))$ | $10$ | $-2$ | $13$ |
| $4$ | $-123=\mbox{round}( (-1229)/10)$ | $1$ | $247$ | $-1359$ |
| $5$ | $ 10=\mbox{round}( 10/1)$ | $0$ | | |
$r_n$ が $0$ になる直前の行から
$\gcd(13579,2468)=1=13579 \times 247 + 2468 \times (-1359)$.
プログラミング上の注意
- 数列 $\{\,r_n\,\}$, $\{\,x_n\,\}$, $\{\,y_n\,\}$ はいずれも直前の 2 項しか残す必要が無いので、変数を使い回せば配列を使わなくて済みます。
- $y$ は $y = (\gcd(a,b) - ax)/b$ によって計算できるので、必ずしも $\{\,y_n\,\}$ を計算しなくて済みます。
- 整数商は、Python 2 では / でも // でもＯＫですが、Python 3 では // と書いてください。
Python3 で / を使うと実数値での計算結果が返されてしまいます。