title: Why the program does not correctly search for the general solution of the Diophantine equation
body: <p>I wrote a program that looks for a general solution to a Diophantine equation, but the solution is not entirely correct when I check the online calculator. For example, for the equation &quot;45x-128y=177&quot; the solution in general form should be &quot;x=6549-128k&quot; and &quot;y=2301-45k&quot;, but I get &quot;x=6549+k<em>128&quot; and
  &quot;y=-2301+k</em>45&quot;.
  My code:</p>
  <pre><code>import re
  
  def extended_gcd(a, b):
      if a == 0:
          return (0, 1)
  
      (x, y) = extended_gcd(b % a, a)
  
      return (y - (b // a) * x), x
  
  
  def gcd(a, b):
      if b == 0:
          return a
      return gcd(b, a % b)
  
  
  def main():
      s = input('Enter the Diophantine equation: ')
      s1 = re.findall(r'\d+', s)
      a = int(s1[0])
      b = int(s1[1])
      c = int(s1[2])
  
      d = gcd(a, b)
      print(f'GCD({a},{b}) = {d}')
  
      if d % c != 0:
          print('This equation has an infinite set of solutions')
          a1 = a // d
          b1 = b // d
          print(f'Short equation: {a1}s + {b1}t = {1}')
          (s, t) = extended_gcd(a1, b1)
  
          x0 = (c // d) * s
          y0 = (c // d) * t
  
          print(&quot;General solution&quot;)
          print(f&quot;x = {x0} + k * {b // d}&quot;)
          print(f&quot;y = {y0} + k * {a // d}&quot;)
      else:
          print('This equation has no solution')
  
  
  if __name__ == &quot;__main__&quot;:
      main()
  </code></pre>
  <p>What is the problem and how to solve it?</p>