9. Сравнения и признаки делимости
Определение. Пусть и
— целые числа,
— натуральное. Говорят, что число
сравнимо с
по
модулю , если
.
Обозначение. .
Пример.
Теорема. тогда и только тогда, когда
и
дают при делении на
равные остатки.
Доказательство. Разделим и
на
с остатками
Тогда
Следовательно,
Свойства сравнений
1. (рефлексивность),
2. (симметричность),
3. (транзитивность),
4. .
5. , НОД
.
Доказательство.
1.
2.
3.
4.
5.
Признаки делимости
Пусть — натуральное число,
,
1. Признаки делимости на и
Так как , то
Натуральное число сравнимо с суммой своих цифр по модулю и по модулю
.
2. Признаки делимости на и на
Натуральное число сравнимо со своей последней цифрой по модулю и по модулю
.
3. Признаки делимости на и на
Натуральное число сравнимо по модулю и по модулю
с числом, образованным его двумя последними цифрами.
4. Признак делимости на
, если
— четное,
, если
> — нечетное.
Натуральное число сравнимо по модулю с числом, которое получится, если сложить все цифры, стоящие на нечетных местах, считая справа, и вычесть из этой суммы сумму всех остальных цифр.
Задачи.
1. Найдите остаток от деления числа
на
.
2. Найдите остаток от деления
a) на
;
б) на
, если
и
.
3. Докажите, что если , то
.
4. Докажите, что
делится на .
5. Докажите, что если делится на
, то
.
6. Докажите, что если натуральные числа и
таковы, что
делится на
, то
делится на
.
7. Докажите, что если , то
, где
– наибольший общий делитель
и
.
8. Выведите признаки делимости на .
1 Магическая числовая пирамида в десятичной системе счисления | Математика, которая мне нравится:
[...] любое число в десятичной системе счисления записывается как [...]
1 Январь 2012, 12:212 Задача от Hewlett-Packard | Математика, которая мне нравится:
[...] значение при . Для этого переведем в двоичную систему счисления: И очевидно, что число, в двоичной записи которого [...]
18 Июль 2012, 0:093 Доказательство конца света в троичной системе счисления | Математика, которая мне нравится:
[...] ставлю 0 последним, потому что в десятичной системе счисления на самом деле есть только девять цифр плюс ноль, [...]
2 Декабрь 2012, 0:06