Задача
Пусть 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.
Решение
а) Из задачи 160489 следует, что уравнение ax + by = c (*)
имеет решение (x0, y0) в целых числах. Тогда все решения уравнения (*) имеют вид (x0 + kb, y0 – ka) (см. задачу 160514). "Расстояние" между соседними числами вида 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, и мы нашли решение уравнения в неотрицательных целых числах.
Второй способ. См. решение задачи 173729.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь