DiophantineSolver.py

# REFATH BARI
# 12/5/19
# PROGRAMMING ASSIGNMENT #4

print ("I will now find all solutions (x,y) to ax + by = c \n")

# TAKES USER INPUT FOR COEFFICIENTS
a = int(input("Enter a: "))
b = int(input("Enter b: "))
c = int(input("Enter c: "))

# CONFIRMS USER INPUT
print ("\nSolutions to " + str(a) +"x"+" + "+ str(b) +"y = "+ str(c))

# FUNCTION THAT FINDS GCD
def gcd(m,n):
    if m < n: 
        m,n = n,m
    while m % n != 0:
        m, n = n, m % n
    return n

# SET GCD TO VARIABLE SO AN INTEGER ISN'T CALLED
gcd = gcd(a,b)

# IF THERE's A SOLUTION, SOLVE! THE NESTED FOR LOOP SEARCHES BETWEEN THE RANGES GIVEN BY THE COEFFICIENTS

def yesman():
  if (c % gcd == 0):
    for i in range (-a,a):
      for j in range (-b,b): 
        if (a*j+b*i == c): 
          x = j
          y = i
          
          print ("\nThe GCD of (" + str(a)+","+str(b)+")"+" is " + str(gcd))

          print ("\n"+str(gcd)+" divides " + str(c) + "! A solution exists!")

          print ("\nSolutions of " + str(a) +"x"+" + "+ str(b) +"y = "+ str(c) + " are (x,y) = (" + str(x) + "+"+str(b)+"t" + ","+str(y)+"-"+str(a)+"t)")

          return None

  else:        
  
    print ("\nThe GCD of (" + str(a)+","+str(b)+")"+" is " + str(gcd))
  
    print ("\n"+str(gcd)+" doesn't divide " + str(c) + "! No solution exists!")

yesman()