定义：
若 $acdot{k}equiv 1pmod{p}, a perp p$, 就说 $k$ 是 $a$ 模 $p$ 的乘法逆元. 记为 $k = a^{-1}$.
我个人习惯用 $ie(a)$ 表示 $a$ 模某数的逆元. ($inverse$ $element$)
性质：
-
$frac{a}{b}equiv acdot {b^{-1}} pmod{p}, b mid a.$
证明: $frac{a}{b} mod p = frac{a}{b}cdot b cdot b^(-1) mod p$, 化简得 $frac{a}{b} mod p = acdot b^(-1) mod p$.
-
$ie(x)$ 是积性函数
证明: 设 $x$ 是 $a$ 关于 $p$ 的逆元, $y$ 是 $b$ 关于 $p$ 的逆元, 即 $xa mod p = yb mod p = 1$, 则
$xayb equiv 1 pmod p$
$(ab)cdot (xy) mod p = 1$
即 $xy$ 是 $ab$ 关于模 $p$ 的逆元, 即 $ie(ab) = xy = ie(a)cdot ie(b)$.
-
$a^{-1} = a^{p-2}$
证明: 先证明 $a^(p-1) equiv 1 pmod p$.
首先, $a, 2a, 3a, ..., (p-1)a$，这些数 $mod p$ 的值互不相同.
用反证法可以证明: 假设 $icdot aequiv jcdot a pmod p (1 leq i, j leq p)$, 设 $i geq j$, 则 $(i-j)cdot a mod p = 0$, 由于 $a$ 与 $p$ 互质, 可以得到 $i-j$ 是 $p$ 的倍数, 又 $i-j < p$, 矛盾, 所以假设不成立.
由上述结论可知, $a, 2a, 3a, ..., (p-1)a mod p$ 的值与 $0, 1, 2, ..., p-1$ 一一对应(不一定按顺序对应), 将这些数相乘可以得到 $(p-1)!cdot a^{p-1} equiv {(p-1)!} pmod p$, 两边消去 ${(p-1)!}$, 得到 $a^{p-1} equiv 1 pmod p$.
又 $a^{p-1} = a cdot a^{p-2}$, 所以 $a cdot a^{p-2} equiv acdot a^{-1} pmod p$，即 $a^{-1}=a^{p-2}$.
应用：
见 http://www.cnblogs.com/lsdsjy/p/3920528.html Prime 一题。