最近我阅读了扩展欧几里德算法，该算法用于找出关于 MOD 的数 N 的模逆，使得 gcd(N, MOD)=1.
但是我对如果 gcd(N,MOD)!=1 如何求一个数的模逆有疑问？
最佳答案
如果 gcd(N,MOD)!=1 N 的模逆不存在。
但是，在某些情况下，您仍然可以除以 N，即找到一个 X，使得 A = N * X (mod MOD)。当 gcd(N,MOD) 除 gcd(A,MOD) 时，这是可能的。要找到这样的 X，只需将 A、N 和 MOD 除以 gcd(N,MOD)，然后照常进行(gcd(N', MOD') 则为 1)。
关于algorithm - 数的模逆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25322763/