№19. Задачи на олимпиадные темы

Сравнение по модулю

Запоминайте формулы по каждой теме

Осваивайте новые концепции ежедневно

Вдумывайтесь в теоретические материалы

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела: №19. Задачи на олимпиадные темы

Теоретическая справка

#574

Важнейшие свойства сравнений

Определение Целые числа $a$ и $b,$ разность которых делится на натуральное число $m,$ называют сравнимыми по модулю $m$ . Записывают так: $a ≡ b (mod m).$

NB Для неотрицательных чисел определение можно интерпретировать так, что $a$ и $b$ дают равные остатки при делении на $m.$

Свойства сравнений

Везде ниже все числа целые, модуль $m$ — натуральный.

Сравнения можно умножать на число
$a≡ b (mod m) ⇒ ak ≡ bk (mod m)$
Сравнения можно складывать
$} a≡ b (mod m ) c≡ d (mod m ) ⇒ a+ c≡ b+ d (mod m )$
Сравнения можно перемножать
$} a ≡b (mod m ) ⇒ ac≡ bd (mod m ) c≡ d (mod m )$
Сравнения можно возводить в степень
$a≡ b (mod m) ⇒ ak ≡ bk (mod m )$

А зачем нам вообще это нужно?

Фактически вышеперечисленные свойства позволяют нам удобнее работать с остатками и делимостью. К примеру, раньше, если нам нужно было вычислить остаток, который дает какое-то сложное выражения (содержащее операции умножения, сложения, вычитания и возведения в степень, скобки, все это в произвольном порядке) при делении на некоторое число, мы бы стали вычислять значение этого выражения и лишь в конце искать остаток результата. Теперь же мы можем заменить все числа на их остатки, что может существенно упростить вычисления, а также заменять результат на его остаток по ходу вычисления. Следующая задача иллюстрирует, что здесь имеется в виду.

1. Докажите, что число $1000⋅1001 ⋅1002⋅1003− 24$ делится на 999.

Решение. По сути, нам нужно доказать, что

1000⋅1001⋅1002⋅1003 − 24 ≡ 0 (mod 999)

Мы можем заменить любое число на сравнимое с ним по модулю 999, значит,

1000⋅1001⋅1002⋅1003− 24≡ 1⋅2⋅3⋅4− 24≡ 0 (mod 999)

Остатки отрицательных чисел

Остановимся чуть подробнее на остатках отрицательных чисел, потому что иногда на первый взгляд то, как они устроены, может показаться неинтуитивным.

Определение Определим остаток числа $a$ по модулю $m$ как наименьшее целое неотрицательное число, которое нужно вычесть из $a,$ чтобы разность делилась на $m.$

Можно заметить связь этого определения с определением сравнимых по модулю чисел. По данному только что определению $− 7$ дает остаток 3 по модулю 10, так как из $− 7$ нужно вычесть минимум 3, чтобы разность делилась на 10; $− 99$ дает остаток 1 по модулю 100, а $− 1$ дает остаток $m − 1$ по любому модулю $m.$

2. На какую цифру оканчивается число $2015 2016 9 + 7 ?$

Ответ. 0

Решение. Нам нужно найти, с чем сравнима данная сумма по модулю 10.

$pict$

Получили что сумма сравнима с $− 1+ 1 =0$ по модулю 10, а значит, оканчивается нулем. Если какие-то сравнения в цепочках не до конца понятны, рекомендуется обратиться к основным свойствам и проверить по определению.

Предыдущая справка

Следующая справка