Задание 19 ЕГЭ профиль: теория чисел

Задание 19 — 4 балла и часто самое нетипичное. Здесь нет стандартных алгебраических формул — нужно думать, что за число, каковы его цифры, делители, остатки. Разбираем все типы.

Что проверяет задание 19

• Делимость (признаки, НОД, НОК)
• Остатки от деления (сравнения по модулю)
• Цифры числа (задачи на цифры)
• Оценка числовых выражений (неравенства с натуральными числами)
• Системы с натуральными ограничениями

Ключевые признаки делимости

Тип 1: Задачи на цифры числа

Запись числа через цифры: Двузначное: $\overline{ab} = 10a + b$ Трёхзначное: $\overline{abc} = 100a + 10b + c$

Пример. Найти все двузначные числа, у которых сумма цифр равна 9, а само число делится на 3.

Решение: $\overline{ab} = 10a + b$, $a + b = 9$, $a \geq 1$, $b \geq 0$.

Пары $(a, b)$: $(1,8), (2,7), (3,6), (4,5), (5,4), (6,3), (7,2), (8,1), (9,0)$.

Делимость на 3 при $a + b = 9$ — выполняется для всех, т.к. $9$ делится на $3$.

Ответ: 18, 27, 36, 45, 54, 63, 72, 81, 90.

Тип 2: Остатки от деления (сравнения по модулю)

Обозначение: $a \equiv r \pmod{m}$ означает, что $a$ при делении на $m$ даёт остаток $r$.

Полезные свойства:

• Если $a \equiv r_1 \pmod{m}$ и $b \equiv r_2 \pmod{m}$, то:
  • $a + b \equiv r_1 + r_2 \pmod{m}$
  • $a \cdot b \equiv r_1 \cdot r_2 \pmod{m}$

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

Решение: $2^1 = 2 \equiv 2 \pmod{3}$ $2^2 = 4 \equiv 1 \pmod{3}$ $2^3 = 8 \equiv 2 \pmod{3}$ $2^4 = 16 \equiv 1 \pmod{3}$

Период 2: чётные степени ≡ 1, нечётные ≡ 2 (по mod 3).

$100$ — чётное. $2^{100} \equiv 1 \pmod{3}$.

Ответ: остаток 1.

Тип 3: Нахождение НОД и НОК

НОД (наибольший общий делитель) — алгоритм Евклида: $\gcd(a, b) = \gcd(b, a \mod b)$

Пример. $\gcd(48, 36)$: $48 = 1 \cdot 36 + 12$ $36 = 3 \cdot 12 + 0$ НОД = 12.

НОК: $\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$

Тип 4: Оценка (задачи на неравенства с натуральными числами)

Нужно доказать, что выражение делится на данное число, или что оно больше/меньше чего-то.

Стандартные приёмы:

1. Полные квадраты/кубы: представить как $A^2 - B^2 = (A-B)(A+B)$

2. Делимость через раскладку: Доказать, что $n^3 - n$ делится на 6: $n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1) \cdot n \cdot (n+1)$ Три последовательных числа — всегда одно делится на 2 и одно на 3. Значит, произведение делится на 6.

Тип 5: Диофантовы уравнения (целые числа)

Нужно найти натуральные или целые решения уравнения.

Пример. Найти все натуральные решения уравнения $3x + 5y = 23$.

Решение: Выражаем: $x = \frac{23 - 5y}{3}$.

Чтобы $x$ было натуральным: $23 - 5y \equiv 0 \pmod{3}$. $23 \equiv 2 \pmod{3}$, $5y \equiv 2y \pmod{3}$. $2y \equiv 2 \pmod{3}$ → $y \equiv 1 \pmod{3}$.

Значения $y$: 1, 4, 7, ... При $y = 1$: $x = \frac{18}{3} = 6$ — натуральное. При $y = 4$: $x = 1$ — натуральное. При $y = 7$: $x$ отрицательное.

Ответ: $(6, 1)$ и $(1, 4)$.

Тип 6: Задачи про простые числа

Признак простого числа: имеет ровно два делителя — 1 и само себя.

Полезный факт: если $n > 1$ не делится ни на одно простое $\leq \sqrt{n}$, то $n$ простое.

Частые вопросы:

• Разложить на простые множители
• Найти все простые числа в промежутке (решето Эратосфена)
• Доказать, что $n^2 + n + 41$ простое для $n = 0, 1, 2, \ldots$ (не всегда!)

Типичные ошибки в задании 19

Ошибка 1. Не проверить все ограничения ($a \geq 1$ в цифровых задачах, $n \in \mathbb{N}$ в Диофантовых).

Ошибка 2. При остатках от деления — неправильно найти период повторения.

Ошибка 3. Думать, что $\gcd(a, b) = a/b$ или перепутать НОД и НОК.

Ошибка 4. При доказательстве делимости — использовать «очевидно» без обоснования.

Ошибка 5. Забыть, что 0 делится на любое число (и это корректный остаток 0).

Чек-лист по заданию 19

• Знаю признаки делимости на 2, 3, 5, 9, 11
• Умею записывать число через цифры: $\overline{ab} = 10a + b$
• Знаю алгоритм Евклида для НОД
• Понимаю сравнения по модулю и умею находить период
• Умею раскладывать выражения для доказательства делимости

Связанные темы

• Задание 19 ЕГЭ — углублённый разбор (блог)
• Системы уравнений

В Сотах задание 19 начинается с делимости (признаки) и цифровых задач, потом остатки. Теория чисел — нестандартная, но в Сотах её прокачивают через конкретные задачи из открытого банка ФИПИ.