DimsVs 6 окт 2020 в 14:15

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

2 мин

Математика*Программирование*

Технотекст 2020

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

На сегодня существует несколько алгоритмов нахождения общего решения.

Один из них размещен на сайте кафедры теории чисел мехмата МГУ.

В этой статье я расскажу, как бы я решал поставленную задачу.

Если для кого то нижеописанный алгоритм известен и банален, просьба отнестись к автору снисходительнее.

Для решения нам понадобится только явная формула решения диофантового уравнения с двумя переменными.

$\begin{cases}x_k=ca^{\phi(b)-1}+bk,\\y_k=c\frac{1-a^{\phi(b)}}{b}-ak,\end{cases}\\k\in\mathbb{R}$

где

$\phi()$

— функция Эйлера
Решение состоит из двух этапов.

1 этап. Частные решения
Разделим исходное диофантовое уравнение

$display$

таким образом

$display$

где

$A=GCD(a_1,a_2,....,a_{n-1})$

$display$

GCD — НОД чисел

Решая это уравнение, получаем что

$display$

равен какому то числу и это число является правой частью выражения

$\cfrac{a_1x_1+a_2x_2+a_3x_3+....+a_{n-1}x_{n-1}}{GCD(a_1,a_2,....,a_{n-1})}=y_n$

Решим это новое уравнение получим

$y_{n-1}$

В конечном итоге мы получим цепочку частных решений исходного диофантового уравнения.
Давайте рассмотрим сразу пример:

$display$

$\begin{cases}y_5=-152-91k_5,\\x_5=-5-3k_5,\end{cases}$

$\cfrac{21}{GCD(21,27,81,720)}x_1-\cfrac{27}{GCD(21,27,81,720)}x_2+\\+\cfrac{81}{GCD(21,27,81,720)}x_3+\cfrac{720}{GCD(21,27,81,720)}x_4=-152$

$display$

$\begin{cases}y_4=88+240k_4,\\x_4=-1-1k_4,\end{cases}$

$display$

$\begin{cases}y_3=7+27k_3,\\x_3=3-1k_3,\end{cases}$

И осталось последнее уравнение

$display$

Так как оно последнее в наших вычислениях, то два корня и будут являться

$display$

$\begin{cases}x_1=1-9k_2,\\x_2=0-7k_2,\end{cases}$

Мы получили цепочку частных решений заданного диофантового уравнения

$display$

Проверим?

$21\cdot1-27\cdot0+81\cdot3+720\cdot(-1)-\\-91\cdot(-5)=21+243-720+455=-1$

Совпадает с правой частью исходного уравнения?
Да!
Следовательно наши расчеты верны. Под это дело был сделан калькулятор Частное решение диофантового уравнения с несколькими неизвестными.

Теперь приступим ко второму этапу.

2 этап. Общая матрица

Когда я писал что у нас есть частное решение

$display$

я умышленно не писал вот так

$(x_1,x_2,x_3,x_4,x_5)=\\=(1-9k_2,0-7k_2,3-1k_3,-1-1k_4,-5-3k_5)$

так как приняв k за ноль мы и получим то что искали.

Но для понимания нам полная форма понадобится.

Подставив в исходное уравнение полную форму частных решений, мы увидим следующее

$21\cdot(1-9k_2)-27\cdot(0-7k_2)+81\cdot(3-1k_3)+\\+720\cdot(-1-1k_4)-91\cdot(-5-3k_5)=-1$

где

$display$

— какое то целое число.

После преобразований мы получим что в конечном итоге наше уравнение можем записать как

$21\cdot{m_1}-27\cdot{m_2}+81\cdot{m_3}+720\cdot{m_4}-91{m_5}=0$

или

$21\cdot{m_1}-27\cdot{m_2}+81\cdot{m_3}+720\cdot{m_4}=91{m_5}$

Ищем частное решение если например

$display$

Почему именно 3?

Потому что

$display$

Не утомляя Вас, дадим частные решения

$display$

ну и

$display$

Дальше идем как по накатанной...

Решаем уравнение

$7\cdotp_1-9\cdotp_2+27\cdotp_3=-720\cdotp_4$

частные решения

$display$

…
…
В конечном итоге мы получили следующие частные решения

$display$

Построим из них матрицу

$\begin{matrix}-27&0&0&4&1\\ -21&9&-1 &2 &0 \\0 &3 &-27 &3 &3 \\0 &0 &3 &0 &-1 \\0 &0 &0 &3 &-5\end{matrix}$

И эта матрица и является общим решением исходного диофантового уравнения
Проверить достаточно легко воспользовавшись калькулятором умножения вектора на матрицу

$\begin{pmatrix}21&-27&81&720&-91\\\end{pmatrix}\cdot\begin{pmatrix}-27&0&0&4&1\\-21&9&-1&2&0\\0&3&-27&3&3\\0&0&3&0&-1\\0&0&0&3&-5\\\end{pmatrix}=\\=\begin{pmatrix}0&0&0&0&-1\\\end{pmatrix}$

По итогу был создан калькулятор Общее решение линейного диофантового неоднородного уравнения которым могут воспользоваться все желающие.

Еще один пример

$display$

$\begin{pmatrix}x_4\\x_3\\x_2\\x_1\end{pmatrix}=\\=\begin{pmatrix}8&1&5&5\\-5&-1&-3&-3\\0&1&-1&0\\0&0&1&8\\\end{pmatrix}\cdot\begin{pmatrix}k_4\\k_3\\k_2\\k_1\end{pmatrix}$

Проверка

$\begin{pmatrix}5&8&3&2\\\end{pmatrix}\cdot\begin{pmatrix}8&1&5&5\\-5&-1&-3&-3\\0&1&-1&0\\0&0&1&8\\\end{pmatrix}=\\=\begin{pmatrix}0&0&0&17\\\end{pmatrix}$

Надеюсь, из этой статьи Вы узнали что то новое.

Спасибо за внимание и уделённое время.

Теги:

Хабы:

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

Публикации

Истории

Ближайшие события