Задача 30587

Тема:    [ Арифметика остатков (прочее) ]

Сложность: 2+ Классы: 7,8

Условие

Докажите, что  a ≡ b (mod m)  тогда и только тогда, когда  a – b  делится на m.

Решение

  Пусть  a ≡ b (mod m).  Обозначим одинаковый для a и b остаток при делении на m через r. Тогда  a = mk + r,  b = ml + r.  Отсюда  a – b = m(k – l).
  Обратно, пусть  a – b  делится на m.  Разделим a и b на m с остатком. Получим  a = mk + r,  b = ml + s.  Значит,  r – s  делится на m. Так как  |r – s| < m,  то  r = s.

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

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	10
Название	Делимость-2
Тема	Теория чисел. Делимость
задача
Номер	001