拡張ユークリッドの互除法の前にユークリッドの互除法を理解する

拡張ユークリッド互除法について、わかりやすかったページなどを紹介しつつ、まとめていきます。
何も見ないで書けるくらい理解するのが目標です。

まず拡張ユークリッド互除法の前にユークリッド互除法を説明します。
整数a, bが与えられた時に、最大公倍数(greatest common divisor)を求めるアルゴリズムがユークリッド互除法です。
まずは一般的な形でユークリッドの互除法を見てから、具体的な数字を当てはめて考えていきます。

こちらのサイトから引用しつつ、説明します。

0より大きい整数 $a, b$ があって $a$ は $b$ より大きいとします。この時以下の操作を繰り返します。

$a, b \in \mathbb{Z}_{>0}, a \geq b$

(0) $a_1 :=a, b_1 := b$ とおいて、ステップ(1)へ進む
(1) $a_1 = q_1 b_1 + r_1$ なる $q_1 \in \mathbb{Z}_{>0} , 0 \leq r_1 < b_1$ を取る( $q_1, r_1$ はそれぞれ $a_1$ を $b_1$ で割った時の商と余り)。 $r_1 = 0$ のときここで終了し、 $r_1 \neq 0$ のとき、 $a_2 := b_1, b_2 := r_1$ とおいて、ステップ(2)へ進む
(2) $a_2 = q_2 b_2 + r_2$ なる $q_2 \in \mathbb{Z}_{>0} , 0 \leq r_2 < b_2$ を取る( $q_2, r_2$ はそれぞれ $a_2$ を $b_2$ で割った時の商と余り)。 $r_2 = 0$ のときここで終了し、 $r_2 \neq 0$ のとき、 $a_3 := b_2, b_3 := r_2$ とおいて、ステップ(3)へ進む
$\cdots$
(k) $a_k = q_k b_k + r_k$ なる $q_k \in \mathbb{Z}_{>0} , 0 \leq r_k < b_k$ を取る( $q_k, r_k$ はそれぞれ $a_k$ を $b_k$ で割った時の商と余り)。 $r_k = 0$ のときここで終了し、 $r_k \neq 0$ のとき、 $a_{k+1} := b_k, b_{k+1} := r_k$ とおいて、ステップ( $k+1$ )へ進む
$\cdots$
この時、この操作は必ずあるステップで終了し、ステップ $(n)$ で終了したとき、 $b_n = gcd(a, b)$ である。

少しだけコードにすると、

# 商
q1 = a // b
# 余り
r1 = a % b

ステップ1からステップ2にいくときのポイントとしては、
ステップ2ではbの値をステップ1の余りで割って、また商と余りを求めているところです。

具体的な数字でやってみます。

gcd(1444, 32)の場合、余りは1444 % 32 = 4、1444 / 32の商は4
次のステップで32を4で割ると余りは0になるので、答えは4になります。

gcd(1414, 154)の場合、余りは1414 % 154 = 28、1414 / 154の商は9
次のステップで、154を28で割ると余りは154 % 28 = 14、商は5になります。
さらに次のステップで、28を14で割ると余りは0になるので、答えは14になります。

この繰り返し操作をコードに落とし込むと、以下のようになります。

def gcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return gcd(b, a % b)

拡張ユークリッド互助法は整数a, bが与えられた時に、最大公約数だけでなく、 $ax + by = gcd(a, b)$ を満たす $x$ と $y$ を求めることができます。

長くなったので拡張ユークリッド互除法は次の機会にまわします。