Урок 4. Делимость и остатки

Математика

🎯 Что ты узнаешь

Признаки делимости на 2, 3, 4, 5, 9, 10 и 11, и почему они работают (а не просто «так надо»).
Что такое остаток и как остатки складываются и умножаются.
Как находить последнюю цифру больших степеней вроде $7^{100}$ .
Что чётность — это просто остаток при делении на 2, и как это помогает.
Как с помощью остатков доказывать, что чего-то быть не может.

📖 Разбираемся в теме

Назови любое огромное число, хоть $7^{100}$ , в котором почти сотня знаков. Я скажу его последнюю цифру за пять секунд, без всякого калькулятора (это, кстати, 1; проверь потом). Звучит как суперспособность? На самом деле это просто магия остатков: оказывается, чтобы узнать что-то важное про гигантское число, часто хватает крошечного остатка. Сейчас ты получишь эту суперспособность сам.

Что значит «делится»

Число $a$ делится на число $b$ , если при делении не остаётся остатка (то есть $a$ нацело разбивается на кусочки по $b$ ). Например, 12 делится на 3, потому что $12 = 3 \cdot 4$ , а 13 на 3 не делится, потому что $13 = 3 \cdot 4 + 1$ , то есть остаётся 1.

Математики говорят так: « $a$ делится на $b$ », если найдётся такое целое число $k$ , что $a = b \cdot k$ . Число $b$ тогда называют делителем, а $a$ — кратным числа $b$ . Например, 6 — делитель числа 24, а 24 — кратное шести.

📌 Три полезных факта о делимости. Их стоит понять один раз, дальше они работают сами:

Если $a$ делится на $b$ , и $b$ делится на $c$ , то и $a$ делится на $c$ (делимость «передаётся по цепочке»).

Если и $a$ , и $b$ делятся на $c$ , то на $c$ делится и сумма $a + b$ , и разность $a - b$ .

Если $a$ делится на $c$ , то и $a \cdot m$ (любое кратное) делится на $c$ .

Проверь на пальцах: 15 и 6 оба делятся на 3, значит и $15 + 6 = 21$ делится на 3 ( $21 = 3 \cdot 7$ ), и $15 - 6 = 9$ тоже.

Признаки делимости — это быстрые способы проверить делимость, не выполняя само деление. Но мы не будем зубрить их вслепую, а разберёмся, ПОЧЕМУ они работают. Понятный признак не забудешь.

Откуда вообще берутся признаки: разложение числа

Любое число можно расписать по разрядам. Например:

3572 = 3000 + 500 + 70 + 2 = 3 \cdot 1000 + 5 \cdot 100 + 7 \cdot 10 + 2.

Это и есть ключ ко всему. Каждый разряд — это цифра, умноженная на 1, 10, 100, 1000 и так далее. Дальше мы будем смотреть, что происходит с каждым таким кусочком при делении: если почти все кусочки на нужное число делятся, то судьбу всего числа решает маленький остаток.

Признаки на 2, 5, 10: смотрим на конец

Числа 10, 100, 1000 и так далее делятся на 2, на 5 и на 10. А значит, все разряды, кроме последнего (единиц), на эти числа делятся. Остаётся только последняя цифра: она одна и решает всё.

📌 Признаки делимости по последней цифре:

Число делится на 2, если его последняя цифра — 0, 2, 4, 6 или 8 (то есть число чётное).

Число делится на 5, если его последняя цифра — 0 или 5.

Число делится на 10, если его последняя цифра — 0.

Признак на 4: две последние цифры

Тут чуть хитрее. На 4 число 10 уже НЕ делится ( $10 = 4 \cdot 2 + 2$ ). Зато 100 делится на 4 ( $100 = 4 \cdot 25$ ), а значит, и все сотни, тысячи, десятки тысяч на 4 делятся. Поэтому решают две последние цифры.

📌 Признак делимости на 4: число делится на 4, если на 4 делится число из двух его последних цифр.

Например, 1316: смотрим на 16, оно делится на 4, значит, и 1316 делится ( $1316 = 4 \cdot 329$ ). А число 1318 не делится: 18 на 4 не делится.

🤔 А заметил ли ты закономерность? На 2 смотрим на 1 цифру, на 4 — на 2 цифры. А на 8? Правильно: на 3 последние цифры, ведь $1000 = 8 \cdot 125$ делится на 8. Признаки для $2, 4, 8, 16, \dots$ устроены одинаково: просто добавляешь по одной цифре с конца.

Признаки на 3 и 9: складываем цифры

Это самые красивые признаки. Секрет в том, что 9, 99, 999 и так далее делятся на 9 (и на 3).

Распишем число, скажем, 372:

372 = 3 \cdot 100 + 7 \cdot 10 + 2.

Хитрый ход: заменим 100 на 99+1, а 10 на 9+1:

372 = 3 \cdot (99 + 1) + 7 \cdot (9 + 1) + 2 = (3 \cdot 99 + 7 \cdot 9) + (3 + 7 + 2) .

Первая скобка делится на 9 (там везде множители 99 и 9). Значит, делимость всего числа на 9 зависит только от второй скобки, а это сумма цифр $3 + 7 + 2 = 12$ !

Отсюда:

📌 Признаки делимости на 3 и 9:

Число делится на 9, если сумма его цифр делится на 9.

Число делится на 3, если сумма его цифр делится на 3 (то же рассуждение: ведь 9, 99, … делятся и на 3).

Проверим 372: сумма цифр 12, она делится на 3, но не на 9. Значит, 372 делится на 3, но не на 9. И правда: $372 = 3 \cdot 124$ .

💡 Лайфхак: складывай цифры повторно. Если сумма цифр всё ещё большая, сложи цифры уже у неё. Возьмём 987654: сумма цифр $9 + 8 + 7 + 6 + 5 + 4 = 39$ , а $3 + 9 = 12$ , а $1 + 2 = 3$ . Дошли до 3, значит, всё число даёт остаток 3 при делении на 9 и делится на 3, но не на 9. Эту финальную цифру (если её не 9, а 0) называют цифровым корнем числа.

🤔 А знаешь ли ты? Этот трюк с суммой цифр когда-то использовали бухгалтеры для проверки расчётов. Приём назывался «выбрасывание девяток». Если в столбике сложения сумма цифр результата не сходится с тем, что должно получиться, значит, где-то закралась ошибка. Дешёвый и быстрый детектор опечаток без всякого компьютера.

Признак на 11: чередуем плюс и минус

Раз уж мы поняли механику, разберём признак, который в школе почти не проходят, а на олимпиадах он выручает. Он про число 11.

Секрет в том, что рядом с 11 стоят «почти делящиеся» числа: $10 = 11 - 1$ , $100 = 99 + 1$ , $1000 = 1001 - 1$ . То есть чётные степени десятки ( $100, 10000, \dots$ ) дают остаток $+ 1$ при делении на 11, а нечётные ( $10, 1000, \dots$ ) — остаток $- 1$ .

Распишем, например, 2728:

2728 = 2 \cdot 1000 + 7 \cdot 100 + 2 \cdot 10 + 8.

Заменим $1000 = 1001 - 1$ , $100 = 99 + 1$ , $10 = 11 - 1$ :

2728 = 2 \cdot 1001 + 7 \cdot 99 + 2 \cdot 11 + остаётся это (- 2 + 7 - 2 + 8) .

Всё, что с множителями 1001, 99, 11, делится на 11. А в остатке — знакочередующаяся сумма цифр, если идти справа налево: $8 - 2 + 7 - 2 = 11$ . Она делится на 11, значит, и 2728 делится ( $2728 = 11 \cdot 248$ ).

📌 Признак делимости на 11: число делится на 11, если на 11 делится знакочередующаяся сумма его цифр (плюс, минус, плюс, минус…). Ноль тоже считается делящимся.

Остатки

Когда число не делится нацело, остаётся остаток. Запись: «33 даёт остаток 3 при делении на 5», потому что $33 = 5 \cdot 6 + 3$ . Остаток всегда неотрицательный и строго меньше делителя. При делении на 5 остаток может быть только 0, 1, 2, 3 или 4 — пять вариантов, ни больше ни меньше.

