Числа и их свойства: «может ли», оценка плюс пример 🔢

Последнее задание профильного ЕГЭ выглядит обманчиво просто. Никаких интегралов, логарифмов и параметров — только натуральные числа, суммы, средние и делимость. Условие понятно шестикласснику: «На доске написано несколько различных натуральных чисел, их сумма равна 100. Может ли их быть 14?» И тем не менее задание 20 — одно из самых низко решаемых на экзамене. Причина не в сложности вычислений, а в том, что здесь нужно доказывать, а доказательствам в школе учат мало.

Хорошая новость: задание 20 состоит из пунктов а), б), в), и каждый даёт свои баллы (до 4 первичных баллов за всё задание). Пункты а) и б) часто решаются одним примером или одним наблюдением про чётность или остаток. Даже без пункта в) можно уверенно забрать 1–2 балла. А если освоить схему «оценка плюс пример», то и пункт в) перестаёт быть лотереей.

Эта тема неожиданно близка к IT. Остатки от деления — основа хэш-таблиц, контрольных сумм банковских карт и криптографии. Когда ты вызываешь hash(key) % size или pow(a, b, m) в Python — ты работаешь с той же арифметикой остатков, что и в задании 20.

Ты узнаешь:

🎯 Как работать с остатками и сравнениями по модулю и почему это самый быстрый способ доказать «не может»

🎯 Как отвечать на вопросы «может ли»: когда достаточно примера, а когда нужно доказательство невозможности

🎯 Что такое схема «оценка плюс пример» и почему без любой из двух частей пункт в) не засчитывают

🎯 Как оформлять решение, чтобы эксперт поставил полный балл

История: откуда это взялось? 📜

Задачи на остатки старше алгебры. В китайском трактате «Математика Сунь-цзы» (примерно III–V век) есть знаменитая задача: «Есть неизвестное число предметов. Если считать тройками — остаётся 2, пятёрками — остаётся 3, семёрками — остаётся 2. Сколько предметов?» Её решение — то, что сегодня называют китайской теоремой об остатках. Задачу решали для календарных расчётов: нужно было найти момент, когда совпадают несколько циклов разной длины.

В XVII веке Пьер Ферма, юрист из Тулузы и математик-любитель, сформулировал множество утверждений о делимости. Одно из них, малая теорема Ферма, гласит: если $p$ — простое, то $a^p - a$ делится на $p$ при любом целом $a$. Доказательства Ферма, по своему обыкновению, не опубликовал — его дал Леонард Эйлер в 1736 году. А в 1801 году 24-летний Карл Фридрих Гаусс в книге «Арифметические исследования» ввёл обозначение $a \equiv b \pmod m$ и превратил работу с остатками в исчисление: остатки можно складывать, умножать и возводить в степень, как обычные числа.

Почти двести лет теория чисел считалась самой «бесполезной» частью математики. Английский математик Годфри Харди даже гордился тем, что его работы никогда не найдут военного применения. Всё изменилось в 1977 году, когда Ривест, Шамир и Адлеман опубликовали алгоритм RSA. Он построен на теореме Эйлера (обобщении малой теоремы Ферма) и возведении в степень по модулю. С тех пор арифметика остатков защищает каждое HTTPS-соединение, банковские переводы и мессенджеры.

Блок 1: Делимость, остатки и сравнения по модулю

Давай разберёмся с интуицией

Любое целое число $n$ при делении на натуральное $m$ даёт остаток $r$ от $0$ до $m - 1$: $n = mq + r$. Главная идея: во многих вопросах важно не само число, а только его остаток. Чётность — это остаток при делении на $2$. Последняя цифра — остаток при делении на $10$. Признак делимости на $9$ — утверждение о том, что число и сумма его цифр дают одинаковый остаток при делении на $9$.

Остатки удобно записывать сравнениями:

Определение: Целые числа $a$ и $b$ сравнимы по модулю $m$ (пишут $a \equiv b \pmod m$), если они дают одинаковые остатки при делении на $m$, то есть $a - b$ делится на $m$.

Свойства: если $a \equiv b$ и $c \equiv d \pmod m$, то

• $a + c \equiv b + d \pmod m$;
• $a \cdot c \equiv b \cdot d \pmod m$;
• $a^k \equiv b^k \pmod m$ для любого натурального $k$.

Это значит, что в любом выражении из сумм, произведений и степеней можно заменить каждое число его остатком — и остаток результата не изменится. Огромные числа вроде $3^{2026}$ сразу становятся ручными.

Полезные факты, которые стоит знать наизусть:

• квадрат целого числа при делении на $3$ даёт остаток $0$ или $1$;
• при делении на $4$ — остаток $0$ или $1$;
• при делении на $8$ — остаток $0$, $1$ или $4$;
• при делении на $9$ — остаток $0$, $1$, $4$ или $7$;
• из $k$ последовательных целых чисел ровно одно делится на $k$; поэтому произведение $k$ последовательных чисел делится на $k$, а произведение двух последовательных — на $2$.

Аналогия

Остаток по модулю $m$ — это положение стрелки на циферблате с $m$ делениями. Часы не знают, сколько полных кругов прошла стрелка, но точно знают, где она сейчас. Прибавить $5$ часов к $10$ часам — получится $3$ часа, и неважно, какой это был день. Вся арифметика остатков — это арифметика циферблата. В программировании то же самое делает операция %: индекс в кольцевом буфере, день недели по номеру дня, номер ячейки в хэш-таблице.

Пример 1 (лёгкий): остаток огромной степени

Найди остаток от деления $3^{50}$ на $8$.

Решение:

Шаг 1. Ищем степень тройки с «удобным» остатком: $3^2 = 9 \equiv 1 \pmod 8$.

Шаг 2. Тогда $3^{50} = (3^2)^{25} \equiv 1^{25} = 1 \pmod 8$.

Проверим наш ответ: $3^4 = 81 = 80 + 1 \equiv 1 \pmod 8$ — закономерность подтверждается.

Ответ: $1$.

Пример 2 (средний): делимость при любом $n$

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

Решение:

$30 = 2 \cdot 3 \cdot 5$, и эти числа попарно взаимно просты. Достаточно доказать делимость на каждое.

Шаг 1. Разложим: $n^5 - n = n(n^4 - 1) = n(n^2 - 1)(n^2 + 1) = (n - 1)n(n + 1)(n^2 + 1)$.

Шаг 2. На $2$ и $3$. Среди трёх последовательных чисел $n - 1$, $n$, $n + 1$ есть чётное и есть кратное трём. Значит, произведение делится на $6$.

Шаг 3. На $5$. Разберём остатки $n$ при делении на $5$:

• $n \equiv 0$: делится множитель $n$;
• $n \equiv 1$: делится $n - 1$;
• $n \equiv 4$: делится $n + 1$;
• $n \equiv 2$: $n^2 + 1 \equiv 4 + 1 = 5 \equiv 0$;
• $n \equiv 3$: $n^2 + 1 \equiv 9 + 1 = 10 \equiv 0$.

Во всех случаях один из множителей делится на $5$.

Ответ: делится на $2$, $3$ и $5$, а значит, на $30$. Что и требовалось доказать.

Это частный случай малой теоремы Ферма: $n^5 - n$ делится на $5$, потому что $5$ — простое.

Пример 3 (сложный): доказательство «не может» через остатки

Может ли сумма квадратов трёх целых чисел равняться $2023$?

Решение:

Шаг 1. Идея. Для доказательства невозможности нужен модуль, по которому левая часть «не умеет» давать остаток правой. Для квадратов лучший кандидат — $8$.

Шаг 2. Остатки квадратов по модулю 8. Проверим все остатки $n$:

Квадрат даёт остаток $0$, $1$ или $4$.

Шаг 3. Суммы трёх остатков из набора $\{0, 1, 4\}$ по модулю $8$ — разберём по шагам все десять комбинаций:

Получаются остатки $0, 1, 2, 3, 4, 5, 6$, но никогда $7$.

Шаг 4. $2023 = 8 \cdot 252 + 7$, то есть $2023 \equiv 7 \pmod 8$. Такой остаток сумма трёх квадратов дать не может.

Ответ: не может.

Это знаменитый результат: числа вида $8k + 7$ не представляются суммой трёх квадратов. Более того, по теореме Лежандра — Гаусса натуральное число является суммой трёх квадратов тогда и только тогда, когда оно не имеет вида $4^m(8k + 7)$.

Почему это важно

В задании 20 фраза «докажите, что не может» почти всегда решается одним из трёх приёмов: чётность, остаток по удачно выбранному модулю, оценка (сумма слишком большая или слишком маленькая). Первые два — это Блок 1. Навык «угадать модуль» тренируется: для квадратов пробуй $3$, $4$, $8$, $9$; для сумм цифр — $9$; для последних цифр — $10$ и $100$; для степеней двойки — $3$ и $7$.

Блок 2: Суммы, средние и схема «оценка плюс пример»

Давай разберёмся с интуицией

Пункт в) задания 20 почти всегда звучит так: «Найдите наибольшее (наименьшее) возможное значение…». Ответ — одно число, но чтобы получить балл, нужно сделать две вещи:

1. Оценка: доказать, что больше (меньше) этого числа быть не может. Это рассуждение «для любого набора».
2. Пример: предъявить конкретный набор, на котором это значение достигается.

Без оценки непонятно, не бывает ли больше. Без примера непонятно, достигается ли граница вообще — может, настоящий ответ меньше.

Определение (схема «оценка плюс пример»): Чтобы доказать, что наибольшее значение величины $S$ равно $M$, нужно:

• оценка: доказать, что $S \le M$ при любом допустимом наборе;
• пример: указать допустимый набор, для которого $S = M$.

Для наименьшего значения — аналогично, с неравенством $S \ge M$.

Главный инструмент оценки для сумм различных натуральных чисел: если $k$ чисел различны и натуральны, их сумма не меньше $1 + 2 + \ldots + k = \frac{k(k+1)}{2}$. Если к тому же все числа не больше $M$, сумма не больше $M + (M - 1) + \ldots + (M - k + 1)$.

Для средних: среднее арифметическое $k$ чисел равно $s$ $\Leftrightarrow$ сумма равна $ks$. Почти любая задача про средние сводится к задаче про суммы.

Аналогия

Представь, что ты утверждаешь: «Мой рекорд в игре — 310 очков, больше набрать невозможно». Чтобы тебе поверили, нужны две вещи. Скриншот, где у тебя 310 — это пример. И объяснение, почему 311 невозможно по правилам игры, — это оценка. Одного скриншота мало (вдруг кто-то наберёт больше), одного объяснения мало (вдруг и 310 недостижимо). Так же и в задании 20.

Пример 1 (лёгкий): наибольшее число в наборе

Сумма $20$ различных натуральных чисел равна $500$. Какое наибольшее значение может принимать наибольшее из них?

Решение:

Оценка. Пусть наибольшее число $M$. Остальные $19$ чисел различны и натуральны, значит, их сумма не меньше $1 + 2 + \ldots + 19 = \frac{19 \cdot 20}{2} = 190$. Тогда $M \le 500 - 190 = 310$.

Пример. Числа $1, 2, \ldots, 19, 310$: все различны, сумма $190 + 310 = 500$.

Ответ: $310$.

Пример 2 (средний): наибольшее количество чисел

Сумма нескольких различных натуральных чисел равна $50$. Какое наибольшее количество чисел может быть в наборе?

Решение:

Оценка. Если чисел $k$, их сумма не меньше $\frac{k(k+1)}{2}$. При $k = 10$ это $55 > 50$ — невозможно. При больших $k$ — тем более. Значит, $k \le 9$.

Пример. $k = 9$: $1 + 2 + \ldots + 8 = 36$, добавим $14$: набор $1, 2, \ldots, 8, 14$, сумма $50$, все числа различны.

Ответ: $9$.

Пример 3 (сложный): полноценное задание в формате а–в

На доске написано $15$ натуральных чисел (не обязательно различных), каждое не больше $20$. Их среднее арифметическое равно $12$.

а) Может ли ровно $7$ из этих чисел быть меньше $5$?

б) Может ли $8$ из этих чисел быть меньше $5$?

в) Пусть ровно $7$ чисел меньше $5$. Найди наименьшее возможное значение наибольшего из написанных чисел.

Решение:

Сумма всех чисел: $15 \cdot 12 = 180$.

а) Попробуем сделать малые числа как можно больше (по $4$), чтобы остальным осталось поменьше. $7 \cdot 4 = 28$, остальным $8$ числам нужно $180 - 28 = 152 = 8 \cdot 19$. Набор: семь четвёрок и восемь чисел $19$. Все не больше $20$, ровно $7$ меньше $5$, сумма $180$. Может.

