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

  • 5 мин чтения
  • Послушать — 4 мин
  • 12 карточек

Математика, 7 класс · Л. Г. Петерсон, Д. Л. Абраров, Е. В. Чуткова · § 2. Развитие теории делимости

Теорема 1. Целые числа a и b имеют одинаковые остатки при делении на m тогда и только тогда, когда их разность a - b делится на m.

Почему. Если a = mc₁ + r и b = mc₂ + r, то a - b = m(c₁ - c₂). Обратно, если a - b = mc и b = mq + r, то a = m(c + q) + r — остаток тот же.

Определение. Если целые числа a и b дают одинаковые остатки при делении на натуральное число m, говорят, что a и b сравнимы по модулю m, и пишут:

a ≡ b pmod m.

Например, 57 ≡ 2 pmod11, потому что 57 - 2 = 55 делится на 11; -61 ≡ 11 pmod 8: -61 - 11 = -72 делится на 8. Запись a ≡ 0 pmod m означает, что a делится на m, а a ≡ r pmod b — что a даёт при делении на b остаток r (если 0 ≤ r < b).

Часы показывают время «по модулю 12», дни недели повторяются «по модулю 7».

Свойства сравнений (как у равенств):

СвойствоЗапись
Рефлексивностьa ≡ a pmod m
Симметричностьесли a ≡ b pmod m, то b ≡ a pmod m
Транзитивностьесли a ≡ b и b ≡ c pmod m, то a ≡ c pmod m

Пример. Число сравнимо с 585 242 по модулю 73. Докажем, что оно сравнимо и с 73 000 001. Оба числа дают при делении на 73 остаток 1, значит, они сравнимы, а по транзитивности наше число сравнимо и со вторым.

Правило

1 / 12

Одинаковые остатки

Теорема 1. Целые a и b имеют одинаковые остатки при делении на m тогда и только тогда, когда разность a - b делится на m.

23 = 5 · 4 + 3, 8 = 5 · 1 + 3, и 23 - 8 = 15 vdots 5.

Свойство

2 / 12

Почему так

Если a = mc₁ + r и b = mc₂ + r, то

a - b = m(c₁ - c₂)

Обратно: если a - b = mc и b = mq + r, то

a = m(c + q) + r

Определение

3 / 12

Сравнение по модулю

Если целые a и b дают одинаковые остатки при делении на натуральное m, то a и b сравнимы по модулю m:

a ≡ b pmod m

57 ≡ 2 pmod11: 57 - 2 = 55 делится на 11.

Правило

4 / 12

Как проверить сравнение

a ≡ b pmod m ⟺ (a - b) vdots m

-61 ≡ 11 pmod 8: -61 - 11 = -72, и -72 vdots 8.

40 not≡ 17 pmod 6: 40 - 17 = 23 на 6 не делится.

Проверь себя

5 / 12

Верно ли сравнение?

Проверяем разность a - b.

Верно ли, что 38 ≡ -2 pmod 8?

данет: остатки 6 и -2нет: 36 не делится на 8
Ответ и объяснение

38 - (-2) = 40, и 40 vdots 8. У обоих чисел остаток 6.

Правило

6 / 12

Нуль и остаток справа

a ≡ 0 pmod m — то же, что a vdots m:

45 ≡ 0 pmod 9.

a ≡ r pmod m при 0 ≤ r < m — значит, r — остаток от деления a на m:

47 ≡ 2 pmod 9, остаток 2.

Пример

7 / 12

Часы и календарь

Часы считают время по модулю 12:

15 ≡ 3 pmod12 — 15 часов на циферблате — это 3.

Дни недели повторяются по модулю 7: через 7 и через 14 дней — тот же день недели.

Свойства

8 / 12

Свойства сравнений

Сравнения ведут себя как равенства:

СвойствоЗапись
рефлексивностьa ≡ a
симметричностьa ≡ b ⇒ b ≡ a
транзитивностьa ≡ b, b ≡ c ⇒ a ≡ c

Всё — по одному модулю m.

Разбор

9 / 12

Транзитивность в деле

Число x ≡ 585 242 pmod73. Докажем, что x ≡ 73 000 001 pmod73.

  1. Первое число

    585 242 = 73 · 8017 + 1 — остаток 1.

  2. Второе число

    73 000 001 = 73 · 1 000 000 + 1 — остаток 1.

  3. Связь

    Остатки равны: 585 242 ≡ 73 000 001 pmod73.

  4. Ответ

    x ≡ 585 242 и 585 242 ≡ 73 000 001, по транзитивности x ≡ 73 000 001 pmod73.

Частая ошибка

10 / 12

Справа не всегда остаток

57 ≡ 13 pmod11 — верно: 57 - 13 = 44 vdots 11.

Но 13 — не остаток: 13 > 11. Остаток 57 — это 2.

Число справа — остаток, только если 0 ≤ r < m.

Проверь себя

11 / 12

Наименьшее натуральное

x ≡ 30 pmod 7: x - 30 делится на 7.

Наименьшее натуральное x, что x ≡ 30 pmod 7:

3092
Ответ и объяснение

30 = 7 · 4 + 2: остаток 2, и 2 - 30 = -28 vdots 7. Меньше 2 — только 2 - 7 < 0.

Главное

12 / 12

Главное

  • a ≡ b pmod m — одинаковые остатки при делении на m.
  • Проверка: (a - b) vdots m.
  • a ≡ 0 pmod m ⟺ a vdots m; справа остаток, если 0 ≤ r < m.
  • Рефлексивность, симметричность, транзитивность — как у равенств.

Проверь себя: тест по теме

Несколько заданий по этой теме из того же учебника. Каждый ответ проверяется сразу, а начать можно без регистрации.

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест