Примеры. Найти остаток от деления на 3 числа: А=-·
Решение: очевидно 131 (mod 3)
2 -1 (mod 3)
5 -1 (mod 3), тогда
-· 1-1 0 (mod 13)
Ответ:искомый остаток равен нулю, и А делится на 3.
Доказать, что 1 + 13, если х=3n+1 (n=0,1,2,…).
Решение: Докажем, что 1+(mod13) или 1+(mod 13)
1+=1++=
= 1+
Так как 271 (mod 13), то 1++1·3+1·9 (mod 13).
ч.т.д.
3. Найдём остаток при делении с остатком числа на 24.
Имеем: 1 (mod 24), поэтому
1 (mod 24)
Прибавляя к обеим частям сравнения по 55, получаем:
(mod 24).
Имеем: (mod 24), поэтому
(mod 24) при любом k є N.
Следовательно (mod 24). Поскольку (-8) 16(mod 24), искомым остатком является 16.
Обе части сравнения можно умножать на одно и то же целое число.
Доказательство. Так какab(mod т), то (а—b) т. А так как т n, то в силу транзитивности отношения делимости (а—b n), то есть аb(mod n).
Пример. Найти остаток от деления 196 на 7.
Решение: Зная, что 196=, можно записать 196(mod 14). Воспользуемся предыдущим свойством, 14 7, получим 196(mod 7), то есть 196 7.
Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.
