solution

Nghịch đảo modular khi modulo là số nguyên tố

Với $p$ nguyên tố và $a \not\equiv 0 \pmod p$, định lý Fermat nhỏ cho ta $a^{p-1}\equiv 1\pmod p$, suy ra nghịch đảo:

$a^{-1} \equiv a^{p-2} \pmod p$

Cho $a$ và số nguyên tố $p$. In $a^{-1}\bmod p$ trong khoảng $[0,p)$. Nếu $a\equiv 0\pmod p$ (không khả nghịch) thì in $-1$.

Ví dụ

$3^{-1}\bmod 7 = 5$ vì $3\cdot5=15\equiv1\pmod 7$.