Линейные диофантовы уравнения с двумя переменными

Калькулятор решает линейные диофантовы уравнения с двумя переменными.

Эта страница существует благодаря следующим персонам

Timur

Timur

Создан: 2014-02-15 08:19:35, Последнее изменение: 2020-11-03 14:19:31

Сначала калькулятор, теория под ним.

PLANETCALC, Линейные диофантовы уравнения с двумя переменными

Линейные диофантовы уравнения с двумя переменными

Уравнение
 
Множество всех х
 
Множество всех y
 
x
 
y
 
Множитель для x
 
Множитель для y
 

Диофантово уравнение с двумя неизвестными имеет вид:

ax + by = c,

где a, b, c — заданные целые числа, x и y — неизвестные целые числа.

Для нахождения решений уравнения используется Расширенный алгоритм Евклида (исключая вырожденный случай, когда a = b = 0 и уравнение имеет либо бесконечно много решений, либо же не имеет решений вовсе).
Если числа a и b неотрицательны, тогда с помощью расширенного алгоритма Евклида мы можем найти их наибольший общий делитель g, а также такие коэффициенты x_g и y_g, что:
ax_g + by_g = g.

Утверждается, что если число c делится на g, то диофантово уравнение ax + by = c имеет решение; в противном случае диофантово уравнение решений не имеет. Это следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.

То есть если c делится на g, тогда выполняется соотношение:

a x_g (\frac{c}{g}) + b y_g (\frac{c}{g})=c,

т. е. одним из решений диофантова уравнения являются числа:

x_0 = x_g (\frac{c}{g})

y_0 = y_g(\frac{c}{g})

Если одно из чисел a и b или они оба отрицательны, то можно взять их по модулю и применить к ним алгоритм Евклида, как было описано выше, а затем изменить знак найденных коэффициентов x_0 и y_0 в соответствии с настоящим знаком чисел a и b соответственно.

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

Итак, пусть g = НОД (a,b), выполняется условие:
ax_0 + by_0 = c.

Тогда, прибавив к x_0 число \frac{b}{g} и одновременно отняв \frac{a}{g} от y_0, мы не нарушим равенства:

a(x_0 + \frac{b}{g}) + b(y_0 - \frac{a}{g}) = ax_0+by_0 + \frac{ab}{g}-\frac{ba}{g}=c

Этот процесс можно повторять сколько угодно, т. е. все числа вида:
x = x_0 + k \frac{b}{g}

y = y_0 - k \frac{a}{g},
где k принадлежит множеству целых чисел, являются множеством всех решений диофантова уравнения.

Ссылка скопирована в буфер обмена
PLANETCALC, Линейные диофантовы уравнения с двумя переменными

Комментарии