# mod 逆元を求める [モジュラ逆数 - Wikipedia](https://ja.wikipedia.org/wiki/モジュラ逆数) どちらも $O(\log m)$ - [[フェルマーの小定理]] - 実装がわかりやすい - 法 $m$ が素数でないと使えない - [[拡張ユークリッドの互除法]] - 法 $m$ が素数でなくても使える - 正し、逆元の存在条件を満たすこと - $\mod m$ での $a$ の逆元が存在する条件は、 $m$ と $a$ が互いに素であること ## 拡張ユークリッドの互除法の利用 ### 原理 $ \begin{align} n \times n^{-1} &= 1 \pmod m \\ n \times n^{-1} -1 &= 0 \pmod m \end{align} $ 左辺は $m$ で割り切れる。 $q$ を適当な整数とする。 $ \begin{align} n \times n^{-1} - 1 &= m \times q \\ n \times n^{-1} + m \times (-q) &= 1 \tag{1} \end{align} $ 拡張ユークリッドの互助法の式は $ a \times x + b \times y = \mathrm{GCD}(a,b) $ （ $(x,y)$ を同時に求められる） これに当てはめると $ a \times a^{-1} + m \times q = \mathrm{GCD}(a,m) \tag{2} $ $a$ と $m$ が互いに素であれば、$(1)$ と $(2)$ が同じ形になる。 （逆元 $a^{-1}$ を求めたいだけなので、 $q$ は不要） ## Go による実装 ### 非再帰 ver ```go // 法　m での a の逆元を求める関数 func modInv(a int, m int) int { var b, u, v = m, 1, 0 for b != 0 { t := a / b a -= t * b a, b = b, a u -= t * v u, v = v, u } u %= m if u < 0 { u += m } return u } ``` `u` と `v` は、以下の $u$ と $v$ [ユークリッドの互除法#拡張された互除法 - Wikipedia](https://ja.wikipedia.org/wiki/ユークリッドの互除法#拡張された互除法) $ \begin{aligned} \begin{pmatrix} x & y \\ u & v \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -k_{h - 1} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{h - 2} \\ \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & -k_{2} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{1} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{0} \\ \end{pmatrix} \end{aligned} $ ### 再帰 ver 「[[拡張ユークリッドの互除法]]」を参照。