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

Разделить $a$ на $m$ с остатком — записать $a = mq + r$, где $q$ целое и $0 \le r < m$. Числа с остатком $r$ имеют вид $mk + r$: например, $30035 = 60 \cdot 500 + 35$.

Остаток суммы, разности и произведения равен остатку суммы, разности и произведения остатков. Поэтому квадрат или степень проверяют по остаткам: вместо числа подставьте каждый возможный остаток $0, 1, \ldots, m - 1$.

Числа $a$ и $b$ дают одинаковые остатки при делении на $m$ тогда и только тогда, когда $a - b$ делится на $m$. Если все числа набора дают при делении на $m$ остаток $r$, каждое из них имеет вид $mk + r$. Так бывает, например, когда среднее любых нескольких чисел набора целое (среднее любых k чисел).

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

Запишите число через разряды (запись числа): $\overline{abc} = 100a + 10b + c = (99a + 9b) + (a + b + c)$. Слагаемое $99a + 9b$ делится на 9. Поэтому число и сумма его цифр дают одинаковые остатки при делении на 9 и на 3. Для числа с любым количеством цифр довод тот же: $10^k - 1 = 99\ldots9$ делится на 9.

Отсюда признаки делимости на 3 и на 9. В цепочке «число — сумма его цифр — сумма цифр этой суммы» все числа дают один и тот же остаток при делении на 9.

Числа взаимно просты, если их наибольший общий делитель равен 1. Если $m$ и $n$ взаимно просты, число делится на $mn$ тогда и только тогда, когда оно делится и на $m$, и на $n$. Так проверяют делимость на $45 = 5 \cdot 9$, на $60 = 3 \cdot 4 \cdot 5$, на $12 = 3 \cdot 4$. Множители должны быть взаимно простыми: 18 делится на 2 и на 6, но не делится на 12.

Если два числа делятся на $m$, их сумма и разность тоже делятся на $m$.

Если $ab$ делится на $m$, а $a$ и $m$ взаимно просты, то $b$ делится на $m$. Если общий делитель есть, сначала разделите на него оба числа: из «$35b$ делится на 60» следует «$7b$ делится на 12», а 7 и 12 взаимно просты, поэтому $b$ делится на 12.

Так в пункте в) находят наименьшее значение по делимости.

Если простое число $p$ делит произведение $ab$, то $p$ делит $a$ или $b$. Для составного делителя это неверно: $2 \cdot 3$ делится на 6, а ни 2, ни 3 на 6 не делятся. Составной делитель разложите на взаимно простые множители и проверьте каждый (делимость на произведение).

Так разбирают произведения соседних чисел: $n^2 - n = n(n - 1)$, $n^2 - 1 = (n - 1)(n + 1)$. Соседние числа $n - 1$ и $n$ взаимно просты, а из двух соседних чисел одно чётное.

Количества камней, писем, учеников — целые неотрицательные числа. Уравнение вида $5a + 13b = 79$ с такими неизвестными решают через остатки: обе части дают одинаковые остатки при делении на любое число. Возьмите делитель, на который делится один из коэффициентов: при делении на 5 слагаемое $5a$ даёт остаток 0, и остаётся условие на $b$.

Подходящие $b$ идут с шагом 5. Каждое из них проверьте по границам из условия.

Среди любых $m$ натуральных чисел подряд ровно одно делится на $m$. Разделите количество чисел $k$ на $m$ с остатком: $k = mq + r$. Среди $k$ чисел подряд кратных $m$ ровно $q$ при $r = 0$, и $q$ или $q + 1$ при $r > 0$.

Обратно: если среди чисел подряд $p$ кратных $m$, между первым и последним из них $m(p - 1)$ шагов, и чисел не меньше $m(p - 1) + 1$. Если кратных ровно $p$, чисел не больше $m(p + 1) - 1$: иначе в ряд попадёт ещё одно кратное.

Сумма чётна тогда и только тогда, когда нечётных слагаемых чётное число. Произведение чётно, если чётен хотя бы один множитель. Числа $a + b$ и $a - b$ всегда одной чётности.

Если никакие два числа набора не имеют общего делителя, большего 1 (числа попарно взаимно просты), чётных среди них не больше одного: у двух чётных чисел общий делитель 2. Чётность суммы такого набора зависит от того, есть ли в нём чётное число. У чисел, больших 1, наименьшие простые делители тогда различны, и это даёт оценку суммы снизу. Как чётность и такая оценка доказывают ответ «нет», показано в доказательстве невозможности.