math - 找到两个整数的最大同余模数？

Question

给定两个整数，有没有一种简单的方法可以找到它们的最大同余模数？即a % n == b %n，或者甚至枚举所有这些？显然，我可以尝试比它们少的每个值，但似乎应该有更简单的方法。

我尝试用 gcds 做一些事情，但是你得到的只是 a % n == b % n == 0，这并不像我希望的那样酷，而且我很确定这不一定是最大的 n.

有任何想法吗？

Answer 1

如果 a 和 b 是数字，那么我们考虑：

a = nx + r
b = ny + r

其中 n 是我们想要找到的模数，r 是公共余数。所以，

a - b = n(x - y)

最大 n 是通过 x - y = 1 实现的。所以，

n = a - b

（如果我正确理解了这个问题。）