Числа Серпинского: что это и накрывающий набор

Число Серпинского - это нечётное натуральное число $k$, для которого выражение $k \cdot 2^n + 1$ оказывается составным при всех натуральных $n$. На первый взгляд это странно: формула $k \cdot 2^n + 1$ при росте $n$ даёт всё более крупные числа, и среди них, казалось бы, обязаны попадаться простые. Но для некоторых $k$ простых не возникает никогда, и причина не в случайности, а в красивой конструкции из теории чисел - накрывающем наборе простых. Ниже разберём, что такое число Серпинского, почему наименьшее известное равно 78557, как устроен накрывающий набор и где студенты ошибаются. Чтобы сразу увидеть, чем число Серпинского отличается от обычного нечётного, покрути калькулятор ниже: он красит каждое $n$ цветом простого, которое делит $k \cdot 2^n + 1$.

Что такое число Серпинского

Зафиксируем нечётное $k$ и будем подставлять $n = 1, 2, 3, \dots$ в выражение

$k \cdot 2^n + 1.$

Для большинства нечётных $k$ среди получающихся чисел рано или поздно встречаются простые. Например, при $k = 5$ уже $5 \cdot 2^1 + 1 = 11$ - простое. А вот число $k$ называют числом Серпинского, если простого не получается ни при одном $n$: всё бесконечное семейство $k \cdot 2^n + 1$ состоит из составных чисел. Польский математик Вацлав Серпинский в 1960 году доказал, что таких $k$ бесконечно много, но его доказательство не давало конкретного значения - оно лишь показывало существование.

Требование «составное при всех $n$» очень сильное. Проверить его перебором невозможно: $n$ пробегает бесконечный ряд, и сколько бы значений мы ни проверили вручную, остаётся бесконечный хвост. Поэтому доказательство, что данное $k$ - число Серпинского, строится не на переборе, а на одной идее, которая закрывает сразу все $n$.

Накрывающий набор простых

Ключевая конструкция - накрывающий набор (covering set): конечный набор простых чисел, такой что для каждого $n$ хотя бы одно простое из набора делит $k \cdot 2^n + 1$. Если такой набор найден, число $k \cdot 2^n + 1$ всегда имеет делитель меньше себя и потому составное при любом $n$.

Работает это благодаря периодичности степеней двойки. Остатки $2^n$ по модулю простого $p$ повторяются с периодом, равным порядку двойки по модулю $p$. Значит, и делимость $k \cdot 2^n + 1$ на $p$ зависит только от остатка $n$ по этому периоду. Достаточно набрать столько простых, чтобы их периоды вместе закрывали все классы остатков.

Рассчитать для своей задачи

Для $k = 78557$ накрывающий набор - это семь простых: $\{3, 5, 7, 13, 19, 37, 73\}$. Их периоды по основанию 2 равны 2, 4, 3, 12, 18, 36 и 9, а наименьшее общее кратное этих периодов равно 36. Поэтому всё поведение определяется остатком $n$ по модулю 36: достаточно проверить $n = 0, 1, \dots, 35$ и убедиться, что каждый класс закрыт хотя бы одним простым.

Почему 78557 - наименьшее число Серпинского

Конкретное значение $k = 78557$ нашёл Джон Селфридж в 1962 году. Он же предъявил накрывающий набор $\{3, 5, 7, 13, 19, 37, 73\}$ и проверил, что тот закрывает все 36 классов остатков. Это и есть полное доказательство: раз каждый $n$ попадает в покрытый класс, $78557 \cdot 2^n + 1$ делится на одно из семи простых и не может быть простым само.

Рассчитать для своей задачи

Таблица показывает разбиение остатков: класс $n \equiv 0 \pmod 2$ ловит тройка, ряд классов - пятёрка и семёрка, а самые «редкие» классы достаются крупным простым. Особый случай - класс $n \equiv 27 \pmod{36}$: его закрывает только число 37, единственное среди всех 36 классов. Уберите 37 из набора - и появится дыра, в которой $78557 \cdot 2^n + 1$ снова сможет оказаться простым.

