アルゴリズム論特論（塩田）2021年度

アルゴリズム論特論（塩田）第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 で / を使うと実数値での計算結果が返されてしまいます。

前へ / 戻る / 次へ