| Система двух диофантовых уравнений |
|
|
| Матрица общего решения |
|
| Результат в виде строки |
|
| Проверка для первого уравнения |
![Проверка для первого уравнения]() |
| Проверка для второго уравнения |
![Проверка для второго уравнения]() |
Рассматривается оригинальный алгоритм решения двух произвольных однородных линейных уравнений в целых числах. Автоматический расчет матрицы решений.
Пусть Нам надо решить систему из двух диофантовых уравнений
\(\begin{alignedat}{2}2&a-11&b+13&c=1\\62&a+22&b-73&c=-31\end{alignedat}\)
Несомненно можно решать эту систему так как делают все.
- Умножив первое уравнение на 31 и вычтя из второго мы получим классическое диофантовое уравнение с двумя переменными.
- Решив которое можно найти все целочисленные значения системы
Схема рабочая, несмотря на множество ручных вычислений
Мне такой подход не нравится и для решения мы будем использовать другой метод.
Он красив и понятен даже для школьников, знающих про вектора и матрицы.
Частично использован алгоритм, описанный вот в этой статье ( стр 36,37)
Он доработан, приведен к матричным операциям и обобщен на любые значения.
Алгоритм и его работу мы будем изучать на примере.
Решаем следующую систему диофантовых уравнений
\(\begin{alignedat}{2}49&a+22&b-26&c=12\\70&a-31&b+9&c=9\end{alignedat}\)
Мы этот пример взяли по причине, что в интернете его решали и для него вывели общее решение. Так что есть с чем сравнивать.
1. Находим общее решения первого уравнения из заданной системы. Например пусть будет такое. Но мы можем воспользоваться и онлайн калькулятором общее решение линейного диофантового неоднородного уравнения ответ которого будет равноценен.
\(\begin{pmatrix}8&14&20\\-19&-30&-44\\-1&1&0\end{pmatrix}\)
\(\begin{alignedat}{3}a=8&m+14&p+20\\b=-19&m-30&p-44\\c=-&m+&p+0\end{alignedat}\)
Как проверим что это верное равенство? Да просто умножим вектор коэффициентов первого уравнения на полученную матрицу
\(\begin{pmatrix}49&22&-26\end{pmatrix}*\begin{pmatrix}8&14&20\\-19&-30&-44\\-1&1&0\end{pmatrix}=\begin{pmatrix}0&0&12\end{pmatrix}\)
Как видим ответ совпадает со свободным членом первого уравнения.
2. Теперь, раз мы нашли общее решение первого уравнения, давайте его подставим во второе.
То есть в уравнение \(70a-31b+9c=9\)подставим наши значения
\(\begin{cases}a=8m+14p+20\\b=-19m-30p-44\\c=-m+p+0\end{cases}\)
Можно руками подставлять и сокращать подобное, но в матричном исчислении мы лишь умножаем вектор {70,-31,9} на нашу матрицу.
\(\begin{pmatrix}70&-31&9\end{pmatrix}*\begin{pmatrix}8&14&20\\-19&-30&-44\\-1&1&0\end{pmatrix}=\begin{pmatrix}1140&1919&2764\end{pmatrix}\)
То есть мы получили уравнение
\(1140m+1919p+2764=0\)
Но, обратите внимание, что во втором уравнении свободный член равен не нулю, а девяти.
То есть мы переписываем
\(1140m+1919p+2764=9\)
Переносим свободные члены в правую часть и получаем классическое диофантовое уравнение, которое можем решать легко.
\(1140m+1919p=-2755\)
Общее решение такое
\(\begin{cases}m=6+(1919)k\\p=-5-(1140)k\end{cases}\)
3. А теперь делаем обратное преобразование.
То есть
вот в эту систему \(\begin{cases}a=8m+14p+20\\b=-19m-30p-44\\c=-m+p+0\end{cases}\)
мы вместо неизвестных подставляем найденные m и p.
В матричном исчислении это решается так:
Убираем из матрицы \(\begin{pmatrix}8&14&20\\-19&-30&-44\\-1&1&0\end{pmatrix}\)
последний столбец. Это свободные члены и они нам пока мешаются.
получили \(\begin{pmatrix}8&14\\-19&-30\\-1&1\end{pmatrix}\)
Умножаем эту матрицу на матрицу созданную из этих уравнений
\(\begin{cases}m=6+(1919)k\\p=-5-(1140)k\end{cases}\)
\(\begin{pmatrix}1919&6\\-1140&-5\end{pmatrix}\)
получаем
\(\begin{pmatrix}8&14\\-19&-30\\-1&1\end{pmatrix}*\begin{pmatrix}1919&6\\-1140&-5\end{pmatrix}=\begin{pmatrix}-608&-22\\-2261&36\\-3059&-11\end{pmatrix}\)
Последняя колонка это свободные члены, прибавим к ней ту колонку которую убирали в начале этого пункта
то есть к вектору {-22 36 -11} прибавляем {20 -44 0}
Получаем систему
\(\begin{pmatrix}-608&-2\\-2261&-8\\-3059&-11\end{pmatrix}\)
А следовательно общее решение системы двух диофантовых уравнений
приобретает вид
\(\begin{cases}a=-608k-2\\b=-2261k-8\\c=-3059k-11\end{cases}\)
Проверим, правильно ли посчитали
Для первого уравнения
\(\begin{pmatrix}49&22&-26\end{pmatrix}*\begin{pmatrix}-608&-2\\-2261&-8\\-3059&-11\end{pmatrix}=\begin{pmatrix}0&12\end{pmatrix}\)
Для второго
\(\begin{pmatrix}70&-31&9\end{pmatrix}*\begin{pmatrix}-608&-2\\-2261&-8\\-3059&-11\end{pmatrix}=\begin{pmatrix}0&9\end{pmatrix}\)
Как видим значения свободных членов совпадают с значениями в правой части уравнений, а следовательно мы получили общее решение.
Но радоваться рано, несмотря на то, что мы получили общее решение, мы получаем не все возможные значения.
Почему? Да потому что вектор {-608 -2261 -3059} имеет НОД =19
и фактически наше общее решение имеет вид
\(\begin{cases}a=-32(19k)-2\\b=-119(19k)-8\\c=-161(19k)-11\end{cases}\)
Так как числа в скобках должны быть целыми, то обозначим их t и наше, уже точно окончательное общее решение системы двух диофантовых уравнений имеет вид
\(\begin{cases}a=-32t-2\\b=-119t-8\\c=-161t-11\end{cases}\)
Еще несколько примеров, и небольшие ремарки к алгоритму.
\(\begin{cases}2a-11b+13c=1\\62a+22b-73c=-31\end{cases}\)
ответ
\(a=517k+748\\b=952k+1378\\c=726k+1051\)
еще пример
\(\begin{cases}-a+7b+c-53d+13e=-100\\2a+4b-16c-37d-32e=0\end{cases}\)
ответ
\(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\)
Как видите можно решать неограниченные по числу переменных диофантовые уравнения.
Теперь что калькулятор не может.
Очень сильно не любит уравнения с нулевыми коэффициентами. Особенно первое. Например, вот такую систему
калькулятор не решит.
\((3)*x_{1}+(0)*x_{2}+(-7)*x_{3}+(6)*x_{4}+(0)*x_{5}=17\\(4)*x_{1}+(3)*x_{2}+(0)*x_{3}+(6)*x_{4}+(-5)*x_{5}=19\)
Прибавим к первому уравнению, второе. Таким образом в первом уравнении исчезают все нулевые коэффициенты и калькулятор сможет решить эту систему. Ну как не решит? Решит, если прибегнем к уловке, и постараемся убрать все нулевые коэффициенты
\((7)*x_{1}+(3)*x_{2}+(-7)*x_{3}+(12)*x_{4}+(-5)*x_{5}=36\\(4)*x_{1}+(3)*x_{2}+(0)*x_{3}+(6)*x_{4}+(-5)*x_{5}=19\)
Проверка показывает что общее решение корректно.
Удачи в расчетах!!
