D9 Простые числа и их распределение

Метод состоит в систематическом использовании свойств простых чисел для решения задач о делимости, уравнениях в натуральных числах и распределении. Простое число $p > 1$ делится только на $1$ и на себя — это свойство, которое жёстко ограничивает возможные разложения.

Интуиция: простые числа — это «атомы» натуральных чисел. Если произведение нескольких натуральных чисел равно простому $p$, то один из множителей равен $p$, а остальные — $1$. Это сильнейшее ограничение: из бесконечного числа возможных разложений остаётся ровно одно (или два, с учётом знака). На этом строится большинство задач.

Ключевые инструменты: теорема о бесконечности простых чисел (по Евклиду), распределение простых по остаткам (теорема Дирихле о простых в арифметической прогрессии, на уровне «существования»), малая теорема Ферма, признаки составности. На олимпиадах чаще всего нужны: «если $P \cdot Q = p$, то $P = 1$ и $Q = p$», «если $p \mid ab$, то $p \mid a$ или $p \mid b$» (простое число — простой множитель), и «бесконечно много простых числа формы ...».

• Основная теорема арифметики: каждое натуральное число $n > 1$ единственным образом представляется в виде произведения простых чисел (с точностью до порядка$). *$Условие: всегда. Когда использовать:* при анализе делителей и при разложении числа.

• Свойство простых делителей произведения: если $p$ простое и $p \mid ab$, то $p \mid a$ или $p \mid b$. Условие: $p$ простое (для составных это неверно!$). *$Когда использовать:* при анализе делимости произведений.

• Малая теорема Ферма: $a^{p-1} \equiv 1 \pmod{p}$ при $p \nmid a$. Когда использовать: при вычислении остатков степеней по простому модулю.

• Бесконечность простых (Евклид): существует бесконечно много простых чисел. Когда использовать: при задачах «найдите бесконечно много простых числа вида...» — идея доказательства Евклида (предположение о конечности → произведение + 1).

• Простые в арифметической прогрессии (Дирихле): если $\gcd(a, d) = 1$, то прогрессия $a, a+d, a+2d, \ldots$ содержит бесконечно много простых. Условие: $\gcd(a,d)=1$. Когда использовать: при задачах на существование простых с заданными остатками.

• Разбор делителей единственного разложения. Если $AB = p$ (простое), то $(A=1, B=p)$ или $(A=p, B=1)$. Перебери все случаи.

• Наименьший простой делитель. Если задача содержит натуральное число $n$, рассмотри его наименьший простой делитель $p$. Часто из условия следует ограничение на $p$.

• Два случая: $n$ простое и $n$ составное. Многие задачи про натуральные $n$ естественно разбиваются на эти два случая.

• Бесконечность через конструкцию Евклида. Если нужно бесконечно много простых с нужным свойством — рассмотри число $N = \text{(произведение)} \pm 1$ или похожую конструкцию и найди новое простое.

• Свойство $p \mid ab \Rightarrow p \mid a$ или $p \mid b$. Применяется при цепочке делимостей: если $p \mid x_1 x_2 \cdots x_k$, то $p$ делит хотя бы один $x_i$.

• Проверка малых простых. Для задач с конкретными числами: перебери $p = 2, 3, 5, 7, 11, 13$ и ищи закономерность.

Поверхностные признаки (что буквально написано):
- «Найдите все простые $p$, при которых...»
- «Докажите, что $n$ является простым числом»
- «Докажите, что существует бесконечно много простых чисел вида...»
- «Найдите все натуральные $n$, такие что $n$ и $n+2$ — оба простые»

Структурные признаки (форма выражения, объекты):
- Задача про делители числа, которое является простым или содержит простые множители
- Произведение нескольких натуральных чисел равно простому или степени простого
- Задача про $\gcd(f(n), g(n))$ для полиномов

Цель задачи (что от тебя хотят):
- Найти все простые с заданным свойством (обычно конечный ответ)
- Доказать бесконечность простых в заданном множестве
- Доказать, что некоторое выражение простое или составное

Задача 1. Найдите все простые числа $p$, при которых $2p + 1$ также простое.

Источник: тренировочная (классический тип)

Как думать (рассуждение ученика$):
1. $Что вижу?* $p$ простое, $2p+1$ тоже простое. Ищем все такие $p$.$2. *$Разбиваю по случаям: $p = 2$: $5$ — простое ✓. $p = 3$: $7$ — простое ✓.$3. *$Для $p \geq 5$:* $p$ простое и $p \neq 3$, значит $p \equiv 1$ или $p \equiv 2 \pmod{3}$.
- $p \equiv 1 \pmod 3$: $2p + 1 \equiv 3 \equiv 0 \pmod 3$ — делится на 3, составное.
- $p \equiv 2 \pmod 3$: $2p + 1 \equiv 5 \equiv 2 \pmod 3$ — не делится на 3, но это лишь необходимое условие.
4. Перебор: $p = 5$: $11$ простое ✓; $p = 7$: $15 = 3 \cdot 5$ составное. Значит, нет единого ответа для всех $p \equiv 2 \pmod 3$, задача требует перечисления.