Значит, все целые числа при делении на 5 распадаются на пять «семей» по остатку:

{\dots, 0, 5, 10, \dots}, {\dots, 1, 6, 11, \dots}, {\dots, 2, 7, 12, \dots}, {\dots, 3, 8, \dots}, {\dots, 4, 9, \dots} .

Внутри одной семьи числа ведут себя одинаково: в этом вся сила остатков.

Математики придумали удобную запись — сравнение по модулю. Вместо «17 и 2 дают одинаковый остаток при делении на 5» пишут:

17 \equiv 2 (mod 5) .

Читается: «17 сравнимо с 2 по модулю 5». Значок $\equiv$ похож на равно, но с тремя чёрточками — это не «равно», а «в одной семье по остаткам».

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

Почему это работает? Докажем. Запишем два числа через их остатки при делении на $n$ :

a = k_{1} n + r_{1}, b = k_{2} n + r_{2},

где $r_{1}, r_{2}$ — остатки, а $k_{1}, k_{2}$ — целые числа.

Сумма. Сложим:

a + b = (k_{1} n + r_{1}) + (k_{2} n + r_{2}) = целое (k_{1} + k_{2}) n + (r_{1} + r_{2}) .

Первое слагаемое делится на $n$ , поэтому остаток у суммы $a + b$ такой же, как у $r_{1} + r_{2}$ .

Произведение. Перемножим (раскрывая скобки):

a \cdot b = (k_{1} n + r_{1}) (k_{2} n + r_{2}) = n целое (k_{1} k_{2} n + k_{1} r_{2} + r_{1} k_{2}) + r_{1} r_{2} .

Первое слагаемое опять делится на $n$ , поэтому остаток у произведения $a \cdot b$ такой же, как у $r_{1} r_{2}$ . Значит, чтобы найти остаток суммы или произведения, и правда достаточно работать с одними остатками. Что и требовалось доказать.

Пример. Какой остаток даёт $23 \cdot 14$ при делении на 5? Остаток 23 при делении на 5 равен 3, остаток 14 равен 4. Перемножаем остатки: $3 \cdot 4 = 12$ , его остаток при делении на 5 равен 2. Значит, и $23 \cdot 14$ даёт остаток 2. (Проверка: $23 \cdot 14 = 322 = 5 \cdot 64 + 2$ . Верно!)

На языке сравнений это выглядит так коротко:

23 \cdot 14 \equiv 3 \cdot 4 = 12 \equiv 2 (mod 5) .

Это сильно упрощает жизнь: вместо огромных чисел можно работать с маленькими остатками.

💡 Отрицательные остатки — тайное оружие. Иногда вместо остатка удобно брать «остаток со знаком минус». Например, по модулю 5 число 4 можно заменить на $- 1$ , ведь $4 = 5 - 1$ , то есть $4 \equiv - 1 (mod 5)$ . Тогда $4^{100} \equiv (- 1)^{100} = 1 (mod 5)$ , и никакой возни! Всегда полезно спросить себя: не близок ли мой остаток к делителю? Если да, считай через минус.

💡 Лайфхак: часовая арифметика. Остатки — это как циферблат. На часах после 12 идёт снова 1, а не 13: часы считают по модулю 12. Если сейчас 10 часов и пройдёт 5 часов, будет не 15, а 3: ты просто взял остаток. Каждый раз, когда смотришь на часы, ты пользуешься остатками, даже не зная этого.

Чётность — это остаток по модулю 2

Отдельно стоит сказать про чётность, потому что это самый частый и самый простой случай остатков: при делении на 2 остаток бывает только 0 (чётные) или 1 (нечётные). Всего две семьи!

Правила сложения тут особенно наглядны:

чётное + чётное = чётное $(0 + 0 = 0)$
нечётное + нечётное = чётное $(1 + 1 = 2 \equiv 0)$
чётное + нечётное = нечётное $(0 + 1 = 1)$

