Делимость и остатки

Зачем это в ЕГЭ. Задание №19, 4 первичных балла. Делимость и остатки — основной инструмент для пунктов б) и в): доказательство невозможности, оценка минимума/максимума. Признаки делимости, чётность, остатки mod 2, 3, 4, 9 позволяют сузить перебор или вывести противоречие.

Главная идея. $a\equiv b\pmod m$ означает $m\mid(a-b)$; остатки при делении на $m$ дают конечный набор классов, которые можно перебрать. Это позволяет заменить бесконечный перебор конечным.

Алгоритм (чеклист).
1. Определить, по какому модулю работать: $m=2$ (чётность), $m=3$ или $9$ (сумма цифр), $m=4$ (квадраты), $m=10$ (последняя цифра).
2. Выписать остатки каждого слагаемого/множителя и вычислить остаток результата.
3. Если нужно доказать, что число не делится на $k$ — показать, что остаток по mod $k$ ненулевой.
4. НОД: алгоритм Евклида или разложение на простые. НОК: $\mathrm{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$.
5. Признаки: на $3$ — сумма цифр кратна $3$; на $4$ — последние две цифры кратны $4$; на $9$ — сумма цифр кратна $9$; на $11$ — знакопеременная сумма цифр кратна $11$.

Опоры (кратко).
- Квадраты: $n^2\bmod 4\in\{0,1\}$; $n^2\bmod 3\in\{0,1\}$.
- Произведение $k$ последовательных целых делится на $k!$.
- $a\mid b$ и $a\mid c$ $\Rightarrow$ $a\mid(b\pm c)$ и $a\mid(bc)$.

Пример 1 (алгоритм Евклида). $\gcd(84,60)$.

Шаг 1. $84=60\cdot1+24$; $60=24\cdot2+12$; $24=12\cdot2+0$.

Шаг 2. $\gcd=12$. Значит $\mathrm{lcm}(84,60)=\frac{84\cdot60}{12}=420$.

Пример 2 (остатки для доказательства). Доказать, что $n^2+2$ не делится на $4$ ни при каком целом $n$.

Шаг 1. Остатки $n\bmod4$: $0,1,2,3$. Квадраты: $0,1,0,1$ (mod 4).

Шаг 2. $n^2+2\bmod4$: $2,3,2,3$. Ни разу не $0$. ЧТД.

Пример 3 (сумма цифр). Делится ли $123456789$ на $9$? Сумма цифр: $1+2+\ldots+9=45$, $45\div9=5$ — да.

Типичные ошибки.
1. Путают НОД и НОК — НОД делит оба, НОК делится на оба.
2. Остаток берут неверно — $r$ должен быть $0\le r<m$; для отрицательных: $-2\bmod 3=1$.
3. «Делится на $a$ и на $b$» $\ne$ «делится на $ab$» — только при $\gcd(a,b)=1$.
4. Забывают проверить все остатки — пропускают один случай и делают неверный вывод.

Дальше. Последовательности и числовые наборы — подтемы №19 в тренажёре.