Бесконечность множества простых чисел

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

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

Доказательство. Пусть имеется только конечное количество r простых чисел p₁, p₂, ... , p_r.

Рассмотрим число N = (p₁p₂ × ... × p_r) + 1. Это число не делится ни на одно из чисел (1) и, очевидно, больше любого из них. Следовательно, N — простое, что противоречит допущению. ♦

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

Функция распределения простых чисел

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

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

1. π(x) = π([x]) для любого вещественного x ≥ 0.

2. π(p_n) = n, где p_n — n-ое по порядку простое число.

3. «Характеристическая функция» множества простых π(k) − π(k − 1) = { 1, если k — простое 0, если k — составное

4. Непосредственное следствие из предыдущего пункта:

   ∑p ≤ x f(p)   =  ∑k ≤ pπ(x)(π(k) − π(k − 1))f(k)

5. π(x) < x для любого x > 0 и, соответственно, p_n > n для любого n, так как не все натуральные числа простые.

Проведём грубую оценку снизу функции π(x) (П. Эрдёш [5]). Для этого рассмотрим множество n первых натуральных чисел1, 2, 3, ..., n.Пусть Q — множество всех квадратов в (2), кроме 1². Очевидно, что |Q| ≤ √n. Обозначим L — множество всех чисел в (2) свободных от квадратов (т. е. не делящихся ни на какой полный квадрат). Ясно, что все числа из L содержатся среди всех делителей произведения p₁∙p₂ × ... × p_π(n),

поэтому, |L| равно количеству всех подмножеств π(n)-элементного множества.

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

Теорема о распределении простых чисел — теорема аналитической теории чисел, описывающая асимптотику распределения простых чисел. А именно, она утверждает, что функция распределения простых чисел   (количество простых чисел на отрезке от 1 до n) растёт с ростом n как  , то есть:

 когда 

Грубо говоря, это означает, что у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен  .

Также эта теорема может быть эквивалентным образом переформулирована для описания поведения  -го простого числа  : она утверждает, что

(здесь и далее запись   означает, что   когда аргумент функций стремится к бесконечности).

]Первым статистическую закономерность в расположении простых чисел подметил Гаусс. В письме Энке (1849) он сообщил, что ещё в 1792 или 1793 году, чисто эмпирически, обнаружил, что плотность простых чисел «в среднем близка к величине, обратно пропорциональной логарифму». К этому времени, основываясь на таблицах простых чисел, составленных Фелкелем и Вегой, Лежандр предположил в 1796 году, что функция распределения простых чисел   (число простых чисел, не превосходящих x) может быть приближена выражением:

где   Гаусс в упомянутом письме критикует формулу Лежандра и, используя эвристические рассуждения, предлагает другую приближающую функцию — интегральный логарифм:

Однако Гаусс нигде не опубликовал эту гипотезу. Оба приближения, как Лежандра, так и Гаусса, приводят к одной и той же предполагаемой асимптотической эквивалентности функций   и  , указанной выше, хотя приближение Гаусса и оказывается существенно лучше, если при оценке ошибки рассматривать разность функций вместо их отношения.

В двух своих работах, 1848 и 1850 года, Чебышев доказывает[2], что верхний M и нижний m пределы отношения

(1)

заключены в пределах  , а также, что если предел отношения (1) существует, то он равен 1. Позднее (1881) Дж. Дж. Сильвестр сузил допустимый интервал для предела с 10% до 4%.

В 1859 году появляется работа Римана, рассматривающая (введённую Эйлером как функцию вещественного аргумента)  -функцию в комплексной области, и связывающая её поведение с распределением простых чисел. Развивая идеи этой работы, в 1896 году Адамар и Валле-Пуссен одновременно и независимо доказывают теорему о распределении простых чисел.

Наконец, в 1949 году появляется не использующее комплексный анализ доказательство Эрдеша—Сельберга.