📌 Запомни главное про чётность: сумма меняет чётность только тогда, когда добавляешь нечётное число. А сумма нескольких чисел нечётна тогда и только тогда, когда среди них нечётное количество нечётных слагаемых. Этот факт в одиночку решает целые олимпиадные задачи. Увидишь в примере 7.

Последняя цифра степени

«Последняя цифра» — это остаток при делении на 10. А раз остатки перемножаются (мы это только что доказали), последняя цифра степени зависит только от последней цифры предыдущей степени, а не от всего огромного числа.

Проследим за степенями семёрки, глядя только на последнюю цифру:

7^{1} \to 7, 7^{2} \to 9, 7^{3} \to 3, 7^{4} \to 1, 7^{5} \to 7, \dots

Как это считается? Каждую следующую цифру берём как последнюю цифру произведения «предыдущая цифра $\times 7$ ». Например, у $7^{3}$ было 9, умножаем: $9 \cdot 7 = 63$ → цифра 3. Дальше $3 \cdot 7 = 21$ → 1, потом $1 \cdot 7 = 7$ → снова 7.

Вот и разгадка цикла: на пятом шаге последняя цифра снова стала 7, такой же, как в самом начале. А раз следующая цифра зависит только от текущей, дальше всё повторится точь-в-точь: 7, 9, 3, 1, 7, 9, 3, 1, … — цикл длины 4. И так у любого числа: разных последних цифр всего 10 штук, поэтому какая-то рано или поздно повторится, и с этого места последовательность зацикливается. Это мы используем в примерах: приём очень полезный.

⚠️ Частая ошибка! Когда делишь показатель на длину цикла, будь внимателен с остатком. Остаток 1 → первая цифра цикла, остаток 2 → вторая, и так далее. А вот остаток 0 означает не «первая», а последняя цифра цикла (ты дошёл ровно до конца круга). Многие тут спотыкаются и берут не ту цифру.

✍️ Разбор примеров

Пример 1. Вместо звёздочки в числе 5*2 поставь цифру так, чтобы число делилось на 9. Все ли варианты ты нашёл?

⏱ Попробуй сам прямо сейчас: какой признак делимости на 9 ты знаешь? Запиши сумму цифр через звёздочку, потом читай дальше.

Как рассуждаем. По признаку делимости на 9 нам нужна сумма цифр, делящаяся на 9. Сумма цифр: $5 + * + 2 = 7 + *$ . Нужно, чтобы $7 + *$ делилось на 9. Цифра $*$ — от 0 до 9, значит $7 + *$ меняется от 7 до 16. В этом промежутке на 9 делится только число 9. Значит, $7 + * = 9$ , откуда $* = 2$ . Число 522.

Проверим: $5 + 2 + 2 = 9$ , делится на 9. И правда, $522 = 9 \cdot 58$ .

Ответ: $* = 2$ , число 522 (единственный вариант).

Пример 2. Докажи, что число $1 0^{n} - 1$ (то есть единица с $n$ нулями минус один) всегда делится на 9.

Как рассуждаем. Посмотрим на остаток десятки при делении на 9: $10 = 9 + 1$ , то есть $10 \equiv 1 (mod 9)$ . А раз остатки можно перемножать (значит, и возводить в степень — это то же самое умножение), получаем:

1 0^{n} \equiv 1^{n} = 1 (mod 9) .

Отсюда $1 0^{n} - 1 \equiv 1 - 1 = 0 (mod 9)$ , то есть $1 0^{n} - 1$ делится на 9. Всё доказательство уместилось в одну строчку: вот зачем нужны остатки!

Ответ: доказано ( $10 \equiv 1 (mod 9) \Rightarrow 1 0^{n} \equiv 1 \Rightarrow 1 0^{n} - 1 \equiv 0$ ).

Пример 3. Какой цифрой оканчивается число $7^{100}$ ?

Как рассуждаем. Возводить 7 в сотую степень руками — безумие. Но последняя цифра — это остаток при делении на 10, а он зависит только от последних цифр. Выпишем последние цифры степеней семёрки и поймаем закономерность:

