拡張ユークリッドの互除法を実装してみる

アドベントカレンダー（自称）vol.17

皆さん、こんにちは。yumyum116 です。SWE転職を目指す者です。
アドベントカレンダーに便乗して、1日1記事投稿に挑戦するとともに、執筆活動の習慣化にも挑戦してみます。

今回は、拡張ユークリッドの互除法 について取り上げます。

1. 拡張ユークリッドの互除法とは

２つの整数 $a$, $b$ の最大公約数 $gcd(a, b)$ について、次の2変数一次方程式

$$ax + by = gcd(a, b) ...①$$

が成り立ち、式①を満たす整数解 $(x, y)$ について、1組の解を求める方法です。

2. 拡張ユークリッドの互除法のアルゴリズム

本題に入る前に、ユークリッドの互除法における処理についておさらいしましょう。

ユークリッドの互除法では、2つの整数 $a$, $b$ について、次のような処理により、$gcd(a, b) = r_n$ ...② を求めます。

$$a = b * q_0 + r_0 b = r_0 * q_1 + r_1 r_0 = r_1 * q_2 + r_2 ... r_{n-2} = r_{n-1} * q_n + r_n r_{n-1} = r_n * q_{n+1}$$

ここで、一行目の式に注目します。

$$a = b * q_0 + r_0 r_0 = a - b * q_0$$

となり、$r_0$ を $a$, $b$ の倍数の和で表すことができます。

この結果を、二行目に代入してみましょう。

$$b = r_0 * q_1 + r_1 b = (a - b * q_0) * q_1 + r_1 b = a * q_1 - b * q_0 * q_1 + r_1 r_1 = -a * q_1 + b * (q_0 * q_1 + 1)$$

となり、$r_1$ も $a$, $b$ の倍数の和で表すことができます。

この操作を繰り返していくと、$r_i * (0 <= i <= n)$ も $a$, $b$ の倍数の和で表すことができます。
したがって、最終的に

$$r_n = k * a + l * b$$

と表すことができます。式②より、

$$k * a + b * l = gcd(a, b) ...③$$

となり、式①と同じかたちで表すことができました。
式①と③を比較すると、

$$(x, y) = (k, l)$$

と表せ、この $k$, $l$ が整数解の一つになります。

3. 拡張ユークリッドの互除法を実装してみる

前章の内容を踏まえ、拡張ユークリッドの互除法を実装してみます。

extended_eucledean.py

def extended_eucledean(a, b):
	if b == 0:
		return (1, 0)
	else:
		xd, yd = extended_euclid(b, a % b)
		return (yd, xd - a // b * yd)

非常にシンプルですね。

---

記事内に誤謬等ある場合には、修正いたします。その際は、ご連絡いただけますと幸いです。

それでは。また。