丢番图的解决方案

Question

我创建了一个Python程序来寻找丢番图方程的所有解。不幸的是，程序只是停止打印语句，没有错误。我插入了断点，但无法解决问题：

print ("I will now solve a diophantine equation of form ax + by = c, where (a,b,c) are the coefficients and (x,y) are the solutions\n")

a = int(input("Enter a: "))
b = int(input("Enter b: "))
c = int(input("Enter c: "))

print ("\nGiven coefficients ("+str(a)+","+str(b)+","+str(c)+"), I will now find all solutions (x,y) to the given diophantine of " + str(a) +"x"+" + "+ str(b) +"y = "+ str(c))

#IS THERE A SOLUTION?

def gcd(m, n):
  while n:
    m
    n = n
    m % n
  return m

gcd = gcd(a,b)

if (c % gcd != 0):
  print ("\nYeah no, can't solve this.\n")
else:
  for i in range (0,a):
    for j in range (0,b): 
      if (a*j+b*i == c): 
        x = j
        y = i
        print ("\nThe solutions to the diophantine " + str(a) +"x"+" + "+ str(b) +"y = "+ str(c) + " are (x,y) = (" + str(x) + "+"+str(b)+"t" + ","+str(y)+"-"+str(a)+"t)")

print ("\nThe GCD of (" + str(a)+","+str(b)+")"+" is " + str(gcd(a,b)))

本质上，该程序使用欧几里德算法，首先测试是否有解决方案的丢番图。如果存在，则程序使用嵌套的for循环来搜索丢番图变量的整数值，以生成正确的解决方案。但出于某种原因，我的代码不工作，没有错误消息！

Answer 1

或者您可以使用这个代码modified_gcd来得到丢番图方程的解。在这里，我不是检查解决方案的存在(可以很容易地完成)，而是假设解决方案是存在的。

"""
modified_gcd(int a,int b,int x, int y)
int a = value of a.
int b = value of b.
int x = always set as 0.
int y = always set as 0.

"""
def modified_gcd(a,b,x,y):
    if b==0:
        x=1
        y=0
        return [a,x,y]
    x1=0
    y1=0
    d,x1,y1 = gcd(b,a%b,x1,y1)
    x = y1
    y = x1-y1*(a//b)
    return [d,x,y]

print (modified_gcd(47,30,0,0)[1:])

产出将是：

[-7, 11].  # The value of x and y.

不需要迭代x和y的所有值。

Answer 2

尝试使用此实现时，gcd函数会出现问题：

from math import *

print ("I will now solve a diophantine equation of form ax + by = c, \
        where (a,b,c) are the coefficients and (x,y) are the solutions\n")

a = int(input("Enter a: "))
b = int(input("Enter b: "))
c = int(input("Enter c: "))

print ("\nGiven coefficients ("+str(a)+","+str(b)+","+str(c)+"), \
        I will now find all solutions (x,y) to the given diophantine of " \
        + str(a) +"x"+" + "+ str(b) +"y = "+ str(c))

#IS THERE A SOLUTION?

def euclid_algo(x, y, verbose=True):
    if x < y:
        return euclid_algo(y, x, verbose)
    while y != 0:
        if verbose: print('%s = %s * %s + %s' % (x, floor(x/y), y, x % y))
        (x, y) = (y, x % y)

    if verbose: print('gcd is %s' % x) 
    return x

gcd = euclid_algo(a,b)

if (c % gcd != 0):
  print ("\nYeah no, can't solve this.\n")
else:
  for i in range (0,a):
    for j in range (0,b): 
      if (a*j+b*i == c): 
        x = j
        y = i
        print ("\nThe solutions to the diophantine " + str(a) +"x"+" + "+ \
                str(b) +"y = "+ str(c) + " are (x,y) = (" + str(x) + "+"+\
                str(b)+"t" + ","+str(y)+"-"+str(a)+"t)")
    print("Loop :" + str(i) +" - "+str(j))

print ("\nThe GCD of (" + str(a)+","+str(b)+")"+" is " + str(gcd))