$7^{1} = 7$ → последняя цифра 7
$7^{2} = 49$ → 9
$7^{3} = \dots 3$ ( $9 \cdot 7 = 63$ ) → 3
$7^{4} = \dots 1$ ( $3 \cdot 7 = 21$ ) → 1
$7^{5} = \dots 7$ ( $1 \cdot 7 = 7$ ) → 7, и всё повторяется!

Цикл: 7, 9, 3, 1, длина цикла 4. Дальше всё идёт по кругу. Чтобы узнать, где в цикле стоит $7^{100}$ , делим показатель 100 на длину цикла 4: $100 = 4 \cdot 25$ , остаток 0. Остаток 0 означает, что мы попадаем в конец цикла, на 4-ю позицию, где стоит цифра 1.

(Проверь на маленьком: $7^{4}$ оканчивается на 1, $7^{8}$ тоже на 1; везде, где показатель кратен 4, последняя цифра 1.)

Ответ: 1.

Пример 4. Найди остаток от деления $2^{2025}$ на 3.

Как рассуждаем. Та же идея, что и с последней цифрой, только теперь делим не на 10, а на 3. Работаем с остатками по модулю 3. Остаток числа 2 при делении на 3 равен 2 (а можно сказать «равен $- 1$ », это то же самое, что 2, ведь $- 1 + 3 = 2$ ; иногда удобнее считать с $- 1$ ). Посмотрим на остатки степеней двойки при делении на 3:

$2^{1}$ → остаток 2
$2^{2} = 4$ → остаток 1
$2^{3} = 8$ → остаток 2
$2^{4} = 16$ → остаток 1, …

Цикл: 2, 1, длина 2. Чётные степени дают остаток 1, нечётные — остаток 2. Показатель 2025 нечётный, значит остаток 2.

(Через $- 1$ ещё короче: $2 \equiv - 1$ , значит $2^{2025} \equiv (- 1)^{2025} = - 1 \equiv 2 (mod 3)$ .)

Ответ: 2.

Пример 5. Докажи, что квадрат любого целого числа при делении на 4 даёт остаток только 0 или 1.

Как рассуждаем. «Любое целое число» — это бесконечно много чисел, перебрать нельзя. Но их можно разбить на два типа: чётные и нечётные. Разберём оба случая, и этого хватит на всех.

Если число чётное, его можно записать как $2 k$ . Тогда квадрат: $(2 k)^{2} = 4 k^{2}$ . Это явно делится на 4: остаток 0.
Если число нечётное, его можно записать как $2 k + 1$ . Тогда квадрат: $(2 k + 1)^{2} = 4 k^{2} + 4 k + 1 = 4 (k^{2} + k) + 1$ . Первая часть делится на 4, остаётся остаток 1.

Других случаев нет. Значит, квадрат всегда даёт остаток 0 или 1 при делении на 4.

Ответ: доказано (чётное → 0, нечётное → 1; остатков 2 или 3 у квадратов не бывает).

Пример 6. Может ли сумма квадратов трёх целых чисел давать остаток 3 при делении на 4? (Например, может ли она равняться числу вида $4 m + 3$ ?)

Как рассуждаем. У нас уже есть готовый инструмент из примера 5: каждый квадрат при делении на 4 даёт остаток 0 или 1. У нас три квадрата, их остатки — каждый из ${0, 1}$ . Остаток суммы равен сумме остатков (взятой по модулю 4). Сумма трёх чисел, каждое из которых 0 или 1, может быть: 0, 1, 2 или 3, в зависимости от того, сколько среди них единиц.

Стоп, получается, остаток 3 возможен (если все три квадрата дают остаток 1)! Например, $1^{2} + 1^{2} + 1^{2} = 3$ , и правда даёт остаток 3 при делении на 4. Так что сумма трёх квадратов остаток 3 давать может.

(А вот для двух квадратов остаток 3 невозможен: $0 + 0 = 0$ , $0 + 1 = 1$ , $1 + 1 = 2$ ; тройки не выходит. Это и есть знаменитый трюк: сумма двух квадратов никогда не даёт остаток 3 по модулю 4.)

Ответ: для трёх квадратов — да, может (например, $1 + 1 + 1 = 3$ ). А вот сумма двух квадратов остаток 3 по модулю 4 дать не может.

