|
|
 |
Условие
Пусть натуральные числа $a$ и $b$ взаимно просты. Докажите, что для того, чтобы уравнение $ax + by = c$ имело ровно $n$ целых положительных решений, значение $c$ должно находиться в пределах $(n - 1) \cdot ab + a + b \leqslant c \leqslant (n + 1) \cdot ab.$
Решение
Пусть уравнение $ax + by = c$ имеет $n$ натуральных решений и $(x_0, y_0)$ – решение уравнения с наименьшим натуральным $x_0$. Тогда $(x_0+kb, y_0 - ka)$, $k = 1, 2, ..., n - 1$ – тоже натуральные решения.
Значит, $y_0 > a (n - 1)$, $c - ax_0 = by_0 > (n - 1) \cdot ab$. Кроме того, $c - ax_0$ делится на $b$, поэтому
$c - ax_0 \geqslant (n - 1) \cdot ab + b$, $c \geqslant (n-1) \cdot ab + ax_0 + b \geqslant (n - 1) \cdot ab + a + b$. Уравнение $ax + by = (n - 1) \cdot ab + a + b$ действительно имеет ровно $n$ натуральных решений: $(1 + kb, 1 + (n - k - 1) \cdot a)$, $k = 0, 1, ..., n - 1$.
Уравнение $ax + by = (n + 1) \cdot ab$ тоже имеет ровно $n$ натуральных решений: $(kb, (n + 1 - k) \cdot a)$, $k = 1, ..., n$.
При $c > (n + 1) \cdot ab$ натуральных решений уже больше. Действительно, согласно задаче 60525 уравнение имеет такое решение $(x_0, y_0)$, что $0 \leqslant x_0 < b$, $y_0 \geqslant 0$. При этом $$y_0 = \frac{c}{b} - \frac{a}{b} x_0 > (n+1) a - a = na \ge a.$$ Положим $x_1 = x_0$, $y_1 = y_0$ в случае, если $x_0>0$, и $x_1 = x_0+b = b$, $y_1 = y_0 - a$ иначе. Тогда $(x_1, y_1)$ – положительные целые числа, удовлетворяющие уравнению, причём $0 < x_1 \le b$. Но тогда помимо $x_1, y_1$ решения $(x_1 + kb, y_1 - ka)$, $k = 1, 2, ..., n$ также будут натуральными: $$y_1 - n \cdot a = \frac{c}{b} - \frac{a}{b} x_1 - n \cdot a > (n + 1) \cdot a - a - n \cdot a = 0.$$ Таким образом, при $c > (n+1) \cdot ab$ уравнение имеет по крайней мере $n+1$ решение в положительных целых числах.
Замечания
Далеко не при всех $c$ в указанных пределах натуральных решений ровно $n$ (см. ответ к задаче 60524).
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 3 |
| Название | Алгоритм Евклида и основная теорема арифметики |
| Тема | Алгебра и арифметика |
| параграф | |
| Номер | 2 |
| Название | Алгоритм Евклида |
| Тема | Алгоритм Евклида |
| задача | |
| Номер | 03.074 |
