Коэффициенты первого диофантового уравнения
Коэффициенты второго диофантового уравнения
Система двух диофантовых уравнений
Вид уравнения
Вид уравнения
Матрица общего решения
Матрица общего решения
Результат в виде строки
Проверка для первого уравнения
Проверка для первого уравнения
Проверка для второго уравнения
Проверка для второго уравнения

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

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

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  и наше, уже точно окончательное общее решение системы двух диофантовых уравнений имеет вид

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

Еще несколько примеров, и небольшие ремарки к алгоритму.


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

ответ

a=517k+748\\b=952k+1378\\c=726k+1051

 еще пример

\begin{array}{lcl}-a+7b+c-53d+13d=-100\\2a+4b-16c-37d-32d=0\end{array}

ответ

a=-116p-85m+139q-117//b=-14p+5m+0q+1//c=-18p-14m+20q-1//d=0p+2m-2q+2//e=0p+0m+q-9

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

Теперь что калькулятор не может. 

Очень сильно не любит уравнения с нулевыми коэффициентами. Особенно первое. Например, вот такую систему

калькулятор не решит.

Вид уравнения
Вид уравнения

Ну как не решит? Решит, если прибегнем к уловке, и постараемся убрать все нулевые коэффициенты

Прибавим к первому уравнению, второе. Таким образом в первом уравнении исчезают все нулевые коэффициенты и калькулятор сможет решить эту систему

Система двух диофантовых уравнений
Вид уравнения
Вид уравнения
Матрица общего решения
Матрица общего решения

 Проверка показывает что общее решение корректно.

И еще пример

Система двух диофантовых уравнений
Вид уравнения
Вид уравнения
Матрица общего решения
Матрица общего решения

 Удачи  в расчетах!!

 

Copyright © 2020 AbakBot-online calculators. All Right Reserved. Author by Dmitry Varlamov