Русский
Русский
English
Авторизация
Ip-адрес
Восстановление пароля
Регистрация
Статистика
Реклама

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

В своей предыдущей статье упоминалось об общем решении диофантового уравнения.
На сегодня существует несколько алгоритмов нахождения общего решения.
Один из них размещен на сайте кафедры теории чисел мехмата МГУ.

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

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

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


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

Спасибо за внимание и уделённое время.
Источник: habr.com
К списку статей
admin
Опубликовано: 06.10.2020 14:22:26
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Программирование

Математика

Диофантовое

Уравнение

Общее решение

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru