Уравнения в целых числах: методы и задачи

Решение

Выделим полный квадрат: $y^2 + 2y + 13 = (y + 1)^2 + 12$. Перенесём квадрат влево и разложим разность квадратов:

Обозначим $u = x - y - 1$ и $v = x + y + 1$. Их сумма $u + v = 2x$ чётна, значит, $u$ и $v$ одной чётности. Оба нечётными они быть не могут — тогда произведение было бы нечётным, а 12 чётно. Значит, оба чётные. Разложений 12 в произведение двух чётных множителей четыре: $2 \cdot 6$, $6 \cdot 2$, $(-2) \cdot (-6)$, $(-6) \cdot (-2)$. Отрицательные множители забывают чаще всего — из-за них теряется половина ответа.

Из $x = \dfrac{u + v}{2}$ и $y = \dfrac{v - u}{2} - 1$ получаем:

• $u = 2, v = 6$: $x = 4$, $y = 1$;
• $u = 6, v = 2$: $x = 4$, $y = -3$;
• $u = -2, v = -6$: $x = -4$, $y = -3$;
• $u = -6, v = -2$: $x = -4$, $y = 1$.

Проверка для $(4, 1)$: $16 = 1 + 2 + 13$. Остальные пары проверяются так же.

Источник задачи: 46-я Московская математическая олимпиада, 1983 год, 7 класс, задача 1 — условие и решение — problems.ru, архив задач МЦНМО

Решение

Пусть покупатель отдаёт $y$ монет по 27 тугриков, а получает сдачей $x$ монет по 16. Нужно, чтобы $27y - 16x = 1$ — это линейное уравнение в целых числах. Оно разрешимо, потому что $\text{НОД}(16, 27) = 1$, а нужные коэффициенты находит алгоритм Евклида. Делим с остатком, пока остаток не станет равен 1:

Теперь идём обратно и выражаем 1 через 16 и 27, подставляя остатки:

Значит, можно отдать три монеты по 27 тугриков (81 тугрик) и получить сдачей пять монет по 16 (80 тугриков).

Это не единственный способ. Все решения уравнения $27y - 16x = 1$ имеют вид $y = 3 + 16t$, $x = 5 + 27t$, где $t$ — любое целое число. Например, при $t = -1$ получится $y = -13$, $x = -22$: покупатель отдаёт 22 монеты по 16 (352 тугрика) и получает 13 монет по 27 (351 тугрик).

Источник задачи: Окружная олимпиада по математике (Москва), 2014 год, 7 класс, задача 7.1 — условие, решение и замечание о всех решениях — problems.ru, архив задач МЦНМО

Решение

Сначала разберёмся, какими бывают $n$. При отрицательном $n$ число $2^n$ дробное, тогда и $2^n + 7$ не целое, а $x^2$ — целое. Значит, $n \ge 0$.

При $n = 0$ получаем $x^2 = 8$ — целого решения нет. При $n = 1$ получаем $x^2 = 9$, откуда $x = \pm 3$.

Остался случай $n \ge 2$. Тогда $2^n$ делится на 4, и левая часть даёт остаток 3 при делении на 4. А квадрат целого числа даёт при делении на 4 только остатки 0 или 1: $(2k)^2 = 4k^2$ и $(2k + 1)^2 = 4(k^2 + k) + 1$. Остаток 3 недостижим, решений нет.

Разбор через остатки приведён в сборнике P. J. Taylor «International Mathematics Tournament of the Towns 1984–1989» (1992, с. 24, решение A. Liu). В архиве МЦНМО дан другой ход: $(x - 3)(x + 3) = 2(2^{n-1} - 1)$, и множители слева одной чётности. Оба пути занимают несколько строк. Остатки здесь удобнее: они отсекают все $n \ge 2$ одним доводом.

Источник задачи: 6-й Турнир городов, 1984/85 учебный год, осенний тур, подготовительный вариант, 7–8 класс, задача 3 — условие и решение — problems.ru, архив задач МЦНМО

Решение

Обозначим $S = a + b + c$. Все коэффициенты лежат между 28 и 31, поэтому

Из правого неравенства: $31S \ge 365$, а $31 \cdot 11 = 341 < 365$, значит, $S \ge 12$. Из левого: $28S \le 365$, а $28 \cdot 14 = 392 > 365$, значит, $S \le 13$.

Осталось исключить $S = 13$. Перепишем уравнение как $28S + 2b + 3c = 365$. При $S = 13$ это даёт $364 + 2b + 3c = 365$, то есть $2b + 3c = 1$. Но $b$ и $c$ неотрицательные: если хотя бы одно из них не меньше 1, левая часть не меньше 2, а если оба равны нулю, она равна 0. Значит, $S = 12$.

Смысл задачи виден из чисел: в году один месяц из 28 дней, четыре по 30 и семь по 31, $28 + 4 \cdot 30 + 7 \cdot 31 = 365$. Кроме этой тройки $(1, 4, 7)$, подходят ещё $(0, 7, 5)$ и $(2, 1, 9)$ — и у всех сумма равна 12.

Источник задачи: 61-я Московская математическая олимпиада, 1998 год, 10 класс, задача 1 — условие и решение — problems.ru, архив задач МЦНМО

Решение

Будем считать уравнение квадратным относительно $x$:

Целый корень у него может быть только при неотрицательном дискриминанте:

Условие $D \ge 0$ означает $3(y - 1)^2 \le 4$, то есть $(y - 1)^2 \le 1$. Значит, $y$ равно 0, 1 или 2 — бесконечная задача свелась к трём случаям.

• $y = 0$: $x^2 - x = 0$, $x = 0$ или $x = 1$.
• $y = 1$: $x^2 - 2x = 0$, $x = 0$ или $x = 2$.
• $y = 2$: $x^2 - 3x + 2 = 0$, $x = 1$ или $x = 2$.

Уравнение симметрично: замена $x$ на $y$ его не меняет. Поэтому вместе с каждой парой решением будет и переставленная, и в списке это видно.

В архиве приведено и второе решение. Правая часть равна $\tfrac{1}{4}(x+y)^2 + \tfrac{3}{4}(x-y)^2$, поэтому $x + y \ge 0$. Затем из неравенства $xy \le \tfrac{1}{4}(x + y)^2$ получается оценка $x + y \le 4$, после чего остаётся перебрать пять значений суммы.

Источник задачи: 7-я Московская математическая олимпиада, 1941 год, 9–10 класс, второй тур, задача 4 — условие и два решения — problems.ru, архив задач МЦНМО