理解Modular Multiplicative Inverse及Python实现中%运算符的作用

首先明确模逆的核心定义 #

模乘逆元的定义本身就依赖模运算：如果整数x满足 (a * x) mod m = 1，则x是a在模m下的乘法逆元。Python中的%就是实现模运算（取非负余数）的操作符，是判断逆元的基础，你手写计算5 mod7的逆元时，其实也默认用到了「15除以7余1」的规则，只是没有显式写取余操作而已。

代码中三次取余的作用分别如下 #

• 第一次a % m：做输入兼容。如果传入的a大于m、或是负数，先取余可以把a转换成[0, m-1]区间内的等价余数，比如a=14、m=11时，14%11=3，和a=3的逆元计算结果完全一致，不用再对更大的a做额外处理。
• 第二次x % m：属于防御性编程。当前代码里x遍历的是1~m-1，所以x%m结果就是x本身，看起来冗余；但如果后续调整了x的遍历范围（比如扩大到超过m的区间），这个取余操作就能保证x始终落在模m的余数范围内，逻辑不会出错。
• 第三次((a%m)*(x%m)) % m：是逆元判断的核心要求。我们要判断的是乘积模m的结果等于1，而非乘积本身等于1。比如你给出的示例中34=12，本身不等于1，正是因为最后做了%11得到1，才判断4是逆元，和你手写的5 mod7求逆元的逻辑完全一致。如果没有这次取余，你举的53=15的例子就会因为15≠1判断不成立，完全得不到正确结果。

多次取余的额外优势 #

在a和m数值很大的场景下，先对a、x取余再计算乘积，最后再取余，可以大幅降低计算量，避免出现超大整数的运算，提升代码运行效率。

内容的提问来源于stack exchange，提问作者William Zebrowski