Задачи с целочисленными неизвестными

Можно ли монетами по $2$ и $5$ рублей заплатить $12$ рублей? Пусть $x$ — число двухрублёвых монет, $y$ — пятирублёвых: $\ 2x + 5y = 12$.

Решений бесконечно много: $(1;\ 2)$, $(6;\ 0)$, $(-4;\ 4)$, … Отрицательное $x$ означает, что покупатель получил сдачу $|x|$ монетами по $2$ рубля.

Уравнения с несколькими неизвестными, решения которых ищут в целых числах, называют диофантовыми — по имени Диофанта (III в.).

Простейшее диофантово уравнение — первой степени: $\ ax + by = c$, $a$ и $b$ — целые, не равные нулю. При $c = 0$ есть решение $(0;\ 0)$.

Если $(x_0;\ y_0)$ — решение, то $ax_0 + by_0$ делится на $d = (a,\ b)$, поэтому и $c$ делится на $d$.

Если $c$ не делится на $\text{НОД}(a,\ b)$, решений нет. $\ 3x + 6y = 5$: $(3,\ 6) = 3$, а $5$ на $3$ не делится.

Если $c$ делится на $d$, делим уравнение на $d$ и получаем $a_1x + b_1y = c_1$ с $(a_1,\ b_1) = 1$.

Если $(a,\ b) = 1$ и $(x_0;\ y_0)$ — решение уравнения $ax + by = c$, то все его решения задаются этими формулами. $(x_0;\ y_0)$ — частное решение, формулы — общее решение.

Доказательство. Подстановка: $a(x_0 + bn) + b(y_0 - an) = ax_0 + by_0 = c$ — это решения. Пусть $(x_1;\ y_1)$ — любое решение. Вычитая, получаем $a(x_1 - x_0) = b(y_0 - y_1)$.

Левая часть делится на $a$, значит, $b(y_0 - y_1)$ делится на $a$, а $(a,\ b) = 1$ — по лемме $y_0 - y_1 = an$. Подставив, получим $x_1 - x_0 = bn$. Других решений нет.

1. $(3,\ 5) = 1$ — решения есть. Частное решение подбором: $x_0 = 1$, $y_0 = 2$ ($3 + 10 = 13$).
2. Общее решение: $x = 1 + 5n$, $\ y = 2 - 3n$, $n \in \mathbb{Z}$.
3. На прямой $3x + 5y = 13$ целые точки идут с шагом $5$ по $x$ и $-3$ по $y$.

Решения $3x + 5y = 13$ — целые точки прямой: от одной к следующей $x$ растёт на $b = 5$, $y$ убывает на $a = 3$. Между ними целых точек на прямой нет.

1. $31x + 21y = 1770$, $x$ и $y$ — натуральные. $21$ и $1770$ делятся на $3$, а $31$ — нет, поэтому $x = 3x_1$: $\ 31x_1 + 7y = 590$.
2. $x_1 = \dfrac{590 - 7y}{31} = 19 - \dfrac{7y - 1}{31}$. Наименьшее натуральное $y$, при котором $7y - 1$ делится на $31$, — это $y = 9$; тогда $x_1 = 17$, $x = 51$.
3. Общее решение: $x = 51 + 21n$, $\ y = 9 - 31n$. Натуральные значения: $n = 0, -1, -2$; при $n \le -3$ получаем $x < 0$.
4. Решения: $(51;\ 9)$, $(30;\ 40)$, $(9;\ 71)$.

1. а) Частное решение $x_0 = -10$, $y_0 = 2$: $-190 + 194 = 4$. $(19,\ 97) = 1$, общее решение $x = -10 + 97t$, $y = 2 - 19t$, $t \in \mathbb{Z}$.
2. б) Добавим $19 \cdot 97 = 1843$: $\ xy + 19x + 97y + 1843 = 1847$, $\ (x + 97)(y + 19) = 1847$. Число $1847$ простое, поэтому множители — $\pm1$ и $\pm1847$: $(x;\ y) = (-96;\ 1828),\ (1750;\ -18),\ (-98;\ -1866),\ (-1944;\ -20)$.
3. в) Умножим на $4$ и добавим $1843$: $\ 16xy - 76x - 388y + 1843 = 1843$, $\ (4x - 97)(4y - 19) = 1843 = 19 \cdot 97$.
4. $4x - 97 \equiv 3$, $4y - 19 \equiv 1 \pmod 4$, и $x, y \ge 1$: подходят $4x - 97 = 19$, $4y - 19 = 97$ ($x = y = 29$) и $4x - 97 = 1843$, $4y - 19 = 1$ ($x = 485$, $y = 5$). Отрицательные разложения дают $x = y = 0$ или $y < 0$.

