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

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

Ax+By+....Cw+Ez=F
Коэффициенты диофантового уравнения и свободный член (через пробел)
Исходное диофантовое уравнение
Общее решение исходного уравнения
Решение в виде строки

Рассматривается  алгоритм нахождения общего решения диофантового уравнения с многими неизвестными. 

В материале Решение системы из двух однородных диофантовых уравнений мы упоминали о том, что для решения нам понадобилось общее решение диофантового уравнения.

Теперь мы рассмотрим как мы его получаем.

На текущий момент в обществе широко распространен метод, описанный на  сайте кафедры теории чисел мехмата МГУ.

"для уравнения a_1*x_1+… + a_n * x_n = b строим матрицу из n+1 строк и n столбцов. Первая строка — коэффициенты при неизвестных в уравнении, оставшаяся часть — единичная матрица. Приводим матрицу к такому виду, что вся элементы первой строки нулевые за исключением первого, который равен НОД. преобразованиями столбцов: умножение столбца на -1, прибавление к столбцу любого другого, умноженного на целое число, умножение столбца на -1. Тогда элементы первой строки будут результатом подстановки соответствующих столбцов в выражение. А ответ — первый столбец, домноженный на b/НОД плюс остальные столбцы, домноженные на любые целые числа." (с) https://habr.com/ru/post/330632/

 
Не умаляя достоинства и уровня знаний людей, кто это все придумал, я посчитал что для такой простой задачи, должно быть не менее простое решение.
 
Мой вариант решения  нахождения общего решения произвольного однородного диофантового уравнения.
 
Для этого мне понадобится  только знание как решать уравнение с двумя неизвестными, и это знание у нас есть в виде двух формул.
 
\(\begin{cases}x_k=ca^{\phi(b)-1}+bk,\\y_k=c\frac{1-a^{\phi(b)}}{b}-ak,\end{cases}\)
 
где \(\phi()\)- функция Эйлера
 
Решение будем рассматривать сразу на примере, это нагляднее.
 
\(-5x_1+15x_2+72x_3-90x_4+120x_5=-13\)
 
Приведем это уравнение к виду \(Ax+By=C\)
где \(A=НОД(-5,15,72,-90)=1\),  \(B=120\), а \(C=-13\)
 
\(x+120y=-13\)
 
Корни его имеют вид
 
 \(x=107\\y=-1\)
 
Тогда мы можем утверждать что \(-5x_1+15x_2+72x_3-90x_4=107\)
а \(x_5=y=-1\)
 
Повторим то, что мы делали только что
 
\(A=НОД(-5,15,72)=1\),  \(B=-90\), а \(C=107\)
 
 
Решаем
\(x-90y=107\)
 
 Корни его имеют вид
 
 \(x=17\\y=-1\)
 
\(x_4=y=-1\)
 
Продолжаем
\(-5x_1+15x_2+72x_3=17\)
 
\(A=НОД(-5,15)=5\),  \(B=72\), а \(C=17\)

Заметили что НОД равен 5?

 
 Решаем
\(5x+72y=17\)
 
 Корни его имеют вид
 
 \(x=61\\y=-4\)
\(x_3=y=-4\)
 
И остался последний ход 
Так как на предыдущем этапе мы уже выделили/вынесли НОД
то последнее уравнение имеет вид \(-x+3y=61\)
И его корни
 \(x=2\\y=21\)
а следовательно
 
\(x_2=y=21\)
\(x_1=y=2\)
 
Теперь абсолютно точно можно сказать что мы нашли частное решение исходного уравнения и оно имеет вид
\((x_1,x_2,x_3,x_4,x_5)=(2, 21, -4, -1, -1)\)
 
проверим?
\(-5*2+15*21+72*(-4)-90*(-1)+120*(-1)=-10+315-288+90-120=\\305-288-30=275-288=-13\)
 
Что и требовалось доказать.
Теперь приступаем ко второму этапу.
Рассуждаем:
- раз частное решение приводит к тому что:
\(-5x_1+15x_2+72x_3-90x_4+120x_5=0\)
 
то логично предположить что мы можем найти такое же решение  и для
\(-5y_1+15y_2+72y_3-90y_4=-120\)
 
Находим частные корни для этого уравнения \((y_1,y_2,y_3,y_4)=(0,16,-5,0)\)
Потом решаем уравнение
\(-5z_1+15z_2+72z_3=90\)
Находим частные корни для этого уравнения \((z_1,z_2,z_3)=(0,6,0)\)
В конечном итоге у нас будут следующие частные решения
 
\((2, 21, -4, -1, -1)\)
\((0,16,-5,0)\)
\((0,6,0)\)
\((0,-24,5)\)
\((15,5)\)
Построим матрицу
 
\(\begin{pmatrix}15&0&0&0&2\\5&-24&6&16&21\\0&5&0&-5&-4\\0&0&1&0&-1\\0&0&0&1&-1\\\end{pmatrix}\)
 
Это и будет являться общим решением
Проверяется достаточно легко умножением вектора значений исходного уравнения на эту матрицу
Результатом получим вектор где все нули кроме последнего значения и оно совпадает с свободным членом уравнения
 
\(\begin{pmatrix}-5&15&72&-90&120\\\end{pmatrix}*\begin{pmatrix}15&0&0&0&2\\5&-24&6&16&21\\0&5&0&-5&-4\\0&0&1&0&-1\\0&0&0&1&-1\\\end{pmatrix}=\begin{pmatrix}0&0&0&0&-13\\\end{pmatrix}\)
 
Это решение легко алгоритмируется и не приводит к ошибкам.  Как видите нет необходимости вычислять какие либо матрицы.
Поиск по сайту