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

Пусть $m \ge 2$ — натуральное число. Целые числа $a$ и $b$ называют сравнимыми по модулю $m$, если при делении на $m$ они дают один и тот же остаток. Читают: «$a$ сравнимо с $b$ по модулю $m$», знак $\equiv$ — знак сравнения.

Равносильно: $a \equiv b \pmod m$ тогда и только тогда, когда $a - b$ делится на $m$. Если $a = mq_1 + r$, $b = mq_2 + r$, то $a - b = m(q_1 - q_2)$. Обратно, если $a - b = mk$ и $b = mq + r$, то $a = m(q + k) + r$ — остаток тот же.

$100 \equiv 1 \pmod 9$, так как $100 - 1 = 99$ делится на $9$; $\ 1000 \equiv -1 \pmod{11}$, так как $1001 = 11 \cdot 91$.

• 1. Если $a \equiv b$ и $b \equiv c \pmod m$, то $a \equiv c \pmod m$: $\ a - c = (a - b) + (b - c)$ делится на $m$.
• 2. Если $a \equiv b$ и $c \equiv d \pmod m$, то $a + c \equiv b + d$, $\ a - c \equiv b - d$, $\ ac \equiv bd \pmod m$. Для произведения: $ac - bd = a(c - d) + d(a - b)$ — оба слагаемых делятся на $m$.
• 3. Если $a \equiv b \pmod m$, то $a^n \equiv b^n \pmod m$, $n \in \mathbb{N}$ — свойство 2, применённое $n$ раз (индукция).
• 4. Если $P_n(x)$ — многочлен с целыми коэффициентами и $a \equiv b \pmod m$, то $P_n(a) \equiv P_n(b) \pmod m$ — из свойств 2 и 3.
• Сравнения складывают, вычитают, перемножают и возводят в степень, как равенства. Делить обе части нельзя: $6 \equiv 2 \pmod 4$, но $3 \not\equiv 1 \pmod 4$.

1. $6 \equiv -1 \pmod 7$, так как $6 - (-1) = 7$.
2. По свойству 3: $6^{22} \equiv (-1)^{22} = 1 \pmod 7$.
3. Значит, $6^{22} - 1 \equiv 0 \pmod 7$ — делится на $7$.

1. Ищем степень двойки, сравнимую с $\pm1$: $2^5 = 32 = 33 - 1 \equiv -1 \pmod{11}$.
2. $2^{25} = (2^5)^5 \equiv (-1)^5 = -1 \pmod{11}$; $\ 2^4 = 16 \equiv 5 \pmod{11}$.
3. $2^{29} = 2^{25} \cdot 2^4 \equiv -5 \pmod{11}$, а $-5 \equiv 6 \pmod{11}$ — остаток неотрицателен.

Пусть $N = a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + \ldots + a_1 \cdot 10 + a_0$ — число с цифрами $a_n, \ldots, a_0$. Это значение многочлена $P_n(x) = a_n x^n + \ldots + a_1 x + a_0$ при $x = 10$.

Так как $10 \equiv 1 \pmod 9$, по свойству 4: $\ N = P_n(10) \equiv P_n(1) = a_n + \ldots + a_1 + a_0 \pmod 9$.

Число и сумма его цифр дают одинаковые остатки при делении на $9$ (и на $3$, так как $10 \equiv 1 \pmod 3$). Отсюда признаки делимости на $9$ и на $3$ — в обе стороны.

$10 \equiv -1 \pmod{11}$, поэтому $N = P_n(10) \equiv P_n(-1) = a_0 - a_1 + a_2 - \ldots \pmod{11}$.

Число делится на $11$ тогда и только тогда, когда знакочередующаяся сумма его цифр (с последней цифры) делится на $11$.

$918\,082$: $\ 2 - 8 + 0 - 8 + 1 - 9 = -22$ — делится на $11$; действительно, $918\,082 = 11 \cdot 83\,462$.

Таблицу получают перебором остатков $x$ по свойству 3. Удобно брать остатки $\pm1, \pm2$: $(\pm2)^2 = 4$.

1. а) $2013 \equiv 3 \pmod 5$; $\ 3^2 = 9 \equiv -1$, $\ 3^4 \equiv 1$. $\ 2014 = 4 \cdot 503 + 2$: $\ 3^{2014} \equiv 3^2 \equiv 4 \pmod 5$.
2. б) $2015 \equiv 2 \equiv -1 \pmod 3$: $\ (-1)^{2016} = 1$.
3. в) $2010 = 17 \cdot 118 + 4$, $\ 4^2 = 16 \equiv -1 \pmod{17}$. $\ 4^{2011} = (4^2)^{1005} \cdot 4 \equiv (-1)^{1005} \cdot 4 = -4 \equiv 13 \pmod{17}$.

1. а) Сумма цифр $10(1 + 2 + 3) = 60$: число делится на $3$, но не на $9$. Квадрат, делящийся на $3$, делится на $9$ ($x = 3k \Rightarrow x^2 = 9k^2$). Нельзя.
2. б) Сумма цифр $10 \cdot 11 = 110 \equiv 2 \pmod 3$, значит, и число $\equiv 2 \pmod 3$. Квадраты дают остатки $0$ и $1$. Нельзя.
3. в) $1970 \equiv 2 \pmod 3$ ($1 + 9 + 7 + 0 = 17$) — по той же причине нет.

1. а) Да: $111 + 61 + 1 = 173$.
2. б) Числа меньше $109$: $1, 6, 11, 16, 61, 66$. Взять $61$ и $66$ вместе нельзя ($127 > 109$), без одного из них сумма не больше $66 + 16 + 11 + 6 + 1 = 100$. Нет.
3. в) Каждое такое число оканчивается на $1$ или $6$, то есть $\equiv 1 \pmod 5$. Сумма $k$ чисел $\equiv k \pmod 5$, а $1021 \equiv 1$: $k = 1, 6, 11, \ldots$. Одно число $1021$ не подходит (есть цифры $0$ и $2$).
4. Шесть чисел подходят: $666 + 166 + 161 + 16 + 11 + 1 = 1021$.

1. а) Да: $A = 221$, $S = 5$, $221 \cdot 5 = 1105$.
2. Главное: $A \equiv S \pmod 3$ (и $\pmod 9$). Если оба $\equiv 0$, произведение делится на $9$; если оба $\equiv 1$ или оба $\equiv 2$, произведение $\equiv 1 \pmod 3$. Остаток $2$ невозможен.
3. б) $1106 \equiv 2 \pmod 3$ — нет.
4. в) $1504 = 47 \cdot 32$: $A$ кратно $47$ и делит $1504$, то есть $A \in \{188,\ 376,\ 752\}$, а суммы цифр $17, 16, 14$ не равны $8, 4, 2$. $\ 1505 \equiv 2 \pmod 3$. $\ 1506$ делится на $3$, но не на $9$. $\ 1507 = 137 \cdot 11$, и у $137$ сумма цифр $11$ — подходит.

• $a \equiv b \pmod m$ — одинаковые остатки, то есть $m \mid a - b$.
• Сравнения складывают, перемножают, возводят в степень; делить нельзя.
• Остаток степени: найти $a^k \equiv \pm1 \pmod m$ и разбить показатель.
• Число $\equiv$ сумма цифр $\pmod 9$; $\ \equiv$ знакочередующаяся сумма $\pmod{11}$.
• Квадраты: по модулю $3$ и $4$ — только $0, 1$; по модулю $9$ — $0, 1, 4, 7$; последние цифры — $0, 1, 4, 5, 6, 9$.