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

Известно, что простые числа расположены в натуральном ряду крайне неравномерно. С одной стороны, существует много простых чисел-близнецов (простые числа, отличающиеся друг от друга на 2 единицы), среди которых есть и очень большие, например, такая пара: $$ 242206083 \cdot2^{238880} \pm 1. $$ С другой стороны, натуральный ряд содержит длинные участки, состоящие только из составных чисел. Так, среди сотни чисел $1\,671\,800, \ldots , 1\,671\,900$ нет ни одного простого. Вообще, не трудно показать, что в натуральном ряду имеются сколько угодно большие отрезки, не содержащие простых. Действительно, последовательность $$ n! + 2, n! + 3, \ldots , n! + n $$ содержит только составные числа и, очевидно, может быть сколько угодно длинной при достаточно большом $n$.

Основная проблема распределения простых [8] заключается в том, что до сих пор не известно какой-либо практически полезной формулы для $n$-го простого числа $p_n$, с помощью которой по заданному номеру $n$ можно найти само число $p_n$. Поэтому главной задачей распределения простых чисел в настоящее время считается нахождение оценок или наилучшего асимптотического выражения для $p_n$, или для функции их распределения $\pi(x)$, равной количеству простых, не превосходящих заданного вещественного числа $x$.

Поясним сказанное. Обозначим $\prod(a_n, x)$ количество членов положительной последовательности $a_n$, не превосходящих вещественного $x$. Не трудно, например, найти количество нечётных чисел $\prod(2n- 1, x)$, равное $[(x + 1)/2]$ или количество квадратов $\prod(n^2, x)$, равное $\big[\sqrt{x}\big]$. Легко убедиться, что эта задача сводится к решению относительно $n$ уравнений $2n - 1 = x$, $n^2 = x$, соответственно, и последующему взятию целой части. Для случая $\prod(p_n, x) = \pi(x)$ получим уравнение $p_n = x$, точное решение которого относительно $n$ не найдено, поскольку не известны сколько-нибудь пригодные практически * точные формулы для $p_n$ и $\pi(x)$.

Простые числа, как известно, образуют мультипликативный базис множества натуральных чисел. Проще говоря, любое натуральное число может быть получено перемножением некоторого количества простых чисел и этот набор простых уникален для данного натурального числа — основная теорема арифметики [6]. Этот факт выражает исключительную важность простых чисел для арифметики и, следовательно, для математики в целом.

Многие вопросы, относящиеся к простым числам, помимо собственно теории чисел, тесно связаны со многими труднейшими, до настоящего времени (2017 год) не решёнными, проблемами из различных областей математики, такими, как гипотеза о нулях дзета-функции Римана и задача об эквивалентности алгоритмической сложности классов P и NP. Обе эти задачи входят в список семи так называемых «проблем тысячелетия», за доказательство каждой из которых Институт математики Клея (Clay Mathematics Institute, Кембридж, Массачусетс, США) обещает выплатить приз в размере $1\,000\,000$ долларов.

Кроме этого, в последнее время, с развитием компьютерной техники и Интернета, проблема распределения простых чисел приобрела и важное практическое значение поскольку она напрямую связана с надежностью так называемых криптографических систем с открытым ключом, которые используются при передаче секретной информации по открытым каналам связи**. Однако, мы любим простые числа не за это.

Следующая теорема — это единственный за более, чем 2000 лет, строго доказанный результат, относящийся к распределению простых чисел в натуральном ряду. Доказательство этой теоремы, без всякого сомнения, можно считать настоящим образцом эстетически безупречного рассуждения в математике.

Теорема 3.1 (Евклид, «Начала», кн. IX, III в. до н. э.) Существует бесконечно много простых чисел.

Доказательство. Пусть имеется только конечное количество $r$ простых чисел \begin{equation} \label{EVCLID_primes_prod} p_1, p_2, \ldots , p_r. \end{equation} Рассмотрим число $N = (p_1 p_2 \times \ldots. \times p_r) + 1$. Это число не делится ни на одно из чисел (\ref{EVCLID_primes_prod}) и, очевидно, больше любого из них. Следовательно, $N$ — простое, что противоречит допущению. ♦

Позднее (не прошло и 2000 лет) были найдены другие доказательства бесконечности множества простых. Некоторые из этих доказательств весьма остроумны технически и глубоки по содержанию (особенно необходимо отметить замечательный результат Л. Эйлера 1737 года) [8] [9], но ни одно из них не сравнимо с простым и ясным доказательством Евклида.

Распределение простых чисел в натуральном ряду задаётся функцией, обозначаемой $\pi(x)$ и равной количеству простых, не превосходящих вещественного числа $x$. Перечислим простейшие её свойства. Все эти свойства следуют непосредственно из только что приведённого определения функции $\pi(x)$ — см. график $\pi(x)$, $x < 100$.

Свойства функции $\pi(x)$:

1. $\pi(x) = \pi\big( [x] \big)$ для любого вещественного $x > 0$.
2. $\pi(p_n) = n$, где $p_n$ — $n$-ое по порядку простое число.
3. «Характеристическая функция» множества простых $$ \pi(k) - \pi(k - 1) = \left\{ \begin{array}{ll} 1, k \textrm{ прост.}\\ 0, k \textrm{ сост.} \end{array} \right. $$
4. Непосредственное следствие из предыдущего пункта: $$ \sum_{p \; \le \; x}\!\!f( p )\! =\!\!\!\!\!\!\!\sum_{k \; \le \; p_{\pi(x)}}\!\!\!\!\!\bigl(\!\pi(k)\! -\! \pi(k-1)\!\bigr)\!f(k) $$
5. $\pi(x) < x$ для любого $x > 0$ и, соответственно, $p_n > n$ для любого $n$, так как не все натуральные числа простые.

Проведём грубую оценку снизу функции $\pi(x)$ (П. Эрдёш [5]). Для этого рассмотрим множество $n$ первых натуральных чисел \begin{equation} \label{ERDES_nat_numbers} 1, 2, 3, \ldots, n. \end{equation} Пусть $Q$ — множество всех квадратов в (\ref{ERDES_nat_numbers}), кроме $1^2$. Очевидно, что выполняется неравенство $\big| Q \big| \le \sqrt{n}$. Обозначим $L$ — множество всех чисел в (\ref{ERDES_nat_numbers}) свободных от квадратов (т. е. не делящихся ни на какой полный квадрат). Ясно, что все числа из $L$ содержатся среди всех делителей произведения $$ p_1 p_2 \times \ldots \times p_{\pi(n)}, $$ поэтому, $\big| L \big|$ равно количеству всех подмножеств $\pi(n)$-элементного множества, т. е. (см. формулу (2.3)) $$ |L| = \sum_{k = 0}^{\pi(n)} C^{k}_{\pi(n)} = 2^{\pi(n)}. $$ Пусть $M$ — множество, образованное произведением всех различных пар чисел из множеств $Q$ и $L$: $$ M = \left\{ ql\; |\; q \in Q, l \in L \right\}. $$ Легко видеть, что множество (\ref{ERDES_nat_numbers}) содержится в $M$ и $|M| = |Q| |L|$. Отсюда имеем неравенство $$ n \le \sqrt{n} 2^{\pi(n)} $$ или \begin{equation} \label{weak_estim_0} 2^{\pi(n)} \ge \sqrt{n}, \end{equation} откуда, с учетом свойства 5° функции $\pi(x)$ получаем довольно слабую, как увидим далее, оценку \begin{equation} \label{weak_estim} \frac{1}{\ln 4} \, \ln n \le \pi(n) < n . \end{equation}