モジュラ逆数を学ぶ

https://zenn.dev/log5/scraps/330d042b0602e9 の発展で、modを取ろうとしたら割り算で壁にぶつかったので、ちゃんと合同式の割り算について学ぼうと思いました。

※合同式については下記が詳しい
https://mathtrain.jp/mod

$p$ を法として、ある整数 $a$ について、 $ax \equiv 1 \mod p$ が成立するような数 $x$ をモジュラ逆数と呼ぶ。
モジュラ逆数 $x$ を $a^{-1}$ と書くこともある。

重要なポイントは

モジュラ逆数を求めるには、フェルマーの小定理を利用する。
https://mathtrain.jp/fermat_petit

$a^p \equiv a \pmod p$

特に $p$ が素数なら $a^{p-1} \equiv 1 \pmod p$

これより、 $p \ge 3$ かつ $p$ が素数の場合、 $a^{-1} \equiv a^{p-2} \pmod p$

よって、 $x$ を割りたいときは、 $x^{-1}$ つまり $x^{p-2}$ を掛ける。

いや、ちょっと待って... $p=1000000007$ ってでかすぎない...? （今更気づいたのかって感じだけど）

モンゴメリ乗算とかもセットで勉強すべき事案か...