Общее решение диофантова уравнения

Question

Написал программу для решения диофантова уравнения вида 45x-128y=177. Имеется два вопроса:

а как сделать так, чтобы выводилось общее решение диофантова уравнения в виде формулы, зависящей от параметра?
можно ли тут реализовать вывод данных, полученных на промежуточных этапах решения задачи, а не только конечный результат?

def nod(m, n):
    return m if n == 0 else nod(n, m % n)


a = int(input('Введите коэффициент a: '))
b = int(input('Введите коэффициент b: '))
c = int(input('Введите коэффициент c: '))
print()
assert c != 0

nod_ab = nod(abs(a), abs(b))
if c % nod_ab:
    print('Решения нет')
else:
    a //= nod_ab
    b //= nod_ab
    c //= nod_ab

    for i in range(abs(a)):
        if (c - b * i) % a == 0:
            y = i
            x = (c - b * y) // a
            if x < 0:
                x += b
                y -= a
            print('x = ', x, 'y = ', y, '\n',
                  'Проверка: ', ((a*x)+(b*y)), ' = ', c, ' - Левая часть равна правой части уравнения')
            break
    else:
        print('Решения нет')

Answer 1

уравнение вида ax + by = c в случае, если известно хотя бы одно решение (x0, y0) имеет следующие решения:

x = x0 + k * b / НОД(a, b)
y = y0 + k * a / НОД(a, b)

т.е. задача сводится к нахождению хотя бы одного решения и вычислению gcd(a, b)

т.к. код примерно такой:

import math

def gcd(a, b):
    if a == 0:
        return (b, 0, 1)

    res = gcd(b % a, a)

    x = res[2] - (b // a) * res[1]
    y = res[1]

    return (res[0], x, y)


# найти любое решение
def find_solution (a, b, c):
    g, x0, y0 = gcd(abs(a), abs(b))

    if c % g != 0:
        return (False, 0, 0)

    x0 *= c // g
    y0 *= c // g

    if a < 0:
        x0 *= -1

    if b < 0:
        y0 *= -1

    return (True, x0, y0)


# Определить любое решение
a, b, c = 45, -128, 177
res = find_solution(45, -128, 177)

if res[0] is True:
    print(f"x = {res[1]} + k * {b / math.gcd(a, b)}")
    print(f"y = {res[2]} + k * {a / math.gcd(a, b)}")
else:
    print("Решений нет")

вывод отрицательных значений надо только красиво оформить :)

БЛОГ НА HUSL

Общее решение диофантова уравнения

Ответы (1 шт):