Онлайн калькулятор: Линейные диофантовы уравнения с двумя переменными

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

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

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

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

Коэффициент а

Коэффициент b

Коэффициент с

Уравнение

Множество всех х

Множество всех 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 Онлайн калькуляторы

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

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

Timur

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

Похожие калькуляторы

Комментарии

PLANETCALC Онлайн калькуляторы

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

Похожие калькуляторы

Комментарии

Поделиться этой страницей