这是一篇发布于 1724 天以前的旧文.其中的部分内容可能已经过时.
当我们取模的时候,被模数很大,无法直接计算其值,我们就会用取模运算的下面两个性质:
那么对于除法,是否也满足这个式子呢?
很显然也很遗憾,不满足.很容易找到反例:
那么当除数很大的时候怎么算呢?这就要用到乘法逆元了.
在阅读本文之前建议先阅读:欧几里德算法与拓展欧几里德算法详解 与 欧拉函数,费马小定理与欧拉定理详解.
本文中有大量 KaTeX 公式,请确保浏览器支持,否则卡到超乎你想象.
Windows 可以在控制面板-程序-卸载程序-卸载\更新 Windows 组件中卸载IE浏览器.
前面已经说了,乘法逆元可以在进行除法时让等式满足"分配律".下面给出证明:
从简单而暴力的方法开始~ 当 p 很小的时候,我们可以枚举 1 到 p-1,判断这个式子是否成立:
(在这里我要把 DYT 同学批判一番,在他的博客 数论初步:乘法逆元与几种求法 - CSDN博客 里居然写道:"对于给定的 a 和 p,有且仅有一个数是它的逆元"这一显然错误的结论......)
关于扩展欧几里德欧几里德的介绍参见:欧几里德算法与拓展欧几里德算法详解.
对于刚才的同余方程,可以变形为以下这个"裴蜀等式":
ax+py=1
接下来就可以用扩展欧几里德解了.具体解法在欧几里德算法与拓展欧几里德算法详解这篇文章中已经详细介绍,这里不赘述.贴代码:
费马小定理和欧拉定理在 欧拉函数,费马小定理与欧拉定理详解 这一篇里已经有详细的介绍.由于费马小定理是欧拉定理的一般情况,我们下面就只介绍欧拉定理求逆元.
可以化成:
以 O(N) 线性时间复杂度递推逆元的方法 线性时间复杂度递推逆元的方法")
请勿填写无意义邮箱或发表无关评论,否则会被视为垃圾评论.