б) Пусть $8$ чисел меньше $5$. Каждое из них не больше $4$, их сумма не больше $32$. Оставшиеся $7$ чисел не больше $20$, их сумма не больше $140$. Общая сумма не больше $172 < 180$. Противоречие. Не может.

в) Оценка. Семь чисел меньше $5$ дают в сумме не больше $28$. Значит, сумма остальных восьми не меньше $180 - 28 = 152$. Наибольшее из восьми чисел не меньше их среднего: $\frac{152}{8} = 19$. Итак, наибольшее число $\ge 19$.

Пример — набор из пункта а): наибольшее число равно $19$.

Ответ: а) да; б) нет; в) $19$.

Посмотри, как пункты связаны: пример из а) пригодился в в), а идея «малые числа не больше 4» — и в б), и в в). Так устроено почти каждое задание 20: пункты — это лестница к последнему вопросу.

Почему это важно

По критериям ФИПИ пункт в) без оценки или без примера засчитывается не полностью. При этом каждый из пунктов а) и б) приносит свой балл. Схема «оценка плюс пример» — это не только ЕГЭ. Любая задача оптимизации в программировании решается так же: алгоритм даёт пример (конкретное решение), а нижняя граница доказывает, что лучше не бывает. Когда говорят, что сортировка сравнениями требует порядка $n\log n$ операций, — это оценка. Когда показывают сортировку слиянием с такой сложностью — это пример.

Блок 3: Как оформлять задание 20 и доказывать невозможность

Давай разберёмся с интуицией

Вопрос «может ли…» имеет два возможных ответа, и оформляются они по-разному:

• «Да, может» — достаточно одного примера. Пример должен быть конкретным (числа выписаны явно) и проверенным: покажи, что все условия выполнены.
• «Нет, не может» — нужно доказательство для всех случаев. Перебор нескольких неудачных попыток — не доказательство.

Самые частые способы доказать невозможность:

1. Чётность / остаток: левая часть всегда имеет один остаток, правая — другой.
2. Оценка: даже в самом «выгодном» случае сумма слишком мала или слишком велика.
3. От противного: предположи, что можно, и выведи противоречие.
4. Разбиение на пары или группы: «из каждой пары можно взять не больше одного».

Определение (структура решения на полный балл):

• а) Ответ «да» — конкретный пример и проверка условий. Ответ «нет» — доказательство.
• б) То же самое.
• в) Ответ, оценка (доказательство, что лучше нельзя) и пример (достижение).
• В конце — строка «Ответ: а) …; б) …; в) …».

Аналогия

Представь, что ты тестировщик. Чтобы доказать, что в программе есть баг, достаточно одного воспроизводимого сценария — это пример. Чтобы доказать, что бага нет, никакое количество удачных запусков не поможет — нужно формальное рассуждение, покрывающее все входные данные. Ответ «нет» в задании 20 — это верификация, ответ «да» — это найденный баг.

Пример 1 (лёгкий): невозможность через разложение

Можно ли представить число $64$ в виде суммы нескольких (не менее двух) последовательных натуральных чисел?

Решение:

Пусть $64 = a + (a + 1) + \ldots + (a + n - 1)$, $n \ge 2$, $a \ge 1$. Сумма арифметической прогрессии:

Множители $n$ и $2a + n - 1$ имеют разную чётность (их сумма $2a + 2n - 1$ нечётна). Значит, один из них нечётный. Но единственный нечётный делитель $2^7$ — это $1$. При этом $n \ge 2$ и $2a + n - 1 \ge 2 + 2 - 1 = 3$ — оба больше $1$. Противоречие.

Ответ: нельзя.

Общий факт: степень двойки никогда не является суммой двух и более последовательных натуральных чисел.

Пример 2 (средний): система остатков

Сколько натуральных чисел от $1$ до $100$ дают остаток $1$ при делении на $3$ и остаток $2$ при делении на $4$?

Решение:

Шаг 1. Найдём наименьшее такое число перебором по остатку $2$ mod $4$: $2, 6, 10, \ldots$ Остатки при делении на $3$: $2, 0, 1$. Подходит $10$.

Шаг 2. Числа $3$ и $4$ взаимно просты, поэтому условие равносильно $n \equiv 10 \pmod{12}$ (китайская теорема об остатках: решения повторяются с периодом $3 \cdot 4 = 12$).

Шаг 3. $n = 10 + 12t \le 100 \Rightarrow t \le 7{,}5$, $t = 0, 1, \ldots, 7$ — восемь чисел: $10, 22, 34, 46, 58, 70, 82, 94$.

Ответ: $8$.

Пример 3 (сложный): образец оформления а–в

Числа $1, 2, 3, \ldots, 12$ разбивают на несколько групп (в каждой хотя бы одно число) так, чтобы суммы чисел во всех группах были равны.

а) Можно ли разбить их на две группы?

б) Можно ли разбить их на четыре группы?

в) На какое наибольшее число групп можно их разбить?

Решение (так и пиши в бланке):

Сумма всех чисел: $1 + 2 + \ldots + 12 = 78$.

а) Каждая группа должна иметь сумму $39$. Пример: $\{12, 11, 10, 6\}$ (сумма $39$) и $\{1, 2, 3, 4, 5, 7, 8, 9\}$ (сумма $39$). Можно.

б) Сумма каждой группы равна $\frac{78}{4} = 19{,}5$ — не целое число, а сумма натуральных чисел целая. Нельзя.

в) Оценка. Пусть групп $k$, сумма каждой $\frac{78}{k}$. Число $12$ входит в какую-то группу, значит, сумма этой группы не меньше $12$: $\frac{78}{k} \ge 12 \Rightarrow k \le 6{,}5$, то есть $k \le 6$.

Пример для $k = 6$ (сумма группы $13$): $\{12, 1\}$, $\{11, 2\}$, $\{10, 3\}$, $\{9, 4\}$, $\{8, 5\}$, $\{7, 6\}$.

Ответ: а) да; б) нет; в) $6$.

Проверь, что есть всё необходимое: пример в а) с проверкой сумм, доказательство в б), в в) — и оценка, и пример. Это решение на полный балл.

Почему это важно

Эксперт не ищет «правильное число» — он ищет обоснование. Ответ «в) 6» без оценки и примера принесёт не больше, чем ноль баллов за этот пункт. Зато аккуратно оформленные а) и б) — это гарантированные баллы, даже если в) не получился. Поэтому стратегия на экзамене: сначала полностью решить и оформить а) и б), потом браться за в).

И ещё один мостик в IT. Хэш-функция $h(k) = k \bmod m$ раскладывает ключи по $m$ «корзинам» — это разбиение на группы по остаткам. Если все ключи кратны $4$, а $m = 32$, то заняты только корзины $0, 4, 8, \ldots, 28$ — восемь из тридцати двух. Хорошие хэш-функции выбирают так, чтобы такие перекосы не возникали: обычно размер таблицы берут простым числом или умножают ключ на число, взаимно простое с $m$. Задание 29 практики — ровно об этом.

Практика: 30 заданий

А теперь попробуй сам. В заданиях «может ли» не забывай: «да» — пример, «нет» — доказательство.

Базовые (задания 1–10)

Задание 1: Найди остаток от деления $2^{100}$ на $7$.

Задание 2: Может ли сумма пяти нечётных чисел равняться $100$?

Задание 3: Найди последнюю цифру числа $3^{2026}$.

Задание 4: Докажи, что $n^3 - n$ делится на $6$ при любом натуральном $n$.

Задание 5: Может ли сумма квадратов двух целых чисел равняться $2027$?

Задание 6: Десятизначное число записано пятью единицами и пятью двойками (в каком-то порядке). Может ли оно быть точным квадратом?

Задание 7: Сколько натуральных чисел от $1$ до $1000$ делятся на $6$, но не делятся на $4$?

Задание 8: Среднее арифметическое пяти чисел равно $12$. Когда к ним добавили ещё одно число, среднее стало равно $13$. Какое число добавили?

Задание 9: Число $n$ при делении на $5$ даёт остаток $3$. Какой остаток при делении на $5$ даёт $n^2 + 2n$?

Задание 10: Может ли сумма трёх последовательных натуральных чисел равняться $2026$?

Средние (задания 11–20)

Задание 11: Найди наименьшее натуральное число, которое при делении на $3$ даёт остаток $2$, на $4$ — остаток $3$, на $5$ — остаток $4$.

Задание 12: На доске $10$ различных натуральных чисел, их среднее арифметическое равно $12$. Какое наибольшее значение может иметь наибольшее из них?

Задание 13: На доске $10$ различных натуральных чисел, их среднее арифметическое равно $12$. Какое наименьшее значение может иметь наибольшее из них?

Задание 14: Может ли число $n^2 + n + 1$ делиться на $5$ при каком-нибудь натуральном $n$?

Задание 15: Найди наименьшее натуральное число, которое делится на $5$ и сумма цифр которого равна $25$.

Задание 16: Сколько существует пар натуральных чисел $(x; y)$, для которых $x^2 - y^2 = 60$?

Задание 17: Набор состоит из $7$ различных натуральных чисел, их среднее арифметическое равно $10$. Какое наибольшее количество чисел набора может быть больше $12$?

Задание 18: Найди все натуральные $n$, при которых $\dfrac{n^2 + 7}{n + 1}$ — целое число.

Задание 19: Может ли число $2^n + 1$ делиться на $7$ при каком-нибудь натуральном $n$?

Задание 20: Найди две последние цифры числа $7^{2026}$.

Продвинутые (задания 21–30)

Задание 21: В классе $25$ учеников написали тест, каждый получил целое число баллов от $0$ до $100$. Средний балл равен $60$.

а) Могли ли ровно $20$ учеников получить не менее $70$ баллов?

б) Могли ли $22$ ученика получить не менее $70$ баллов?

в) Какое наибольшее число учеников могло получить не менее $70$ баллов?

Задание 22: Может ли сумма цифр квадрата натурального числа равняться $2027$?

Задание 23: Из чисел $1, 2, \ldots, 20$ удалили одно. Среднее арифметическое оставшихся — целое число. Какое число могли удалить?

Задание 24: Есть сколько угодно монет по $3$ и по $5$ рублей.

а) Можно ли без сдачи заплатить $7$ рублей?

б) Какую наибольшую сумму (в рублях) нельзя заплатить без сдачи?

в) Сколькими способами можно заплатить $100$ рублей (способы различаются количеством монет каждого вида)?

Задание 25: а) Может ли квадрат натурального числа оканчиваться двумя одинаковыми ненулевыми цифрами? б) Тремя? в) Четырьмя?

Задание 26: Какое наибольшее количество чисел можно выбрать из $1, 2, \ldots, 50$ так, чтобы сумма никаких двух выбранных чисел не делилась на $7$?

Задание 27: На доске написано несколько различных натуральных чисел, их сумма равна $100$.

а) Может ли на доске быть $13$ чисел?

б) Может ли на доске быть $14$ чисел?

в) Пусть на доске ровно $12$ чисел. Какое наибольшее количество из них может быть чётными?

Задание 28: Найди все натуральные $n$, при которых $n^2 + 1$ делится на $n + 1$.

Задание 29: Хэш-функция сопоставляет числу $n \in \{0, 1, \ldots, 31\}$ номер ячейки $h(n)$ — остаток от деления на $32$.

а) Пусть $h(n) = (13n + 5) \bmod 32$. Могут ли два разных $n$ попасть в одну ячейку?

б) Пусть $h(n) = (12n + 5) \bmod 32$. Могут ли два разных $n$ попасть в одну ячейку?

в) Сколько различных ячеек занимает $h(n) = (12n + 5) \bmod 32$ при $n = 0, 1, \ldots, 31$?

Задание 30: На доске написано несколько различных натуральных чисел, любые два из которых отличаются не меньше чем на $3$. Сумма чисел равна $100$.

а) Может ли на доске быть $7$ чисел, все чётные?

б) Может ли на доске быть $8$ чисел, все чётные?

в) Какое наибольшее количество чисел может быть на доске?

Частые ошибки

❌ Ошибка 1: «Не может» без доказательства

Неправильно: «Я попробовал несколько наборов — не получилось, значит, нельзя».

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

Почему важно: перебор нескольких вариантов не исключает, что подходящий набор существует. Эксперт такой ответ не засчитает.

❌ Ошибка 2: Только оценка или только пример в пункте в)

Неправильно: «Сумма $n$ чисел не меньше $\frac{n(n+1)}{2}$, значит, $n \le 9$. Ответ: $9$».

Правильно: добавить пример набора из $9$ чисел, где все условия выполнены.

Почему важно: оценка показывает, что больше нельзя, но не доказывает, что $9$ достижимо. Ответ может оказаться $8$.

❌ Ошибка 3: Пример, который не проверен

Неправильно: выписать набор «примерно подходящих» чисел и не проверить сумму или различность.

Правильно: в конце примера явно показать: «числа различны, каждое не больше $20$, сумма равна $180$».

