如何求解公式（y * known_number）％145 = 81中的y而没有循环

Question

是否可以在没有循环的情况下求解此方程中的y？

known_number = 7
(y * known_number) % 145 == 81

[我正在使用循环，但是我在想，因为它是简单的乘法，所以可能有一个公式可用于无循环地求解它，或者存在吗？

这是我用来解决它的代码：

known_number = 7
for y in range(145):
   if (y * known_number) % 145 == 81:
       print(y)  # -> 53

Answer 1

还有另一种方法，但是如果仔细观察，它会具有不同类型的循环。无论如何，可以这样解决：

y*known_number ≡ 81 (mod 145)
y ≡ 81 * known_number ^ -1 (mod 145)

仅在known_number时有效” [[有 modular multiplicative inverse模145，当已知数和模数之间的GCD为1时会发生（gcd(7, 145) = 1，因此在这种情况下它将起作用）。这里的逆是83，因此我们计算y = 81 * 83 % 145 = 53。

[通常，您可以使用扩展的欧几里得算法，但也可以通过其他各种方法，例如pow(known_number, 111, 145)，其中111为totient(145) - 1，来找到逆。除非您具有数字的素因数分解，否则计算求生数并不容易。 pow函数隐藏了一个循环，但比强行强制方程式要短得多。