|
|
 |
Условие
Пусть a и b – натуральные взаимно простые числа. Рассмотрим точки плоскости с целыми координатами (x, y), лежащие в полосе 0 ≤ x ≤ b – 1. Каждой такой точке припишем целое число N(x, y) = ax + by.
а) Докажите, что для каждого натурального c существует ровно одна точка (x, y) (0 ≤ x ≤ b – 1), для которой N(x, y) = c.
б) Теорема Сильвестра. Докажите, что наибольшее c, для которого уравнение ax + by = c не имеет решений в целых неотрицательных числах, имеет вид
c = ab – a – b.
Решение
а) Из задачи 60489 следует, что уравнение ax + by = c (*)
имеет решение (x0, y0) в целых числах. Тогда все решения уравнения (*) имеют вид (x0 + kb, y0 – ka) (см. задачу 60514). "Расстояние" между соседними числами вида x0 + kb равно b, поэтому ровно одно из них попадает в заданный отрезок, состоящий из b целых чисел.
б) Первый способ. Уравнение ax + by = ab – a – b (**)
имеет очевидное решение (x0, y0) = (b – 1, –1). Поэтому все его решения имеют вид (x, y) = (b – 1 + kb, –1 – ka). Но при отрицательном k x < 0, а при неотрицательном y < 0. Значит, уравнение (**) не имеет решений в неотрицательных целых числах.
Пусть c > ab – a – b. Согласно а) уравнение (*) имеет решение (x0, y0), где 0 ≤ x0 ≤ b – 1. При этом by0 = c – ax0 ≥ c – a(b – 1) > –b. Значит, y0 > –1, то есть y0 ≥ 0, и мы нашли решение уравнения в неотрицательных целых числах.
Второй способ. См. решение задачи 73729.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 3 |
| Название | Алгоритм Евклида и основная теорема арифметики |
| Тема | Алгебра и арифметика |
| параграф | |
| Номер | 2 |
| Название | Алгоритм Евклида |
| Тема | Алгоритм Евклида |
| задача | |
| Номер | 03.073 |