Почему важно: пример с арифметической ошибкой — это не пример. Пункт теряется целиком.

❌ Ошибка 4: Делят сравнение на число, не взаимно простое с модулем

Неправильно: $4x \equiv 8 \pmod{12} \Rightarrow x \equiv 2 \pmod{12}$.

Правильно: $4x \equiv 8 \pmod{12} \Leftrightarrow x \equiv 2 \pmod 3$ (делим и модуль на $\text{НОД}(4, 12) = 4$). Решения: $x = 2, 5, 8, 11, \ldots$ — а не только $2, 14, \ldots$

Почему важно: теряется часть решений. Сокращать сравнение на $a$ можно, только если $a$ взаимно просто с модулем.

❌ Ошибка 5: Путают «не обязательно различные» и «различные»

Неправильно: в задаче про различные числа строят пример с двумя одинаковыми числами — или, наоборот, в задаче с «не обязательно различными» используют оценку $1 + 2 + \ldots + k$.

Правильно: перечитай условие. Для различных чисел сумма $\ge \frac{k(k+1)}{2}$, для произвольных натуральных — только $\ge k$.

Почему важно: эта деталь полностью меняет ответ на пункт в).

❌ Ошибка 6: Забывают, что остаток неотрицателен

Неправильно: «$-7$ при делении на $5$ даёт остаток $-2$».

Правильно: $-7 = 5 \cdot (-2) + 3$, остаток $3$. Остаток всегда от $0$ до $m - 1$.

Почему важно: в программировании это тоже ловушка: в C++ и Java -7 % 5 равно -2, а в Python — 3. Код, переносимый между языками, ломается именно здесь.

Главное запомнить

📝 Ключевые понятия

✅ Сравнение по модулю: $a \equiv b \pmod m \Leftrightarrow m \mid (a - b)$. Сравнения можно складывать, умножать и возводить в степень.

✅ Остатки квадратов: по модулю $3$ и $4$ — $\{0, 1\}$; по модулю $8$ — $\{0, 1, 4\}$; по модулю $9$ — $\{0, 1, 4, 7\}$.

✅ Степени по модулю периодичны: найди степень с остатком $1$ и дели показатель на период.

✅ Признак делимости на 3 и 9: число и сумма его цифр дают одинаковый остаток при делении на $9$ (и на $3$).

✅ Произведение $k$ последовательных целых делится на $k$; $n^3 - n$ делится на $6$, $n^5 - n$ — на $30$.

✅ «Может ли» — да: один конкретный проверенный пример. Нет: доказательство для всех случаев.

✅ Способы доказать «нет»: чётность, остатки, оценка суммы, от противного, разбиение на пары.

✅ Пункт в) = оценка + пример. Без любой из частей — неполный балл.

✅ Сумма $k$ различных натуральных $\ge \frac{k(k+1)}{2}$; сумма $k$ различных, не больших $M$, $\le kM - \frac{k(k-1)}{2}$.

✅ Среднее — это сумма: среднее $s$ у $k$ чисел означает сумму $ks$.

Связь с другими темами курса

Что нужно было знать до этого урока:

• Делители и кратные — делимость, простые числа, разложение на множители
• НОД и НОК — нужны в задачах на системы остатков и в хэш-функциях (задания 7, 11, 29)
• Признаки делимости — быстрые проверки на $2$, $3$, $4$, $5$, $9$, $10$
• Элементы статистики — среднее арифметическое и его связь с суммой
• Арифметическая прогрессия — сумма последовательных чисел (Пример 1 Блока 3, задания 10, 30)

Что изучить дальше:

• Задание 20 ЕГЭ: карта темы — место задачи в экзамене и дополнительные разборы
• Задачи с параметром — задание 19, где тоже работает логика «найти все и доказать, что других нет»
• Кусочные функции — следующий урок раздела
• Хэш-таблицы — как остатки по модулю превращаются в структуру данных

Где это нужно в жизни:

