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


Коэффициенты первого диофантового уравнения

Коэффициенты второго диофантового уравнения

Система двух диофантовых уравнений

Матрица общего решения

Результат в виде строки

Проверка для первого уравнения

Проверка для второго уравнения

Рассматривается оригинальный алгоритм решения двух произвольных однородных линейных уравнений в целых числах. Автоматический расчет матрицы решений.

Пусть Нам надо решить систему из двух диофантовых уравнений

$2a-11b+13c=1&&62a+22b-73c=-31$

Несомненно можно решать эту систему так как делают все.

- Умножив первое уравнение на 31 и вычтя из второго мы получим классическое диофантовое уравнение с двумя переменными.

- Решив которое можно найти все целочисленные значения системы

Схема рабочая, несмотря на множество ручных вычислений

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

Он красив и понятен даже для школьников, знающих про вектора и матрицы.

Частично использован алгоритм, описанный вот в этой статье ( стр 36,37)

Он доработан, приведен к матричным операциям и обобщен на любые значения.

Алгоритм и его работу мы будем изучать на примере.

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

$система диофантовых уравнений$

Мы этот пример взяли по причине, что в интернете его решали и для него вывели общее решение. Так что есть с чем сравнивать.

1. Находим общее решения первого уравнения из заданной системы. Например пусть будет такое

8 14 20 -19 -30 -44 -1 1 0

$общее решение системы$

Как проверим что это верное равенство? Да просто умножим вектор коэффициентов первого уравнения на полученную матрицу

$Результат умножения$

Как видим ответ совпадает со свободным членом первого уравнения.

2. Теперь, раз мы нашли общее решение первого уравнения, давайте его подставим во второе.

То есть в уравнение $70a-31b+9c=9$ подставим наши значения

$общее решение системы$

Можно руками подставлять и сокращать подобное, но в матричном исчислении мы лишь умножаем вектор {70,-31,9} на нашу матрицу.

$Результат умножения$

То есть мы получили уравнение

$1140m+1919p+2764=0$

Но, обратите внимание, что во втором уравнении свободный член равен не нулю, а девяти.

То есть мы переписываем

$1140m+1919p+2764=9$

Переносим свободные члены в правую часть и получаем классическое диофантовое уравнение, которое можем решать легко.

$1140m+1919p=-2755$

Общее решение такое

$Переменная M$

$Переменная P$

3. А теперь делаем обратное преобразование.

То есть

вот в эту систему $общее решение системы$

мы вместо неизвестных подставляем найденные m и p.

В матричном исчислении это решается так:

Убираем из матрицы $Матрица решений$ последний столбец. Это свободные члены и они нам пока мешаются.

получили

$Матрица решений$

Умножаем эту матрицу на матрицу созданную из этих уравнений

$Переменная M$

$Переменная P$

$матрица диофантового уравнения$

получаем

$Результат умножения$

Последняя колонка это свободные члены, прибавим к ней ту колонку которую убирали в начале этого пункта

то есть к вектору {-22 36 -11} прибавляем {20 -44 0}

Получаем систему

$Результат умножения$

А следовательно общее решение системы двух диофантовых уравнений

приобретает вид

$общее решение системы$

Проверим, правильно ли посчитали

Для первого уравнения

$Результат умножения$

Для второго

$Результат умножения$

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

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

Почему? Да потому что вектор {-608 -2261 -3059} имеет НОД =19

и фактически наше общее решение имеет вид

$общее решение системы диофантовой$

Так как числа в скобках должны быть целыми, то обозначим их t и наше, уже точно окончательное общее решение системы двух диофантовых уравнений имеет вид

$общее решение системы диофантовой$