この記事のオリジナル は，2023年3月12日に公開されました．
文脈は，競技プログラミングです．剰余を扱う 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 などが必要になるかもしれない．
たとえば，初項 $a$，公比 $a$，項数 $x$ の等比数列の和を，$\text{mod } M$ で求めたいとする．$r - 1$ と $M$ が互いに素でないとすると，和 $a(r^x - 1)/(r - 1)$ を求めるのに，$\text{mod } M$ で $a(r^x - 1)$ を $r - 1$ で割るというわけにはいかない．そこで，$a(r^x - 1)$ を $\text{mod } (r-1)M$ で求める．この値は当然 $r - 1$ の倍数になるので，$r - 1$ で割って，求める値が得られる．