mod ライブラリで素数以外の法に関してできることを書きます．
制限なくできること
- 加算
- 減算
- 乗算
これらは，単に整数として演算した後に法で割って余りを求める (あるいはそれと同値なことをする) だけだから，できる．
除算
$\bmod M$ における $a/b$ というのは， 「$b$ にかけたら $a$ になる数」である．
できる場合
$(b, M) = 1$ ならば，一意に存在する．
- (存在)$\quad$ $bu + Mv = 1$ となる $u, v$ がとれるので，$x = au$ とすればよい．
- (一意性)$\quad$ $bx \equiv bx’ \equiv a$ ならば， $b(x - x’) \equiv 0$ だから，$x \equiv x’$となる．
特に $M$ が素数ならば， $b\not\equiv 0 \pmod M$ のとき，一意に存在する．
できない場合
$(b, M) \neq 1$ のときは，存在しないかもしれないし，複数あるかもしれない．
例
- $2x \equiv 3 \pmod 4$ となる $x$ は存在しない．
- $2x \equiv 2 \pmod 4$ となる $x$ は， $x = 1$, $x = 3$ の2つがある．
mod ライブラリでは，$(b, M) \neq 1$ の時に $a/b$ を実行すると， 実行時エラーにしている．
割り切れる除算
$a/b$ が整数になるとわかっている場合，$a/b \bmod M$ を求めるのに， $r := a\bmod bM$ を求めるという方法がある． $a = bMu + r$ とすると，$a/b = Mu + r/b$ であるから， $r/b$ は整数になるはずなので，普通に整数で割り算をすれば良い． $bM$ が大きな数になる可能性があって，int128 などが必要になるかもしれない．