Решение линейных диофантовых уравнений

# решение линейных диофантовых уравнений

# вычисление наибольшего общего делителя чисел x, y
gcd = lambda x, y : x if not(y) else y if not(x) else gcd(y, x%y)

# нахождение частного решения соотношения Безу ax + by = 1 для взаимно простых a, b
bezout = lambda a, b : bezout(b, a)[::-1] if a < b else (0, 1) if b == 1 else (lambda x, y, k : (x, y - k*x))(*bezout(a%b, b), a//b)

# решение диофантова уравнения ax + by = c
# x = u t + v
# y = w t + s
# возвращает результат в виде u, v, w, s или всех нулей, если решений нет
diophantus = lambda a, b, c : (0, 0, 0, 0) if c % gcd(a, b) else diophantus(*map(lambda x : x/gcd(a, b), (a, b, c))) if gcd(a, b) != 1 else (lambda a, b, c, x0, y0 : (b, x0*c, -a, y0*c))(a, b, c, *bezout(a, b))

# тесты:
print(gcd(17*3, 17*5))
print(bezout(981, 991), 99*981 - 98*991)
print("x = %d * t + (%d),\ty = %d * t + (%d)" % diophantus(17*3, 17*5, 17*4))