Решение:

$p = 2$: $2 \cdot 2 + 1 = 5$ — простое. $p = 3$: $2 \cdot 3 + 1 = 7$ — простое.

Пусть $p \geq 5$. Тогда $p$ простое, $p \neq 3$, значит $p \equiv 1$ или $p \equiv 2 \pmod{3}$.
- $p \equiv 1 \pmod 3$: $2p + 1 \equiv 2 + 1 = 3 \equiv 0 \pmod 3$, то есть $3 \mid 2p+1$ и $2p+1 > 3$, значит составное.
- $p \equiv 2 \pmod 3$: необходимое условие выполнено. Пример: $p = 5$, $2p+1 = 11$ простое; $p = 11$, $2p+1 = 23$ простое; $p = 7$, $2p+1 = 15$ составное.

Таким образом, пар бесконечно много (гипотеза о простых Жермен), но строгое доказательство их бесконечности открыто. Для олимпиадной задачи отвечаем: при $p \equiv 1 \pmod 3$ и $p \geq 5$ число $2p+1$ составное.

Ответ: при $p \equiv 1 \pmod 3$ и $p \geq 5$ выражение $2p+1$ всегда составное.

Что в этой задаче было главным: анализ остатков по $\bmod 3$ для простых $p \geq 5$ позволяет отсечь один из классов.

Задача 2. Докажите, что существует бесконечно много простых чисел вида $4k + 3$.

Источник: классика теории чисел (доказательство по Евклиду)

Как думать (рассуждение ученика$):
1. $Что вижу?* «Существует бесконечно много простых вида $4k+3$» — нужно элементарное доказательство.$2. *$Стратегия Евклида: предположим, что простых такого вида конечное число $p_1, \ldots, p_r$. Построим число, которое не делится ни на одно из них, но содержит простой делитель вида $4k+3$.$3. *$Конструкция:* $N = 4 p_1 p_2 \cdots p_r - 1$. Тогда $N \equiv 3 \pmod 4$. Значит, хотя бы один простой делитель $q \equiv 3 \pmod 4$.

Решение:

Предположим, что таких простых конечно: $p_1 = 3, p_2, \ldots, p_r$ — все простые вида $4k+3$. Рассмотрим $N = 4p_1 p_2 \cdots p_r - 1$.

$N \equiv -1 \equiv 3 \pmod{4}$. Все простые делители $N$ нечётны (так как $N$ нечётно). Произведение нечётных простых, каждое $\equiv 1 \pmod 4$, само $\equiv 1 \pmod 4$. Но $N \equiv 3 \pmod 4$, значит среди делителей $N$ есть хотя бы одно простое $q \equiv 3 \pmod 4$.

Но $q \mid N = 4p_1 \cdots p_r - 1$, откуда $q \nmid 4p_1 \cdots p_r$, значит $q \notin \{p_1, \ldots, p_r\}$. Противоречие с полнотой списка.

Ответ: простых вида $4k+3$ бесконечно много.

Что в этой задаче было главным: наблюдение «произведение чисел $\equiv 1 \pmod 4$ тоже $\equiv 1 \pmod 4$» — ключ к построению $N$.

• Ошибка: считать, что «$p \mid ab$» при составном $p$ влечёт «$p \mid a$ или $p \mid b$». → Почему неверно: для составного $m$: $6 \mid 4 \cdot 9 = 36$, но $6 \nmid 4$ и $6 \nmid 9$. → Как избежать: свойство «$p \mid ab \Rightarrow p \mid a$ или $p \mid b$» верно только для ПРОСТОГО $p$.

• Ошибка: «$1$ — простое число». → Почему неверно: по определению простые $> 1$. $1$ не является простым. → Как избежать: всегда проверяй $p > 1$ в условиях задачи.

• Ошибка: конструкция Евклида $N = p_1 \cdots p_r + 1$ якобы даёт простое число. → Почему неверно: $N$ может быть составным, но содержит новый простой делитель. → Как избежать: говори «$N$ содержит простой делитель, не из нашего списка», а не «$N$ само простое».

• Ошибка: забыть рассмотреть случай $p = 2$ или $p = 3$ при переборе простых. → Почему неверно: малые простые часто дают исключения. → Как избежать: всегда проверяй $p = 2, 3$ отдельно, прежде чем переходить к общему случаю.