フェルマーの小定理
<ul>
<li>$a^{p-1}\equiv 1{\pmod {p}}$
を変形して</li>
<li>$a \times a^{p-2}\equiv 1{\pmod {p}}$
なので</li>
<li>$a^{-1} \equiv a^{p-2} {\pmod {p}}$</li>
</ul>
Python: <code>pow(a, p - 2, p)</code>
Python3.8から素直に <code>pow(a, -1, p)</code>できる
フェルマーの小定理はPが素数であることを要求する
<ul>
<li>素数でない場合には<a href="/ja/%E6%8B%A1%E5%BC%B5%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E4%BA%92%E9%99%A4%E6%B3%95">拡張ユークリッド互除法</a>を使う　<a href="/ja/P%E3%81%8C%E7%B4%A0%E6%95%B0%E3%81%A7%E3%81%AA%E3%81%84mod%20P">Pが素数でないmod P</a></li>
<li>この場合はaとpが互いに素であれば良い
python</li>
</ul>
<pre><code>def mod_inverse_ee(a, m):
 &quot;&quot;&quot;
 Solve ax mod m = 1 with extended euclidean.
 x = a^-1.
 &quot;&quot;&quot;
 x, y, g = extended_euclidean(a, m)
 assert g == 1
 return x % m
</code></pre>
<ul>
<li><a href="/ja/%E5%89%B0%E4%BD%99%E7%BE%A4%E3%81%A7%E3%81%AE%E9%99%A4%E7%AE%97">剰余群での除算</a></li>
</ul>
<blockquote>
nのmodulo pでの逆元は<a href="/ja/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86">フェルマーの小定理</a>より
 pow(n, p-2, p)
 で求められます。計算量はO(logp)です。<a href="/ja/%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0">二項係数</a>とかでよく使います。
<a href="https://qiita.com/Kentaro_okumura/items/5b95b767a2e691cd5482">https://qiita.com/Kentaro_okumura/items/5b95b767a2e691cd5482</a>
</blockquote>

mod Pでの逆元