matthew as a q.

競技プログラミングメイン

フェルマーの小定理を用いたmod p上の逆元

フェルマーの小定理

$p, a$ が互いに素な自然数のとき、 $a^{p-1} \equiv 1\ \mathrm{mod}\ p$

$a^{p-2} \times a \equiv 1\ \mathrm{mod}\ p$

$p$ 上、 $a^{p-2}$ の逆元は $a$

参考

フェルマーの小定理の証明と例題 | 高校数学の美しい物語

分数と小数から広がる整数の世界 ~フェルマーの小定理からアルチン予想まで~ (数学への招待)

分数と小数から広がる整数の世界 ~フェルマーの小定理からアルチン予想まで~ (数学への招待)

作者: 中島匠一
出版社/メーカー: 技術評論社
発売日: 2016/11/12
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る