Арифметика остатков

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

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

Числа, сравнимые по модулю m, имеют одинаковые остатки, и их удобно считать «одним числом». Для этого числовую прямую как бы наматывают на окружность, разделённую на m равных частей: точки деления — остатки 0, 1, 2, …, m - 1 (отсчёт против часовой стрелки). Так устроен циферблат часов: 0, 12, 24 — одна и та же точка.

Сложение остатков. Если A ≡ a, B ≡ b pmod m, то суммой остатков a и b называют остаток c от деления A + B на m: a + b ≡ c pmod m. Например, по модулю 12: 5 + 2 ≡ 7, а 11 + 4 = 15 ≡ 3.

Так же вводят вычитание и умножение. Правило: если результат стал отрицательным или не меньше m, переходи к его остатку от деления на m.

Таблицы по модулю 4:

a + b0123
00123
11230
22301
33012
a · b0123
00000
10123
20202
30321

Теоремы. Если a ≡ b pmod m и c ≡ d pmod m, то

a + c ≡ b + d, a - c ≡ b - d, ac ≡ bd pmod m.

Пример. Квадрат целого числа либо кратен 3, либо даёт остаток 1: если a ≡ 0, то a² ≡ 0; если a ≡ 1, то a² ≡ 1; если a ≡ 2, то a² ≡ 4 ≡ 1 pmod 3.

Наглядно

1 / 13

Прямая на окружности

Числовую прямую наматывают на окружность из m равных частей. Точки — остатки 0, 1, …, m - 1, отсчёт против часовой стрелки.

Окружность из 4 частей
Окружность из 4 частей

Так устроены часы: 0, 12, 24 — одна точка.

Определение

2 / 13

Сумма остатков

Пусть A ≡ a, B ≡ b pmod m. Суммой остатков a и b называют остаток c от деления A + B на m:

a + b ≡ c pmod m

По модулю 12: 5 + 2 ≡ 7, 11 + 4 = 15 ≡ 3.

Правило

3 / 13

Вычитание и умножение

Так же вводят разность и произведение остатков.

Правило: если результат отрицательный или не меньше m, переходи к его остатку от деления на m.

По модулю 5: 2 - 4 = -2 ≡ 3; 3 · 4 = 12 ≡ 2.

Проверь себя

4 / 13

Сложи по модулю 7

Результат ≥ m — бери остаток.

По модулю 7: 5 + 6 ≡ ?

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

5 + 6 = 11 = 7 · 1 + 4, поэтому 5 + 6 ≡ 4 pmod 7.

Пример

5 / 13

Сложение по модулю 4

+0123
00123
11230
22301
33012

3 + 2 = 5 ≡ 1, 2 + 2 = 4 ≡ 0.

Пример

6 / 13

Умножение по модулю 4

·0123
00000
10123
20202
30321

3 · 3 = 9 ≡ 1, 2 · 2 = 4 ≡ 0.

Формула

7 / 13

Действия со сравнениями

Если a ≡ b и c ≡ d pmod m, то

a + c ≡ b + d ; a - c ≡ b - d ; ac ≡ bd pmod m

Сравнения по одному модулю можно складывать, вычитать и умножать, как равенства.

Проверь себя

8 / 13

Остаток произведения

Числа можно заменить их остатками.

a ≡ 3, b ≡ 4 pmod 5. Остаток от деления ab на 5:

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

ab ≡ 3 · 4 = 12 ≡ 2 pmod 5.

Разбор

9 / 13

Большое произведение

Найдём остаток от деления 38 · 27 на 5, не перемножая числа.

  1. Остатки

    38 ≡ 3, 27 ≡ 2 pmod 5

  2. Произведение

    38 · 27 ≡ 3 · 2 = 6 ≡ 1 pmod 5

  3. Ответ

    Остаток 1. Проверка: 38 · 27 = 1026 = 5 · 205 + 1.

Разбор

10 / 13

Квадрат по модулю 3

Докажем ещё раз: квадрат целого числа либо кратен 3, либо даёт остаток 1.

  1. Остаток 0

    a ≡ 0 ⇒ a² ≡ 0 · 0 = 0 pmod 3

  2. Остаток 1

    a ≡ 1 ⇒ a² ≡ 1 · 1 = 1 pmod 3

  3. Остаток 2

    a ≡ 2 ⇒ a² ≡ 2 · 2 = 4 ≡ 1 pmod 3

  4. Ответ

    a² ≡ 0 или a² ≡ 1 pmod 3 — что и требовалось.

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

11 / 13

Забытый переход к остатку

По модулю 5: 11 ≡ 1, 8 ≡ 3.

11 - 8 ≡ 1 - 3 = -2 — не остаток: -2 < 0.

Верно: -2 ≡ 3 pmod 5. Проверка: 11 - 8 = 3.

Проверь себя

12 / 13

Вычти по модулю 7

Отрицательный результат — бери остаток.

По модулю 7: 2 - 5 ≡ ?

-334
Ответ и объяснение

2 - 5 = -3 = 7 · (-1) + 4, поэтому 2 - 5 ≡ 4 pmod 7.

Главное

13 / 13

Главное

  • Сумма, разность, произведение остатков — остаток результата от деления на m.
  • Результат < 0 или ≥ m — переходи к остатку.
  • a ≡ b, c ≡ d ⟹ a ± c ≡ b ± d, ac ≡ bd pmod m.
  • Большие числа заменяй остатками, потом считай.

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

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

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