← Маршрут ЕГЭ
Тема 58 из 72 · Теория чисел

Остатки. Сравнения. Модулярная арифметика

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

ТГ-каналПодписывайся · там же запись на вводный урок t.me/algo_math ↗
Содержание 12 разделов
  1. 1. Что такое сравнение по модулю
  2. 2. Зачем нужны сравнения
  3. 3. Основные свойства сравнений
  4. Свойство 1. Складывать можно
  5. Свойство 2. Умножать можно
  6. Свойство 3. В степень возводить можно
  7. Свойство 4. Вычитать можно
  8. 4. Пример: доказательство делимости через сравнения
  9. 5. Остатки отрицательных чисел
  10. 6. Как сравнения помогают в задании №20
  11. Типовая задача из ЕГЭ
  12. 7. Типичные ошибки при работе со сравнениями

1. Что такое сравнение по модулю

Сравнение по модулю — это язык, на котором мы говорим об остатках. Вместо того чтобы каждый раз писать «при делении на $m$ даёт остаток $r$», мы пишем коротко и удобно.

$$a \equiv b \pmod m \;\Longleftrightarrow\; a \text{ и } b \text{ дают одинаковые остатки при делении на } m$$

Или, что то же самое:

$$a \equiv b \pmod m \;\Longleftrightarrow\; m \mid (a-b)$$

Примеры:

  • $17 \equiv 2 \pmod 5$, потому что $17 = 5 \cdot 3 + 2$, а $2 = 5 \cdot 0 + 2$.
  • $20 \equiv 0 \pmod 5$, потому что $20$ делится на $5$.
  • $14 \equiv 4 \pmod 10$, потому что $14 = 10 \cdot 1 + 4$, а $4 = 10 \cdot 0 + 4$.
Как читать

«$a \equiv b \pmod m$» читается как «$a$ сравнимо с $b$ по модулю $m$» или «$a$ и $b$ дают одинаковый остаток при делении на $m$».

2. Зачем нужны сравнения

Сравнения позволяют заменять большие числа на маленькие (их остатки) при выполнении арифметических операций. Это сильно упрощает вычисления, особенно когда нужно проверить делимость или найти остаток.

Ключевая идея: если два числа дают одинаковый остаток при делении на $m$, то при сложении, вычитании, умножении и возведении в степень их можно заменять друг на друга — результат сравнения не изменится.

3. Основные свойства сравнений

Свойство 1. Складывать можно

Если $a \equiv b \pmod m$ и $c \equiv d \pmod m$, то:

$$a + c \equiv b + d \pmod m$$

Пример: $17 \equiv 2 \pmod 5$, $13 \equiv 3 \pmod 5$. Тогда $17+13=30$, $2+3=5$. $30 \equiv 5 \equiv 0 \pmod 5$. ✅

Свойство 2. Умножать можно

Если $a \equiv b \pmod m$ и $c \equiv d \pmod m$, то:

$$a \cdot c \equiv b \cdot d \pmod m$$

Пример: $17 \equiv 2 \pmod 5$, $13 \equiv 3 \pmod 5$. Тогда $17\cdot13=221$, $2\cdot3=6$. $221 \equiv 6 \equiv 1 \pmod 5$. ✅

Свойство 3. В степень возводить можно

Если $a \equiv b \pmod m$, то для любого натурального $n$:

$$a^n \equiv b^n \pmod m$$

Пример: $2 \equiv -1 \pmod 3$. Тогда $2^{10} \equiv (-1)^{10} = 1 \pmod 3$. ✅

Свойство 4. Вычитать можно

Если $a \equiv b \pmod m$ и $c \equiv d \pmod m$, то:

$$a - c \equiv b - d \pmod m$$

4. Пример: доказательство делимости через сравнения

Пример

Докажите, что $1000\cdot1001\cdot1002\cdot1003-24$ делится на $999$.

Решение.

  1. Замечаем, что $1000$, $1001$, $1002$, $1003$ — это числа, близкие к $999$.
  2. Найдём их остатки при делении на $999$:
    • $1000 = 999 + 1 \Rightarrow 1000 \equiv 1 \pmod{999}$
    • $1001 = 999 + 2 \Rightarrow 1001 \equiv 2 \pmod{999}$
    • $1002 = 999 + 3 \Rightarrow 1002 \equiv 3 \pmod{999}$
    • $1003 = 999 + 4 \Rightarrow 1003 \equiv 4 \pmod{999}$
  3. По свойству умножения сравнений:
    4. $$1000\cdot1001\cdot1002\cdot1003 \equiv 1\cdot2\cdot3\cdot4 = 24 \pmod{999}$$
  4. Тогда:
    5. $$1000\cdot1001\cdot1002\cdot1003 - 24 \equiv 24 - 24 = 0 \pmod{999}$$
  5. Значит, выражение делится на $999$.

5. Остатки отрицательных чисел

Важно: остаток всегда должен быть неотрицательным и меньше модуля.

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

Примеры

$-7$ при делении на $10$ даёт остаток $3$:

  1. $-7 = -10 + 3$
  2. $-10$ делится на $10$, остаток $3$.

$-23$ при делении на $7$ даёт остаток $5$:

  1. $-23 = -28 + 5$
  2. $-28$ делится на $7$, остаток $5$.

$-1$ при делении на $m$ даёт остаток $m-1$:

  1. $-1 = -m + (m-1)$
  2. $-m$ делится на $m$, остаток $m-1$.

6. Как сравнения помогают в задании №20

В задании №20 сравнения по модулю чаще всего используются для:

  • Доказательства делимости — показываем, что выражение сравнимо с $0$ по нужному модулю.
  • Поиска остатков — нужно найти, какой остаток даёт число при делении на заданное число.
  • Доказательства от противного — показываем, что при некоторых условиях остатки не совпадают.

Типовая задача из ЕГЭ

Задача

Докажите, что $n^5 - n$ делится на $5$ для любого натурального $n$.

Решение.

  1. При делении на $5$ число $n$ может давать только остатки $0, 1, 2, 3, 4$.
  2. Проверим каждый случай:
    • $n \equiv 0 \pmod 5$: $n^5 \equiv 0^5 = 0$, $n^5 - n \equiv 0 - 0 = 0$.
    • $n \equiv 1 \pmod 5$: $n^5 \equiv 1^5 = 1$, $n^5 - n \equiv 1 - 1 = 0$.
    • $n \equiv 2 \pmod 5$: $2^5 = 32 \equiv 2 \pmod 5$, $n^5 - n \equiv 2 - 2 = 0$.
    • $n \equiv 3 \pmod 5$: $3^5 = 243 \equiv 3 \pmod 5$ (проверяем: $243 = 5\cdot48 + 3$), $n^5 - n \equiv 3 - 3 = 0$.
    • $n \equiv 4 \pmod 5$: $4 \equiv -1 \pmod 5$, $4^5 \equiv (-1)^5 = -1 \equiv 4 \pmod 5$, $n^5 - n \equiv 4 - 4 = 0$.
  3. Во всех случаях получаем $0$.
  4. Значит, $n^5 - n$ делится на $5$ для любого $n$.

7. Типичные ошибки при работе со сравнениями

Ошибка Как правильно
Делить сравнения Сравнения нельзя делить! Только складывать, вычитать, умножать.
Забывать про отрицательные остатки $-7 \equiv 3 \pmod{10}$, а не $-7 \equiv -7$.
Путать модуль и остаток Остаток всегда меньше модуля: $0 \le r < m$.
Не проверять все остатки При доказательстве для всех $n$ нужно проверить все возможные остатки.
← 57. Делимость. НОД, НОК. Основная теорема а…