Open5

モジュラ逆数を学ぶ

経緯

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

※合同式については下記が詳しい

https://mathtrain.jp/mod

モジュラ逆数とは

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

重要なポイントは

  • a のモジュラ逆数 a^{-1} が存在するのは、法 pa が互いに素である場合に限る。
  • p が素数の場合は必ず存在する。 (1 \le a < p であるから)

モジュラ逆数を求めるには、フェルマーの小定理を利用する。

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 ってでかすぎない...? (今更気づいたのかって感じだけど)

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

https://ja.wikipedia.org/wiki/モンゴメリ乗算
ログインするとコメントできます