Учебник. Сравнения по модулю и признаки делимости




Сравнения по модулю и признаки делимости

Два натуральных числа 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.

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

Произвольное число x= x n ... x 2 x 1 ¯ = x 1 + x 2 ċ 10 1 + x 3 ċ 10 2 +...+ x n ċ 10 n-1 , где x 1 ...,  x n – цифры числа x в десятичной записи. Так как 10 ≡ 1 (mod 9), то 102 ≡ 1 (mod 9) и вообще 10k ≡ 1 (mod 9) для любого натурального k. Отсюда x 1 + x 2 ċ10+...+ x n ċ 10 n-1 x 1 + x 2 +...+ x n  ( mod 9 ) . Теорема доказана.

Доказать, что число делится без остатка на 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: ap ≡ a (mod p).

В частности, если p – простое число, a – натуральное число, взаимно простое с p, то ap – 1 ≡ 1 (mod 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.





 

Бетонного завода в серпухове http://betonnyi-zavod.ru
betonnyi-zavod.ru
© Физикон, 1999-2015