编写一个程序来检查线性方程是否具有正整数解

Question

我正在尝试编写一种算法来确定线性方程,特别是ax + by = c的形式,对于给定的a,b,c是否具有正整数解.它需要是有效的,因为数字a,b和c可以在0 <= a,b,c <= 10 ^ 16的范围内.我该如何处理这个问题？

由于它是一个丢番图方程式,我试图检查a和b的GCD是否除以c,但这样我无法区分正,负或零解.

确定线性不定方程的非负值解存在性的算法

我在这里找到了一个解决方案,但我并不太明白.也许有人可以为我简化它？因为这个很通用,我只对2个变量的方程感兴趣.

Answer 1

存在

Bezout的身份确实告诉你,使用a和b的最大公约数(gcd)d,我们有:

i)d是可以写为ax + by的最小正整数,以及ii)ax + by形式的每个整数是d的倍数.

你去吧 如果c可以被d分割,你就有了解决方案.

标志

从任何一对解决方案中,我们都可以获得所有其他解决方案.因此,我们可以看出它们是否可以是积极的.仍然来自同一身份,我们得到:

当已经计算了一对Bézout系数(x0,y0)时(例如,使用扩展欧几里德算法),所有对都可以以形式表示

现在我们已经完成了.你所要做的就是:

1. 使用扩展的欧几里德算法,它将给你d和一对(x0,y0)的ax + by = d
2. 检查d是否除以c.如果不是,则不存在解决方案.如果是,则将x0和y0乘以(c/d)以得到等式的解.
3. 如果x0和y0现在都有相同的符号,那么你就完成了.如果它是积极的,你有积极的解决方案,如果它是负面的,你没有.
4. 如果x0和y0具有不同的符号,请选择最小(绝对值)k来更改负整数的符号.
   • 也就是说,如果x0是负数,那么取gcd(a,b),如果是y0,则取gcd(a,b).适当地舍入k以得到与x0(resp.y0)具有不同符号的整数x1(相应的y1).我认为你应该将它向下舍入(至-infinity)所以要注意负数的整数除法,它们向0舍入.
   • 计算 gcd(a,b)
   • 如果它们都是正数,那么您只需找到两个正整数解.如果轻拍一个数字的符号翻转另一个数字,则无法找到正解.

请注意,它与您链接的问题有关,但变量的数量不同.这是因为你只有两个变量.