SavePearlHarbor

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

—

от автора

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

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

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

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

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

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

$\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*1-27*0+81*3+720*(-1)-91*(-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*(1-9k_2)-27*(0-7k_2)+81*(3-1k_3)+720*(-1-1k_4)-91*(-5-3k_5)=-1$

где

$k_n$

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

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

$21*m_1-27*m_2+81*m_3+720*m_4-91m_5=0$

или

$21*m_1-27*m_2+81*m_3+720*m_4=91m_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*p_1-9*p_2+27*p_3=-720*p_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}*\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}*\begin{pmatrix}k_4\\k_3\\k_2\\k_1\end{pmatrix}$

Проверка

$\begin{pmatrix}5&8&3&2\\\end{pmatrix}*\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}$

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

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

ссылка на оригинал статьи https://habr.com/ru/post/521526/

Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *