Задание олимпиады по делимости: равенство по модулю и деление
Докажите, что 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.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.