Диофантово уравнение: различия между версиями
KiKoS (обсуждение | вклад) (Новая страница: «Диофантовым уравнением называется уравнение от двух целочисленных переменных $x, y$ вида...») |
KiKoS (обсуждение | вклад) м |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 4: | Строка 4: | ||
Такое уравнение задает прямую для вещественных чисел, но в случае натуральных чисел задаваемое множество не такое понятное. | Такое уравнение задает прямую для вещественных чисел, но в случае натуральных чисел задаваемое множество не такое понятное. | ||
| − | Например, если $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$. | Оказывается, в остальных случаях решение существует. Достаточно перейти к уравнению $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}$ |
| − | {{Автор|Константин Амеличев| | + | |
| + | [[Категория: Конспекты]] | ||
| + | {{Автор|Константин Амеличев|kik0s}} | ||
Текущая версия на 18:48, 29 октября 2020
Диофантовым уравнением называется уравнение от двух целочисленных переменных $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