Теория
Диофантово уравнение — уравнение вида \(ax + by = c\), у которого ищут решения в целых числах. Такие задачи возникают в быту: например, сколькими способами можно набрать покупку из ручек по 3 рубля и тетрадей по 5 рублей на заданную сумму.
Целое решение существует не всегда. Критерий такой: правая часть \(c\) должна делиться на наибольший общий делитель коэффициентов \(a\) и \(b\). Если условие выполнено, решений бесконечно много, и все они получаются из одного «частного» решения сдвигом по целочисленному параметру.
Важно: если НОД коэффициентов не делит правую часть, целых решений нет вовсе — дальше можно не искать.
Пример с решением
- Условие. Найти целые \(x\) и \(y\), для которых \(3x + 5y = 1\).
- Формула. Сначала частное решение: подберём \(x_0 = 2\), \(y_0 = -1\).
- Подстановка. Проверка: \(3 \times 2 + 5 \times (-1) = 6 - 5 = 1\) — подходит.
- Вычисление. Остальные решения — сдвиги частного: \(x = 2 + 5t\), \(y = -1 - 3t\), где \(t\) — любое целое число.
- Ответ. Калькулятор с полями «a» = 3, «b» = 5, «c» = 1 выдаст частное решение (2; −1) и общую формулу.
Главное
- Диофантово уравнение — линейное уравнение с целыми коэффициентами и целыми решениями.
- Условие разрешимости — правая часть делится на НОД коэффициентов.
- Все решения получаются из частного сдвигом по параметру \(t\).