Учебник. Сравнения по модулю и признаки делимости
Два натуральных числа a и b, разность которых кратна натуральному числу m, называются сравнимыми по модулю m:
Так, 3 ≡ 1 (mod 2), 7 ≡ 1 (mod 3). Два числа сравнимы по модулю 2, если они оба четны, либо если они оба нечетны. По модулю 1 все целые числа сравнимы между собой.
В том случае, если число n делится на m, то оно сравнимо с нулем по модулю m:
Свойства сравнений по модулю вытекают из свойств арифметических операций.
- Пусть a ≡ b (mod m), c ≡ d (mod m). Тогда:
- a + c ≡ b + d (mod m),
- a – c ≡ b – d (mod m),
- ac ≡ bd (mod m).
- Пусть ab ≡ 0 (mod m), и числа a и m взаимно просты. Тогда b ≡ 0 (mod m).
Отметим, что обе части сравнения не всегда можно сократить на какой-либо множитель. Так, 6 ≡ 3 (mod 3), но 2 не сравнимо с 1 по этому же модулю.
Простейшим применением сравнений по модулю является определение делимости чисел. Дадим для начала несколько правил.
Признак делимости на 2. Число, делящееся на 2, называется чётным, не делящееся на 2 – нечётным. Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2.
Признак делимости на 5. Число делится на 5 тогда и только тогда, когда его последняя цифра – 5 или 0.
Признак делимости на 25. Число делится на 25 тогда и только тогда, когда две его последние цифры либо нули, либо образуют число, делящееся на 25.
Признаки делимости на 10, 100, 1000. Число делится на 10 тогда и только тогда, когда его последняя цифра – 0. Число делится на 100 тогда и только тогда, когда две его последние цифры – нули. Число делится на 1000 тогда и только тогда, когда три его последние цифры – нули.
Признак делимости на 4. Число делится на 4 тогда и только тогда, когда две его последние цифры – нули, либо когда двузначное число, образованное двумя его последними цифрами, делится на 4.
Признак делимости на 3. Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.
Признак делимости на 9. Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.
Признак делимости на 11. Число делится на 11 тогда и только тогда, когда сумма его цифр, стоящих на нечётных местах, либо равна сумме цифр, стоящих на чётных местах, либо отличается от неё на число, кратное 11.
Доказать свойство делимости на 9: число делится на 9 тогда и только тогда, когда сумма всех его цифр делится на 9.
Произвольное число где – цифры числа x в десятичной записи. Так как 10 ≡ 1 (mod 9), то 102 ≡ 1 (mod 9) и вообще 10k ≡ 1 (mod 9) для любого натурального k. Отсюда Теорема доказана.
Доказать, что число делится без остатка на 19 тогда и только тогда, когда число его десятков, сложенное с удвоенным числом единиц, кратно 19.
Для любого натурального x верно равенство x = x1 + 10x2, где x1 – число единиц, x2 – число десятков этого числа. Пусть y = x2 + 2x1 (то есть y – число десятков, сложенное с удвоенным числом единиц). Тогда 10y – x = 19x1 ≡ 0 (mod 19), откуда следует, что x ≡ 0 (mod 19) тогда и только тогда, когда 10y ≡ 0 (mod 19), то есть y ≡ 0 (mod 19). Утверждение доказано.
В заключение этого параграфа приведем формулировку малой теоремы Ферма.
Пусть p – простое число, a – натуральное число. Тогда ap – a делится на p:
В частности, если p – простое число, a – натуральное число, взаимно простое с p, то
Запишите состоящее из одних девяток натуральное число, которое делится на 17 без остатка.
Воспользуемся малой теоремой Ферма: ap – 1 ≡ 1 (mod p). Положим a = 10, p = 17. Тогда 1016 ≡ 1 (mod 17) или 1016 – 1 ≡ 0 (mod 17). Число 1016 – 1 состоит из 16 девяток. Это и есть одно из чисел, которые делятся на 17 без остатка.
Ответ. 9 999 999 999 999 999.
А также: библиотека ЭОРов и образовательный онлайн-сервис с тысячами интерактивных работ "Облако знаний".