Пример 7. На доске написаны числа $1, 2, 3, \dots, 2025$ . За один ход можно стереть любые два числа и вместо них написать их разность (модуль разности). Так продолжают, пока не останется одно число. Может ли это последнее число быть нулём?

⏱ Попробуй сам: что не меняется при таком ходе? Ищи «невидимую величину», которая остаётся постоянной.

Как рассуждаем. Тут не помогут признаки делимости, зато поможет чётность. Ключевая идея: следим за чётностью суммы всех чисел на доске. Когда мы стираем $a$ и $b$ и пишем $∣ a - b ∣$ , сумма меняется на величину $(a + b) - ∣ a - b ∣$ . Посчитаем эту величину: если $a \geq b$ , то $∣ a - b ∣ = a - b$ , и изменение равно $(a + b) - (a - b) = 2 b$ , чётное число! Значит, при любом ходе сумма меняется на чётное, а её чётность НЕ меняется.

Теперь найдём чётность начальной суммы:

1 + 2 + \dots + 2025 = \frac{2025 \cdot 2026}{2} = 2025 \cdot 1013.

Это произведение двух нечётных чисел (2025 и 1013), значит, оно нечётное. Итоговая сумма (одно оставшееся число) обязана быть тоже нечётной. А ноль — число чётное. Противоречие!

Ответ: нет, нулём остаться не может: сумма всё время остаётся нечётной, а 0 чётно.

Пример 8. Проверь, делится ли число 918082 на 11, не выполняя деления.

Как рассуждаем. Применяем свежий признак делимости на 11 — знакочередующуюся сумму цифр, справа налево. Цифры числа: 9, 1, 8, 0, 8, 2. Идём с конца (с последней цифры) и чередуем знаки:

2 - 8 + 0 - 8 + 1 - 9 = - 22.

Число $- 22$ делится на 11 ( $- 22 = 11 \cdot (- 2)$ ). Значит, и 918082 делится на 11.

Проверка: $918082 = 11 \cdot 83462$ . Совпало!

Ответ: да, делится (знакочередующаяся сумма цифр равна $- 22$ , кратна 11).

💡 Запомни главное

Когда задача про «может ли / делится ли» с большими числами, переходи к остаткам. Маленькие остатки заменяют огромные числа, а степени дают циклы.

На 2, 5, 10 — смотри последнюю цифру; на 4 — две последние; на 3 и 9 — сумму цифр; на 11 — знакочередующуюся сумму цифр.
Остатки можно складывать и умножать, а потом снова брать остаток. Запись $a \equiv b (mod m)$ означает «одинаковый остаток при делении на $m$ ».
Отрицательный остаток (например, $4 \equiv - 1 (mod 5)$ ) часто короче обычного.
Последняя цифра степени = остаток по модулю 10, и она повторяется циклом. Дели показатель на длину цикла и смотри на остаток (0 → последняя цифра цикла!).
Чётность — это остаток по модулю 2. Ищи величину, чья чётность не меняется, и задача решена.
Квадраты по модулю 4 дают только 0 или 1 — мощный инструмент доказательства невозможности.

📝 Домашнее задание

Не выполняя деления, определи, на какие из чисел 2, 3, 4, 5, 9, 10 делится число 7380.
Подбери все цифры, которые можно поставить вместо звёздочки в числе 4*6, чтобы оно делилось на 3.
Число записано ста единицами подряд: 111…1 (сто единиц). Делится ли оно на 3? А на 9?
Какой цифрой оканчивается число $3^{2025}$ ?
Найди остаток от деления $5^{0} + 5^{1} + 5^{2} + \dots + 5^{10}$ на 4.
Докажи, что среди любых трёх подряд идущих натуральных чисел ровно одно делится на 3.
Докажи, что любое число, записанное цифрами 1, 2, 3, 4, 5, 6, 7, 8 (каждая по одному разу, в любом порядке), делится на 9.
⭐ Докажи, что число вида 11…1 (n единиц) никогда не является точным квадратом при n ≥ 2. (Подсказка: какие остатки бывают у квадратов по модулю 4?)