Калькулятор линейных диофантовых уравнений
Решает линейное диофантово уравнение ax + by = c в целых числах. Введите коэффициенты a, b и c, чтобы проверить существование решений, получить одно частное решение и всю серию x = x₀ + (b/g)t, y = y₀ − (a/g)t.
Решение уравнения ax + by = c в целых числах
Формула линейного диофантова уравнения
Где:
- \(a\), \(b\) — целые коэффициенты при \(x\) и \(y\)
- \(c\) — целое число в правой части
- \(g = \gcd(a, b)\) — наибольший общий делитель коэффициентов
- \((x_0, y_0)\) — одно частное решение, которое находится из тождества Безу \(g = s\,a + t\,b\) умножением на \(c/g\)
- \(t\) — произвольный целочисленный параметр, порождающий все решения
Целочисленные решения существуют тогда и только тогда, когда \(\gcd(a,b)\) делит \(c\). Если это условие выполнено, решений бесконечно много: отправляясь от одного решения \((x_0, y_0)\), любое другое получается, если прибавить к \(x\) число \(b/g\) и вычесть из \(y\) число \(a/g\) одно и то же количество раз \(t\).
Линейное диофантово уравнение — пример вычисления
Пример: решим \(12x + 18y = 30\) в целых числах (значения по умолчанию в калькуляторе).
\[ \gcd(12, 18): \quad 18 = 1 \cdot 12 + 6, \quad 12 = 2 \cdot 6 + 0 \implies \gcd(12, 18) = 6 \]
\[ 6 \mid 30 \implies \text{решения существуют} \]
\[ \text{Безу: } 6 = (-1) \cdot 12 + 1 \cdot 18, \qquad \frac{c}{g} = \frac{30}{6} = 5 \]
\[ x_0 = -1 \cdot 5 = -5, \qquad y_0 = 1 \cdot 5 = 5 \]
\[ 12 \cdot (-5) + 18 \cdot 5 = -60 + 90 = 30 \;\checkmark \]
Сдвинув \(x_0\) в диапазон \(0 \le x < |b/g| = 3\), получаем равносильное частное решение \((1, 1)\), поскольку \(12 \cdot 1 + 18 \cdot 1 = 30\).
Результат: все целочисленные решения имеют вид \(x = 1 + 3t\), \(y = 1 - 2t\) при любом целом \(t\); например \((1, 1)\), \((4, -1)\), \((-2, 3)\).
Как пользоваться калькулятором
- Введите целочисленный коэффициент при \(x\) в поле Коэффициент при x (a).
- Введите целочисленный коэффициент при \(y\) в поле Коэффициент при y (b).
- Введите правую часть в поле Правая часть (c).
- Изучите блоки результата: Существуют ли решения в целых числах? показывает, делит ли \(\gcd(a,b)\) число \(c\); Одно решение (x₀, y₀) выдаёт проверенное частное решение; Общее решение в целых числах содержит полную серию решений с параметром \(t\); Шаги решения показывают алгоритм Евклида, коэффициенты Безу и ход рассуждений.
Все три вводимых числа должны быть целыми (положительными, отрицательными или нулём). Если ввести нецелое значение, калькулятор попросит целое число — диофантовы уравнения по определению решаются только в целых числах.
Что такое линейное диофантово уравнение?
Диофантово уравнение — это уравнение, решения которого требуется найти в целых числах. Линейное диофантово уравнение \(ax + by = c\) — простейший его вид: нужно найти все пары целых чисел \((x, y)\), точно ему удовлетворяющие, без дробей и десятичных чисел. Такие уравнения естественно возникают там, где величины неделимы: монеты фиксированных номиналов, коробки со штучным товаром, люди или плитки.
Ключевой факт — условие разрешимости: значение \(ax + by\) всегда кратно \(\gcd(a, b)\), значит, и \(c\) обязано быть кратным \(\gcd(a, b)\). Например, \(6x + 10y\) всегда чётно, поэтому у уравнения \(6x + 10y = 7\) нет целочисленных решений, сколько бы вы их ни искали. Если условие выполнено, тождество Безу гарантирует хотя бы одно решение, и его эффективно находит расширенный алгоритм Евклида.
Как толковать результат: если решения есть, их бесконечно много — они располагаются вдоль арифметической прогрессии. Общее решение \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\) перечисляет их все: каждый шаг параметра \(t\) увеличивает \(x\) на \(b/g\) и уменьшает \(y\) на \(a/g\), а сумма \(ax + by\) при этом не меняется. Если нужны решения из определённого диапазона (например, неотрицательные), подставьте несколько значений \(t\) и отберите подходящие.
Допущения, ограничения и советы
- Только целые числа. Коэффициенты должны быть целыми; над рациональными или действительными числами уравнение не решается. Над действительными числами \(ax + by = c\) всегда имеет решения, когда \(a\) или \(b\) не равно нулю, — именно ограничение целочисленностью делает задачу интересной.
- Ограничения на размер. Вычисления ведутся в обычной арифметике, поэтому держите коэффициенты в безопасном целочисленном диапазоне (примерно до 15 цифр), чтобы избежать проблем с точностью.
- Вырожденные случаи учтены. Если \(a = b = 0\), уравнение либо выполняется всегда (\(c = 0\), подходит любая пара), либо не выполняется никогда. Если равен нулю ровно один коэффициент, уравнение содержит одну переменную, и калькулятор решает его напрямую.
- Подойдёт любое частное решение. Пара \((x_0, y_0)\) не единственна — калькулятор приводит её к компактному виду с \(0 \le x_0 < |b/g|\), но любой выбор порождает через параметр \(t\) одно и то же полное множество решений.
- Проверка ответа. Всегда проверяйте подстановкой: вычислите \(a x_0 + b y_0\) и убедитесь, что получится \(c\). Калькулятор выполняет эту проверку за вас и показывает её в результате.
Если в задаче не одно уравнение, а два одновременно — система вида \(ax + by = c\), \(dx + ey = f\) — она решается методом elimination, а не через делимость на НОД. Диофантов подход лежит и в основе тем вроде прямой пропорциональности, где две целочисленные величины растут в фиксированной пропорции, а также является классическим инструментом олимпиадных задач и теории чисел.
Часто задаваемые вопросы
Как решить линейное диофантово уравнение вручную?
Сначала найдите \(g = \gcd(a, b)\) алгоритмом Евклида. Если \(g\) не делит \(c\), целочисленных решений нет. В противном случае примените расширенный алгоритм Евклида и найдите коэффициенты Безу, для которых \(g = sa + tb\), умножьте их на \(c/g\) и получите \(x_0 = s \cdot c/g\) и \(y_0 = t \cdot c/g\), после чего запишите все решения в виде \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\).
Можно ли использовать отрицательные коэффициенты или отрицательную правую часть?
Да, все три вводимых числа могут быть отрицательными или нулём — отвергаются только дроби и десятичные числа. НОД всегда берётся от модулей чисел, поэтому положителен. Формулы общего решения без изменений работают при отрицательных \(a\), \(b\) или \(c\); меняются лишь знаки шагов \(b/g\) и \(a/g\) в формулах с параметром.
Как проще всего понять, что решений нет?
Проверьте делимость на НОД: решения существуют тогда и только тогда, когда \(\gcd(a,b)\) делит \(c\). Быстрая проверка на чётность вскрывает многие учебные случаи: если \(a\) и \(b\) оба чётные, левая часть всегда чётна, и при нечётном \(c\) уравнение неразрешимо. Точно так же \(6x + 10y\) всегда чётно и всегда кратно только числам, делящимся на \(\gcd(6,10)=2\).
Как найти только неотрицательные или положительные решения?
Семейство с параметром \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\) даёт линейные условия на \(t\). Решите два неравенства \(x \ge 0\) и \(y \ge 0\) относительно \(t\), возьмите пересечение (это конечный отрезок целых чисел) и переберите каждое значение. Если полученный диапазон \(t\) пуст, решений с обеими неотрицательными переменными не существует.
Почему калькулятор выдаёт другое частное решение, чем в моём учебнике?
Частное решение никогда не единственно: если подходит \((x_0, y_0)\), то подходит и \((x_0 + b/g,\; y_0 - a/g)\). Оба ответа верны, поскольку через параметр \(t\) они порождают одно и то же полное множество решений. Этот калькулятор сдвигает \(x_0\) в компактный диапазон \(0 \le x_0 < |b/g|\), чего в учебниках может не быть. Всегда проверяйте ответ подстановкой в \(ax + by\).
Что будет, если a или b равно нулю?
Уравнение превращается в уравнение с одной переменной. Если \(b = 0\), нужно, чтобы \(a \mid c\); тогда \(x = c/a\) фиксировано, а \(y\) может быть любым целым — и симметрично при \(a = 0\). Если оба коэффициента нулевые, уравнение либо выполняется всегда (\(c = 0\), подходит любая пара), либо не выполняется никогда. Калькулятор напрямую обрабатывает все эти вырожденные случаи.
Чем это отличается от решения обычного линейного уравнения?
Над действительными числами уравнение \(ax + by = c\) с ненулевым коэффициентом всегда имеет решения — целую прямую. Диофантова версия требует только целочисленных пар, из-за чего уравнение может стать неразрешимым (когда \(\gcd(a,b) \nmid c\)) или дать вместо континуума дискретный, равномерно распределённый набор решений на этой прямой. Шаг между соседними решениями равен в точности \((b/g, -a/g)\).