Глава 1. Арифметика

1.1.

Назад Вперед
Назад Вперед

1.1.3.

 

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

Так, 3 ≡ 1 (mod 2), 7 ≡ 1 (mod 3). Два числа сравнимы по модулю 2, если они оба четны, либо если они оба нечетны. По модулю 1 все целые числа сравнимы между собой.

В том случае, если число n делится на m, то оно сравнимо с нулем по модулю m:
n ≡ 0 (mod 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.

Пример 1

Доказать свойство делимости на 9: число делится на 9 тогда и только тогда, когда сумма всех его цифр делится на 9.

Показать решение

Пример 2. Свойство делимости на 19

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

Показать решение

В заключение этого параграфа приведем формулировку малой теоремы Ферма.

Малая теорема Ферма

Пусть p – простое число, a – натуральное число. Тогда ap – a делится на p:
ap ≡ a (mod p).

В частности, если p – простое число, a – натуральное число, взаимно простое с p, то
ap – 1 ≡ 1 (mod p).

Пример 3

Запишите состоящее из одних девяток натуральное число, которое делится на 17 без остатка.

Показать решение


Назад Вперед
Наверх

Включить/Выключить фоновую музыкуВключить/Выключить звуки событий
Сфа
сфа
sani-shop.ru
потолочный кондиционер кассетный
aero-control.ru

 

Смотрите также: Математика, Английский язык, Химия, Биология, Физика, География, Астрономия.
А также: библиотека ЭОРов и образовательный онлайн-сервис с тысячами интерактивных работ "Облако знаний".