CODEWITHSUNDEEP
pythonalgebradiophantine
DarkRunner
DarkRunner

Reputation: 449

Finding solutions to Diophantine

I created a Python Program to find all solutions to a diophantine equation. Unforunately, the program just stops printing statements, with no errors. I inserted breakpoints, but could not resolve the problem:

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)))

Essentially, the program uses the Euclidean Algorithm to first test if there are solutions to the diophantine. If there are, the program uses a nested for loop to search for integer values for the variables of a diophantine to produce the correct solutions. But for some reason, my code just doesn't work and there are no error messages!

Upvotes: 1

Views: 1035

Answers (2)

K_3
K_3

Reputation: 83

Or you can try this code modified_gcd to get the solution for the Diophantine equation. Over here I am not checking for the existence of the solution(can be done easily) but assuming that the solution exists.

"""
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:])

Output Will be:

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

No need to iterate through all the values of x and y.

Upvotes: 2

furkanayd
furkanayd

Reputation: 882

Try to use this implementation, you have a problem with gcd function:

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))

Upvotes: 1

Related Questions