逆元 学习笔记 #

问题背景 #

我们经常遇到一些需要对运算结果取模的问题. 由于加法、减法、乘法对于模运算都是封闭的, 可以在大量运用取模运算防止溢出. 但除法对于模运算来说并非封闭的, 本来可以整除的情况在取完模之后没法进行除法运算了, 而把之前的结果全部保存又会导致溢出. 因此我们需要找到一种能够在一定程度上代替除法的操作.

逆元 #

参考加法运算中的相反数, 以及乘法运算中的倒数, 对于模意义下的除法存在逆元, 同样有 $a\times a^{-1} \equiv 1\ (mod\ p)$ . 那么对于给定的 $a$ 和 $p$ , 怎样计算出 $a$ 在模 $p$ 意义下的逆元呢? 下面介绍两种常见的求解逆元的方法: 费马小定理和扩展欧几里得算法.

费马小定理 #

费马小定理告诉我们, 若存在整数 $a, p$ , 满足 $gcd(a, p) = 1$ , 则有 $a^{p - 1}\equiv 1\ (mod\ p)$ . 如果 $p$ 已经是素数了, 那么只要 $p\nmid a$ , 自然有 $a^{p - 1}\equiv 1\ (mod\ p)$ , 即 $a\times a^{p - 2} \equiv 1\ (mod\ p)$ . $a^{p - 2}$ 恰好就是 $a$ 的逆元. 我们利用快速幂计算出 $a^{p - 2}$ 即可.

扩展欧几里得算法 #

扩展欧几里得算法用于构造裴蜀定理的合法解, 即对于 $a, b$ , 求出一对 $x, y$ , 满足 $ax + by = gcd(a, b)$ . 对于 $ax\equiv 1\ (mod\ p)$ , 可以转化为 $ax + py\equiv 1\ (mod\ p)$ , 利用扩展欧几里得算法求解.