Определение. Пусть и
— целые числа,
— натуральное. Говорят, что число
сравнимо с
по
модулю , если
.
Обозначение. .
Пример.
Теорема. тогда и только тогда, когда
и
дают при делении на
равные остатки.
Доказательство. Разделим и
на
с остатками
Тогда
Следовательно,
Свойства сравнений
1. (рефлексивность),
2. (симметричность),
3. (транзитивность),
4. .
5. , НОД
.
Доказательство.
1.
2.
3.
4.
5.
Признаки делимости
Пусть — натуральное число,
,
1. Признаки делимости на и
Так как , то
Натуральное число сравнимо с суммой своих цифр по модулю и по модулю
.
2. Признаки делимости на и на
Натуральное число сравнимо со своей последней цифрой по модулю и по модулю
.
3. Признаки делимости на и на
Натуральное число сравнимо по модулю и по модулю
с числом, образованным его двумя последними цифрами.
4. Признак делимости на
, если
— четное,
, если
> — нечетное.
Натуральное число сравнимо по модулю с числом, которое получится, если сложить все цифры, стоящие на нечетных местах, считая справа, и вычесть из этой суммы сумму всех остальных цифр.
Задачи.
1. Найдите остаток от деления числа на
.
2. Найдите остаток от деления
a) на
;
б) на
, если
и
.
3. Докажите, что если , то
.
4. Докажите, что
делится на .
5. Докажите, что если делится на
, то
.
6. Докажите, что если натуральные числа и
таковы, что
делится на
, то
делится на
.
7. Докажите, что если , то
, где
– наибольший общий делитель
и
.
8. Выведите признаки делимости на .