Уравнение Пифагора $x^2 + y^2 = z^2$ в натуральных числах: каждое решение — стороны пифагорова треугольника, все стороны которого натуральные: $(3;\ 4;\ 5)$, $(5;\ 12;\ 13)$, $(8;\ 15;\ 17)$.

Великая теорема Ферма: уравнение $x^n + y^n = z^n$ при $n \ge 3$ не имеет решений в натуральных числах. Сформулирована П. Ферма более $300$ лет назад, доказана лишь в $1993$ г.

Общих методов нет. Основные приёмы: разложение на множители, выделение полных квадратов (оценка), остатки (сравнения по модулю).

1. Разложим: $(x - 2y)(x + 2y) = 5$. Множители — целые, а $5$ раскладывается на целые множители четырьмя способами.
2. $\begin{cases} x - 2y = 1\\ x + 2y = 5\end{cases}$, $\ \begin{cases} x - 2y = -1\\ x + 2y = -5\end{cases}$, $\ \begin{cases} x - 2y = 5\\ x + 2y = 1\end{cases}$, $\ \begin{cases} x - 2y = -5\\ x + 2y = -1\end{cases}$.
3. Сложив и вычтя уравнения каждой системы, найдём $(3;\ 1)$, $(-3;\ -1)$, $(3;\ -1)$, $(-3;\ 1)$.

1. Выделим полные квадраты: $(x - 5)^2 + (y + 1)^2 = 4$.
2. $x - 5$ и $y + 1$ — целые. Квадраты целых чисел, не большие $4$: $0, 1, 4$; сумма двух из них равна $4$ только как $4 + 0$ или $0 + 4$.
3. $x - 5 = \pm2$, $y + 1 = 0$ или $x - 5 = 0$, $y + 1 = \pm2$.

1. Пусть $a \ge b$. а) $ab = 25(a - b)$, $\ ab - 25a + 25b - 625 = -625$, $\ (a + 25)(25 - b) = 625$. Первый множитель больше $25$, второй — натуральный меньше $25$: $625 = 625 \cdot 1 = 125 \cdot 5$. Получаем $(600;\ 24)$, $(100;\ 20)$.
2. б) $ab = 25(a + b)$: $\ (a - 25)(b - 25) = 625$. Оба множителя положительны (если оба отрицательны, их произведение меньше $625$): $25 \cdot 25$, $125 \cdot 5$, $625 \cdot 1$ — пары $(50;\ 50)$, $(150;\ 30)$, $(650;\ 26)$.
3. в) $ab = \dfrac{25(a + b)}{2}$: $\ 4ab - 50a - 50b = 0$, $\ (2a - 25)(2b - 25) = 625$. Так же: $(25;\ 25)$, $(75;\ 15)$, $(325;\ 13)$.

1. При $n < 0$ число $3^n + 8$ не целое, а $x^2$ — целое: решений нет.
2. При $n = 0$: $x^2 = 9$, $x = \pm 3$.
3. При $n > 0$: $3^n + 8 \equiv 8 \equiv 2 \pmod 3$. Квадрат по модулю $3$ даёт только $0$ или $1$: $(3k)^2 = 9k^2$, $(3k \pm 1)^2 = 9k^2 \pm 6k + 1$. Решений нет.

1. $2^m = 3^n + 1$. Посмотрим на остатки по модулю $8$: $3^2 = 9 \equiv 1$, поэтому $3^{2k} \equiv 1$, $3^{2k-1} \equiv 3 \pmod 8$.
2. Значит, $3^n + 1 \equiv 2$ или $4 \pmod 8$, а при $m \ge 3$ число $2^m$ делится на $8$. Остаётся $m = 1$ или $m = 2$.
3. $m = 1$: $3^n = 1$, $n = 0$ — не натуральное. $m = 2$: $3^n = 3$, $n = 1$.

1. При $n \ge 5$ число $n!$ оканчивается нулём, $5n$ — на $0$ или $5$, поэтому левая часть оканчивается на $3$ или $8$. Квадраты на $3$ и $8$ не оканчиваются (последние цифры квадратов $0, 1, 4, 5, 6, 9$) — решений нет.
2. Перебор $n = 1, 2, 3, 4$: $\ 1 + 5 + 3 = 9 = 3^2$; $\ 2 + 10 + 3 = 15$; $\ 6 + 15 + 3 = 24$; $\ 24 + 20 + 3 = 47$ — квадрат только при $n = 1$.

• $ax + by = c$ разрешимо в целых числах $\iff$ $c$ делится на $\text{НОД}(a,\ b)$.
• При $(a,\ b) = 1$: $x = x_0 + bn$, $y = y_0 - an$; частное решение — подбором.
• В натуральных числах из общего решения выбираем $n$ по неравенствам $x > 0$, $y > 0$.
• Нелинейные: разложить на множители и перебрать делители числа справа; выделить полные квадраты и оценить.
• «Решений нет» — по остаткам: квадраты, степени, последние цифры.