Исходное диофантовое уравнение |
|
Общее решение исходного уравнения |
|
Решение в виде строки |
|
Рассматривается алгоритм нахождения общего решения диофантового уравнения с многими неизвестными.
В материале Решение системы из двух однородных диофантовых уравнений мы упоминали о том, что для решения нам понадобилось общее решение диофантового уравнения.
Теперь мы рассмотрим как мы его получаем.
На текущий момент в обществе широко распространен метод, описанный на сайте кафедры теории чисел мехмата МГУ.
"для уравнения 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}\)
Это решение легко алгоритмируется и не приводит к ошибкам. Как видите нет необходимости вычислять какие либо матрицы.