Пусть 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.

   Решение

Темы:    [ Уравнения в целых числах ] [ НОД и НОК. Взаимная простота ] [ Центральная симметрия помогает решить задачу ] [ Геометрические интерпретации в алгебре ]

Сложность: 4 Классы: 9,10,11

Прислать комментарий

Условие

Пусть 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     (*)
имеет решение  (x₀, y₀)  в целых числах. Тогда все решения уравнения (*) имеют вид   (x₀ + kb, y₀ – ka)  (см. задачу 60514). "Расстояние" между соседними числами вида  x₀ + kb  равно b, поэтому ровно одно из них попадает в заданный отрезок, состоящий из b целых чисел.

  б) Первый способ. Уравнение  ax + by = ab – a – b     (**)
имеет очевидное решение  (x₀, y₀) = (b – 1, –1).  Поэтому все его решения имеют вид  (x, y) = (b – 1 + kb, –1 – ka).   Но при отрицательном k   x < 0,  а при неотрицательном  y < 0.  Значит, уравнение (**) не имеет решений в неотрицательных целых числах.
  Пусть  c > ab – a – b.  Согласно а) уравнение (*) имеет решение  (x₀, y₀),  где  0 ≤ x₀ ≤ b – 1.  При этом  by₀ = c – ax₀ ≥ c – a(b – 1) > –b.  Значит,  y₀ > –1,  то есть  y₀ ≥ 0,  и мы нашли решение уравнения в неотрицательных целых числах.
 Второй способ. См. решение задачи 73729.

Источники и прецеденты использования