То, что 78557 - именно наименьшее число Серпинского, до сих пор не доказано строго, но в это верят. Меньшие нечётные кандидаты проверяет распределённый проект Seventeen or Bust и его продолжения: для каждого из них ищут хотя бы одно $n$, при котором $k \cdot 2^n + 1$ простое. Если такое $n$ найдено, кандидат вычеркивается - он не число Серпинского. К настоящему времени почти все кандидаты меньше 78557 исключены, остаются единицы, для которых простое пока не нашли, но и накрывающего набора у них нет.

Чем число Серпинского отличается от обычного

Удобный способ почувствовать разницу - сравнить ленту делителей. Для числа Серпинского каждое $n$ окрашено: всегда есть простое из набора, которое делит $k \cdot 2^n + 1$. Для обычного нечётного $k$ покрытия нет, и среди значений попадаются простые - в калькуляторе выше они отмечены отдельным цветом. Возьмите $k = 3$: при малых $n$ значения ещё делятся на простые из стандартного набора, но уже $3 \cdot 2^5 + 1 = 97$ простое, и красная отметка появляется. Это сразу доказывает, что тройка числом Серпинского не является.

Важно не путать число Серпинского с близкой задачей про числа Ризеля: там рассматривают $k \cdot 2^n - 1$ (минус единица вместо плюс). Наименьшее известное число Ризеля - 509203, и у него свой накрывающий набор. Идея одна и та же, но конкретные значения и наборы разные.

Связь с теорией чисел

Числа Серпинского - яркий пример того, как периодичность по модулю управляет арифметикой. Один и тот же приём - накрывающий набор - применяют в задачах про последовательности вида $a \cdot b^n + c$, в вопросах о простоте чисел Ферма и Мерсенна и в конструкциях контрпримеров. Если вы изучаете эту тему, полезно сначала разобраться с порядком элемента по модулю и малой теоремой Ферма: именно из них следует периодичность остатков $2^n$, на которой всё держится.

Накрывающие наборы интересны и сами по себе: вопрос, существует ли число Серпинского без накрывающего набора, остаётся открытым. Все известные числа Серпинского имеют накрывающий набор, но доказательства, что иначе быть не может, нет.

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

• Пробуют доказать перебором. Проверить $k \cdot 2^n + 1$ для $n$ от 1 до 1000 и не найти простого - не доказательство: остаётся бесконечный хвост. Нужен накрывающий набор, закрывающий все классы остатков сразу.
• Забывают про нечётность $k$. Определение числа Серпинского даётся для нечётных $k$. Для чётного $k$ задача вырождается и обычно не рассматривается.
• Путают с числами Ризеля. $k \cdot 2^n + 1$ - это Серпинский, $k \cdot 2^n - 1$ - это Ризель. Наборы и наименьшие значения у них разные.
• Считают 78557 доказанным минимумом. Доказано, что 78557 - число Серпинского, но что меньшего не существует - пока гипотеза, проверяемая вычислениями.
• Берут слишком маленький набор. Если хотя бы один класс остатков не закрыт, набор не накрывающий, и значение $k \cdot 2^n + 1$ в этом классе может оказаться простым.

FAQ

Что такое число Серпинского простыми словами? Это нечётное число $k$, для которого все числа вида $k \cdot 2^n + 1$ составные, сколько ни увеличивай $n$. Простого среди них не бывает никогда, и это гарантируется накрывающим набором простых.

Почему именно 78557? Для 78557 найден накрывающий набор $\{3, 5, 7, 13, 19, 37, 73\}$, который делает $78557 \cdot 2^n + 1$ составным при любом $n$. Это наименьшее $k$ с доказанным таким свойством; что меньшего нет - гипотеза, которую проверяют распределёнными вычислениями.

Как проверить, что данное $k$ не число Серпинского? Достаточно найти хотя бы одно $n$, при котором $k \cdot 2^n + 1$ простое. Одного такого примера хватает, чтобы исключить $k$. Калькулятор выше делает это автоматически и отмечает простое значение.

Коротко

Число Серпинского - это нечётное $k$, для которого $k \cdot 2^n + 1$ составное при всех $n$. Доказывают это не перебором, а накрывающим набором простых: остатки $2^n$ периодичны, поэтому конечный набор простых способен закрыть все классы остатков сразу. Наименьшее известное число Серпинского - 78557 с набором $\{3, 5, 7, 13, 19, 37, 73\}$ и периодом 36. Чтобы исключить кандидата, достаточно найти одно $n$, дающее простое значение.