• 💻 В программировании: хэш-таблица кладёт ключ в ячейку hash(key) % size. Если множитель в хэше и размер таблицы имеют общий делитель, часть ячеек пустует, а в других копятся коллизии (задание 29). Поэтому размеры таблиц часто берут простыми или степенями двойки с «перемешивающим» хэшем.
• 🔐 В криптографии: RSA шифрует сообщение $m$ как $m^e \bmod N$, где $N$ — произведение двух больших простых. Взлом требует разложить $N$ на множители — задачу, для которой не известно быстрого алгоритма на обычных компьютерах. В Python возведение в степень по модулю — pow(m, e, N), и оно работает быстро даже для чисел из сотен цифр.
• 💳 Контрольные суммы: номер банковской карты проверяется алгоритмом Луна (сумма цифр с удвоением каждой второй должна делиться на $10$), ISBN книг — остатком по модулю $11$. Одна опечатка в номере — и остаток не сходится.
• 🤖 В ML: «hashing trick» — признаки (например, слова) переводят в индексы вектора через хэш по модулю размерности. Так модель работает с огромным словарём без хранения самого словаря, ценой редких коллизий.

Интересные факты

💡 Гаусс написал «Арифметические исследования» в 24 года. Книга 1801 года, где впервые появилось обозначение $\equiv$, до сих пор считается одной из самых влиятельных в истории математики. Сам Гаусс называл теорию чисел «царицей математики».

💡 «Бесполезная» теория чисел защищает интернет. Годфри Харди в эссе «Апология математика» (1940) писал, что теория чисел не имеет практического применения. Через 37 лет появился RSA, и теперь каждое HTTPS-соединение опирается на арифметику остатков.

💡 Китайская теорема об остатках ускоряет RSA. При расшифровке вычисления по модулю $N = pq$ разбивают на вычисления по модулям $p$ и $q$ отдельно, а потом склеивают результат по китайской теореме. Это ускоряет расшифровку примерно в 3–4 раза — и так делают почти все реальные реализации.

💡 Числа $8k + 7$ «не любят» три квадрата. Как в Примере 3 Блока 1: ни одно число вида $8k + 7$ не является суммой трёх квадратов. А по теореме Лагранжа (1770) любое натуральное число — сумма четырёх квадратов.

Лайфхаки и полезные трюки

1. Не знаешь, что делать, — посмотри на чётность

Первое, что стоит проверить в любом вопросе «может ли»: чётность сумм и произведений. Удивительно много задач решается одной строкой про чётность.

Пример: сумма пяти нечётных не может быть чётной (задание 2).

2. Выбор модуля для квадратов

Для доказательств с квадратами пробуй модули $3$, $4$, $8$, $9$, $16$ — у квадратов по ним мало возможных остатков.

Пример: $a^2 + b^2 \ne 4k + 3$; $a^2 + b^2 + c^2 \ne 8k + 7$.

3. «Остаток на 1 меньше делителя» — прибавь 1

Если $n$ даёт остатки $m_1 - 1$, $m_2 - 1$, … при делении на $m_1$, $m_2$, …, то $n + 1$ делится на все $m_i$, и $n = \text{НОК} - 1$.

Пример: задание 11: $n + 1$ кратно $60$, $n = 59$.

4. Для оценки — «самый выгодный» набор

Чтобы оценить наибольшее значение одной величины, сделай все остальные минимальными (для различных чисел — $1, 2, 3, \ldots$). Чтобы оценить наименьшее — сделай остальные максимальными.

Пример: задания 12 и 13 — наибольшее и наименьшее значение наибольшего числа.

5. Проверяй примеры кодом (для самоподготовки)

from itertools import combinations

# Задание 26: проверим пример из 23 чисел
S = [n for n in range(1, 51) if n % 7 in (1, 2, 3)] + [7]
print(len(S), all((a + b) % 7 for a, b in combinations(S, 2)))

# Задание 20: две последние цифры 7^2026
print(pow(7, 2026, 100))

Встроенный pow(a, b, m) считает $a^b \bmod m$ быстро, не вычисляя само огромное число. А перебор через itertools мгновенно ловит ошибку в примере.

6. Сначала а) и б), потом в)

Пункты а) и б) дают баллы независимо от в), и почти всегда подсказывают идею для в). Решай и оформляй их первыми.

💡 Совет: задание 20 — это тренировка математического мышления в чистом виде. Здесь нельзя «подставить в формулу», зато можно научиться главному: отличать пример от доказательства. Прорешай 30 заданий, проговаривая для каждого ответа «нет» — почему не бывает никогда, а для каждого ответа «да» — какой конкретный набор это показывает.

Дальше — кусочные функции: функции, заданные разными формулами на разных промежутках, и как с ними работать на экзамене.