拡張ユークリッドの互除法を理解する
拡張ユークリッド互除法について、わかりやすかったページなどを紹介しつつ、まとめていきます。 何も見ないで書けるくらい理解するのが目標です。
ユークリッド互除法については前回の記事をご参照ください。
vermee81-coding-memo.hatenablog.jp
拡張ユークリッド互除法は整数a, bが与えられた時に、最大公約数だけでなく、 を満たすとを求めることができます。
まずはユークリッドの互除法のようにを式で表します。
(はそれぞれをで割った時の商と余り)
上記の式を に代入すると、 になります。
さらに変形してbでくくるととなり、
最初のに関する問題がに関する問題に置き換えられます。
つまりとすると、この式を満たすsとtを求める問題になります。
そして、とが再帰的に求められるとすると、
係数を比較してが成立します。
はコードにすると、a // b
はコードにすると 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
最後により詳細な解説やわかりやすかったページを紹介します。
かつっぱさんの空で書けるのかっこいいよなシリーズで、空で書くときのポイントが解説してあるのでおすすめです。
youtu.be
こちらでは拡張ユークリッドの互除法を行列で表現して、再帰的でない方法で書いています。
qiita.com