Module cp_library_rs::number_theory::ext_euclid

source ·
Expand description

拡張ユークリッド互除法

Functions

  • ext_gcd
    拡張ユークリッド互除法により， $ax + by = \gcd(a, b)$ を満たす $(x, y, \gcd(a,b))$ を求める．
  • inv
    拡張ユークリッド互除法によりモジュラ逆元を計算する．