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

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

vermee81-coding-memo.hatenablog.jp


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

まずはユークリッドの互除法のように aを式で表します。
 a = qb + r ( q, rはそれぞれ a bで割った時の商と余り)
上記の式を ax + by = gcd(a, b) に代入すると、 (qb + r)x + by = gcd(a, b) になります。
さらに変形してbでくくると b(qx+y) + rx = gcd(a, b)となり、
最初の (a, b)に関する問題が (b, r)に関する問題に置き換えられます。
つまり bs + rt = gcd(a, b)とすると、この式を満たすsとtを求める問題になります。
そして、 s t再帰的に求められるとすると、
係数を比較して (qx + y) = s, x = t \Leftrightarrow x = t, y = s - qxが成立します。

 qはコードにすると、a // b
 rはコードにすると a%b

上記のことをちょっと冗長ですが、コードで表現すると

# ax + by = gcd(a, b)
# returns (x, y, gcd(a, b))
def ext_gcd(a: int, b: int) -> tuple:
    if b == 0:
        return 1, 0, a
    q, r = a // b, a % b
    x, y, g = ext_gcd(b, r)
    s, t = y, x - q * x
    return s, t, g

最後により詳細な解説やわかりやすかったページを紹介します。

qiita.com

maspypy.com

かつっぱさんの空で書けるのかっこいいよなシリーズで、空で書くときのポイントが解説してあるのでおすすめです。
youtu.be


こちらでは拡張ユークリッドの互除法を行列で表現して、再帰的でない方法で書いています。
qiita.com