algorithm - 求方程的积分解

Question

这是一个更大问题的一部分。它实际上是一个数学问题。因此，如果有人可以指导我使用任何算法来获得此问题的解决方案或伪代码会有所帮助，那就太好了。

问题。给定一个方程检查它是否有积分解。 例如:

(26a+5)/32=b

这里的a是一个整数。是否有一种算法可以预测或查找 b 是否可以是整数。我需要一个不特定于这个问题的通用解决方案。等式可以变化。谢谢

Answer 1

您的问题是线性丢番图方程的示例。关于那个，Wikipedia says :

This Diophantine equation [i.e., a x + b y = c] has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if (x, y) is a solution, then the other solutions have the form (x + k v, y - k u), where k is an arbitrary integer, and u and v are the quotients of a and b (respectively) by the greatest common divisor of a and b.

在这种情况下，(26 a + 5)/32 = b 等于 26 a - 32 b = -5。未知数系数的gcd为gcd(26, -32) = 2。由于-5不是2的倍数，所以无解。

一般的丢番图方程是未知数的多项式，只能通过更复杂的方法求解(如果有的话)。网络搜索可能会找到针对该问题的专门软件。