|
|
 |
Условие
Пусть числа $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$. Но тогда $(x_0 + kb, y_0 - ka)$, $k = 1, 2, ..., n + 1$, – натуральные решения, поскольку $y_0 - (n + 1) \cdot a = c/b - a/b x_0 - (n + 1) \cdot a > (n + 1) \cdot a - (n + 1) \cdot a = 0.$
Замечания
Далеко не при всех $c$ в указанных пределах натуральных решений ровно $n$ (см. ответ к задаче 60524).
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 3 |
| Название | Алгоритм Евклида и основная теорема арифметики |
| Тема | Алгебра и арифметика |
| параграф | |
| Номер | 2 |
| Название | Алгоритм Евклида |
| Тема | Алгоритм Евклида |
| задача | |
| Номер | 03.074 |
