为何部分整数模不存在乘法逆元？以模7与模9为例求解原因

一、为什么部分整数模不存在乘法逆元？ #

先从乘法逆元的本质定义说起：对于整数 a 和模数 m，如果能找到整数 b 使得 a*b ≡ 1 mod m（也就是 a*b 除以 m 余1），那 b 就是 a 在模 m 下的乘法逆元。

找不到逆元的核心原因很简单：当 a 和 m 的最大公约数（gcd）大于1时，逆元必然不存在。

• 假设 gcd(a, m) = d > 1，那 a 可以拆成 d*k，m 拆成 d*n（k、n 都是整数）。
• 此时 a*b = d*k*b，这个结果除以 m=d*n 的余数肯定是 d 的倍数（整个式子都是 d 的倍数）。
• 但1并不是 d 的倍数（毕竟 d>1），所以不管 b 取什么整数，a*b mod m 都不可能等于1，自然就找不到逆元了。

举个接地气的例子：模9下的数字3，gcd(3,9)=3>1，你试遍所有整数 b，3*b的结果是3、6、9、12...，除以9的余数只能是0、3、6，永远到不了1，所以3在模9下就没有逆元。

二、为什么整数模7满足乘法逆元性质，模9却不满足？ #

这完全取决于模数本身的性质：

• 模7的情况：7是质数。质数的特性是，它和所有小于它的非零整数的最大公约数都是1（质数除了1和自身没有其他因数）。也就是说，模7下的每一个非零整数（1、2、3、4、5、6），都和7互质，所以每个数都能找到对应的乘法逆元。比如：

  • 3*5=15 ≡1 mod7，所以3的逆元是5；
  • 2*4=8≡1 mod7，所以2的逆元是4。
    所有非零元素都有逆元，自然满足乘法逆元的完整性质。

• 模9的情况：9是合数（9=3*3）。这里面存在和9不互质的非零整数，比如3、6，它们和9的gcd是3>1，按照前面的结论，这些数就没有乘法逆元。既然存在没有逆元的元素，整个模9的集合就没法满足“所有非零元素都有乘法逆元”的性质了。

内容的提问来源于stack exchange，提问作者Jason Lu