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

拡張ユークリッドアルゴリズム

 ユークリッドのアルゴリズムを改良すると
$ax+by=\gcd(a,b)$
を満たす $x$, $y$ も求めることができます。
Algorithm 9 (拡張ユークリッドアルゴリズム)
  • 入力:$a$, $b$
  • 出力:$d = \gcd(a,b)$ と、$ax+by=\gcd(a,b)$ を満たす $x$, $y$
  1. 3つの数列 $\{\,r_n\,\}$, $\{\,x_n\,\}$, $\{\,y_n\,\}$ を宣言する
  2. $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$ とおく
  3. $r_{n+1}=0$ ならば 5° へ
  4. $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° へ
  5. $r_{n} \lt 0$ ならば $(r_n,x_n,y_n) \leftarrow (-r_n,-x_n,-y_n)$,
  6. $(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 では / でも // でもOKですが、Python 3 では // と書いてください。 Python3 で / を使うと実数値での計算結果が返されてしまいます。