[基础数论]模的逆 |
您所在的位置:网站首页 › 逆运算的逆运算 › [基础数论]模的逆 |
前言
在学习本节内容前,请确保已完成了同余方程的学习。 模的逆 引入很多题目都会要求我们对答案取模。 如果运算中只有加法、乘法当然没问题。 但是如果有除法就完蛋了。 所以我们考虑将除法转换成乘法, 即对于 \(a / b\) ,我们要找到一个数 \(x\) 使得 \(ax\) 在模 \(m\) 意义下, \(x\) 等同于 \(\frac{1}{b}\) ,我们把 \(x\) 写作 \(b^{-1}\) 。 定义 给定整数 \(a\) ,且满足 \((a,m)=1\) ,称 \(ax \equiv 1 \pmod m\) 的一个解为 \(a\) 模 \(m\) 的逆。注: \(x\) 既是 \(a^{-1}\) ,则满足 \(ax \equiv 1 \pmod m\). 扩欧求逆在同余方程的学习中,我们清楚同余方程 \(ax \equiv 1 \pmod m\) 等价于 \(ax+my = 1\) . 运用上不定方程的知识求解即可。 费马小定理求逆 设 \(p\) 是一个质数, \(a\) 是一个正整数且 \(p \nmid a\) ,则 \(a^{p-1} \equiv 1 \pmod p\)。我们将等式两边同除一个 \(a\) ,得到 \(a^{p-2} \equiv a^{-1} \pmod p\). 我们就得到: \(a^{p-2}\) 就是 \(a\) 在模 \(p\) 意义下的逆元。 一般用快速幂去求即可。 注:用费马小定理求逆,必须满足前提条件。 费马小定理证明:现考虑 \(p-1\) 个整数: \(a,2a,3a,…,(p-1)a\). 因为 \(p\) 为质数,且 \(p \nmid a\) ,这 \(p-1\) 个整数都不能被 \(p\) 整除。 然后我们考虑反证这些数模 \(p\) 不同余。 设 \(ja \equiv ka \pmod p\) ,其中 \(1 \le j < k \le p-1\) . 根据不定方程笔记的定理5推论,由于 \((a,p)=1\) ,得到 \(j \equiv k \pmod p\). 因为 \(p\) 是质数, \(j,k\) 又满足 \(1 \le j < k \le p-1\) ,显然不成立。 故得证。 综上,我们可以得到 \(a,2a,…,(p-1)a\) 满足模 \(p\) 有 \(1,2,…,p-1\). 我们将其全部乘起来,得到: \(a * 2a * 3a * … * (p-1)a \equiv 1 * 2 * 3 * … * (p-1) \pmod p\) . 推得:\(a^{p-1}*(p-1)! \equiv (p-1)! \pmod p\) . 再一次根据不定方程笔记的定理5推论,因为 \(((p-1)!,p)=1\) ,得到 \(a^{p-1} \equiv 1 \pmod p\). 证毕。 线性递推求逆在满足 \(p\) 是质数,\(n < p\) 时,线性递推求 \(1\) 至 \(n\) 在模 \(p\) 意义下的逆元。 \(1^{-1} = 1\) ,\(i^{-1} = (p - p/i) (p \% i)^{-1} \pmod p\) 证明:由带余除法得: \(p = ki + r\) ,其中 \(0 \le r < i\) , 故 \(ki + r \equiv 0 \pmod p\). 两边同乘 \(i^{-1}r^{-1}\) 得到: \(kr^{-1} + i^{-1} \equiv 0 \pmod p\). 移项得: \(i^{-1} \equiv -kr^{-1} \pmod p\) . 即: \(i^{-1} \equiv -(p/i)r^{-1} \pmod p\). 如果要避免负数,因为 \(pr^{-1} \equiv 0 \pmod p\). 所以 \(pr^{-1} + (-p/i)r^{-1} \equiv (-p/i)r^{-1} \pmod p\). 即: \((p-p/i)r^{-1} \equiv (-p/i)r^{-1} \pmod p\). 代回原式即为 \(i^{-1} \equiv (p-p/i)r^{-1} \pmod p\). 即 \(i^{-1} \equiv (p - p/i)(p \% i)^{-1}\). 证毕。 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |