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

 

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

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

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

\(\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. Находим общее решения первого уравнения из заданной системы. Например пусть будет такое

\(8 14 20 -19 -30 -44 -1 1 0\)

\(\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\)

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

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

 

 

Поиск по сайту