В своей предыдущей статье упоминалось об общем решении диофантового уравнения.
На сегодня существует несколько алгоритмов нахождения общего решения.
Один из них размещен на сайте кафедры теории чисел мехмата МГУ.
В этой статье я расскажу, как бы я решал поставленную задачу.
Если для кого то нижеописанный алгоритм известен и банален, просьба отнестись к автору снисходительнее.
Для решения нам понадобится только явная формула решения диофантового уравнения с двумя переменными.
где
— функция Эйлера
Решение состоит из двух этапов.
1 этап. Частные решения
Разделим исходное диофантовое уравнение
таким образом
где
GCD — НОД чисел
Решая это уравнение, получаем что
равен какому то числу и это число является правой частью выражения
Решим это новое уравнение получим
В конечном итоге мы получим цепочку частных решений исходного диофантового уравнения.
Давайте рассмотрим сразу пример:
И осталось последнее уравнение
Так как оно последнее в наших вычислениях, то два корня и будут являться
Мы получили цепочку частных решений заданного диофантового уравнения
Проверим?
Совпадает с правой частью исходного уравнения?
Да!
Следовательно наши расчеты верны. Под это дело был сделан калькулятор Частное решение диофантового уравнения с несколькими неизвестными.
Теперь приступим ко второму этапу.
2 этап. Общая матрица
Когда я писал что у нас есть частное решение
я умышленно не писал вот так
так как приняв k за ноль мы и получим то что искали.
Но для понимания нам полная форма понадобится.
Подставив в исходное уравнение полную форму частных решений, мы увидим следующее
где
— какое то целое число.
После преобразований мы получим что в конечном итоге наше уравнение можем записать как
или
Ищем частное решение если например
Почему именно 3?
Потому что
Не утомляя Вас, дадим частные решения
ну и
Дальше идем как по накатанной...
Решаем уравнение
частные решения
…
…
В конечном итоге мы получили следующие частные решения
Построим из них матрицу
И эта матрица и является общим решением исходного диофантового уравнения
Проверить достаточно легко воспользовавшись калькулятором умножения вектора на матрицу
По итогу был создан калькулятор Общее решение линейного диофантового неоднородного уравнения которым могут воспользоваться все желающие.
Еще один пример
Проверка
Надеюсь, из этой статьи Вы узнали что то новое.
Спасибо за внимание и уделённое время.
