Диофантово уравнение

Материал из Algocode wiki
Версия от 21:48, 29 октября 2020; KiKoS (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Диофантовым уравнением называется уравнение от двух целочисленных переменных $x, y$ вида $$ax + by = c$$

Такое уравнение задает прямую для вещественных чисел, но в случае натуральных чисел задаваемое множество не такое понятное.

Например, если $c \not\equiv 0 \pmod{gcd(a, b)}$, то решений точно нет, ведь левая часть делится на НОД, а правая --- нет.

Оказывается, в остальных случаях решение существует. Достаточно перейти к уравнению $a'x + b'y = c'$, где $a' = \frac{a}{gcd(a, b)}$ и $gcd(a', b') = 1$, а затем воспрользоваться расширенным алгоритмом Евклида для решения уравнения $a'x + b'y = 1$. Полученные решения необходимо будет умножить на $c$.

Чтобы получить все решения, достаточно будет делать переход $(x, y) \to (x + b' \cdot k, y - a' \cdot k), k \in \mathbb{Z}$


Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s