06.10.2020 11:15
DimsVs 4 1200 Источник

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


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


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


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


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


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


$\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 этап. Частные решения
Разделим исходное диофантовое уравнение


$a_1x_1+a_2x_2+a_3x_3+....+a_nx_n=b$


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


$Ay_n+Bx_n=b$


где

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



$B=a_n$


GCD — НОД чисел


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

$y_n$


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

$\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}$


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

$21x_1-27x_2+81x_3+720x_4-91x_5=-1$


$A=GCD(21,27,81,720)=3$


$B=-91$


$3y_5-91x_5=-1$


$\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$


$7x_1-9x_2+27x_3+240x_4=-152$


$A=GCD(7,9,27)=1$


$B=240$


$y_4+240x_4=-152$


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


$7x_1-9x_2+27x_3=88$


$A=GCD(7,9)=1$


$B=27$


$y_3+27x_3=88$


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


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


$7x_1-9x_2=7$


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

$x_1,x_2$



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


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


$(x_1,x_2,x_3,x_4,x_5)=(1,0,3,-1,-5)$


Проверим?


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


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


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


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


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

$(x_1,x_2,x_3,x_4,x_5)=(1,0,3,-1,-5)$


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

$(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$


где

$k_n$


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

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

$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}$


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

$m_5=3$


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


Потому что

$A=GCD(21,27,81,720)=3$


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

$(m_1,m_2,m_3,m_4)=(4,2,3,0)$


ну и

$m_5=3$



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


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

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


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

$(p_1,p_2,p_3)=(0,-1,-27)$



$p_4=3$


$p_5=0$


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


$(1,0,3,-1,-5)$


$(4,2,3,0,3)$


$(0,1,-27,3,0)$


$(0,9,3,0,0)$


$(-27,-21,0,0,0)$


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


$\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}$


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


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


$5x_1+8x_2+3x_3+2_x=17$


$\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}$


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


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