Задача 60489

Темы:    [ НОД и НОК. Взаимная простота ] [ Принцип Дирихле (прочее) ] [ Принцип крайнего (прочее) ] [ Геометрические интерпретации в алгебре ] [ Уравнения в целых числах ]

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

Условие

a, b, c – целые числа; a и b отличны от нуля.
Докажите, что уравнение  ax + by = c  имеет решения в целых числах тогда и только тогда, когда c делится на  d = НОД(a, b).

Решение

  Необходимость. Любое число вида  ax + by  делится на d.

  Достаточность. Достаточно проверить, что имеет решение уравнение  ax + by = d.  Кроме того, можно считать, что a и b положительны.

  Первый способ. См. задачу 60488 б.

  Второй способ. Рассмотрим наименьшее натуральное число m, являющееся линейной комбинацией чисел a и b (то есть представимое в виде  ax + by).  Разделим a на m с остатком:  a = qm + r.  Число  r = a – qm  также является линейной комбинацией чисел a и b, но оно меньше m. Значит,  r = 0,  то есть a кратно m. Аналогично b кратно m. Следовательно, и d делится на m, и поэтому является линейной комбинацией чисел a и b.

  Третий способ. Разделив на d, мы сведём задачу к случаю взаимно простых чисел a и b.
  Для каждого целого c рассмотрим на координатной плоскости прямую l_c, заданную уравнением  ax + by = c.  Все эти прямые параллельны.
  Построим параллелограмм P с вершинами  (0, 0),  (0, 1),  (b, 1 – a),  (b, – a),  две меньшие стороны которого равны 1, а большие лежат на прямых l₀ и l_b. Этот параллелограмм пересекают прямые  l₁, l₂, ..., l_b–1  (и никакие другие из рассматриваемого семейства). Абсциссы соседних целых точек на каждой из этих прямых отличаются на b (см. задачу 60514), поэтому каждая из них содержит не более одной целой точки, принадлежащей P. Две верхние (нижние) вершины параллелограмма как раз и являются соседними целыми точками на прямой l_b (l₀), поэтому на сторонах P нет целых точек, отличных от вершин. Следовательно, на каждой из прямых  x = 1,  x = 2,  ...,  x = b – 1  есть ровно по одной целой точке, лежащей внутри P. Всего таких точек  b – 1.  Каждая из них лежит на одной из прямых  l₁, l₂, ..., l_b–1.  Значит, на каждой из этих прямых лежит по одной из этих точек. В частности, есть целая точка на прямой l₁. Это и значит, что уравнение  ax + by = 1  имеет решение в целых числах.

Замечания

1. Из второго способа ясно, что  m = d,  то есть
      НОК(a, b) является наименьшим натуральным числом, представимым в виде  ax + by.

2. В указанном источнике была другая, но практически эквивалентная формулировка (см. задачу 60488 б).

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	2
Название	Алгоритм Евклида
Тема	Алгоритм Евклида
задача
Номер	03.037