Главная Перейти к главной странице
Введение I. Теория чисел Теорема Вильсона Две теоремы Ферма Распределение простых чисел Неравенства Чебышева II. Анализ III. Модели IV. Задачи
Обозначения Литература

РАСПРЕДЕЛЕНИЕ ПРОСТЫХ ЧИСЕЛ

Известно, что простые числа расположены в натуральном ряду крайне неравномерно. С одной стороны, существует много простых чисел-близнецов (простые числа, отличающиеся друг от друга на 2 единицы), среди которых есть и очень большие, например, такая пара: 242206083 ∙ 2238880 − 1,   242206083 ∙ 2238880 + 1.

С другой стороны, натуральный ряд содержит длинные участки, состоящие только из составных чисел. Так, среди сотни чисел 1671800, ... , 1671900 нет ни одного простого. Вообще, не трудно показать, что в натуральном ряду имеются сколько угодно большие отрезки, не содержащие простых. Действительно, последовательность n! + 2, n! + 3, ... , n! + n содержит только составные числа и, очевидно, может быть сколько угодно длинной при достаточно большом n.

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

Поясним сказанное. Обозначим ∏(an, x) количество членов положительной последовательности an, не превосходящих вещественного x. Не трудно, например, найти количество нечётных чисел ∏(2n − 1, x), равное [(x + 1)/2] или количество квадратов ∏(n2, x), равное [x]. Легко убедиться, что эта задача сводится к решению относительно n уравнений 2n − 1 = x, n2 = x, соответственно, и последующему взятию целой части. Для случая ∏(pn, x) = π(x) получим уравнение pn = x, точное решение которого относительно n не найдено, поскольку не известны сколько-нибудь пригодные практически точные формулы для pn и π(x).

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

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

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

БЕСКОНЕЧНОСТЬ МНОЖЕСТВА ПРОСТЫХ ЧИСЕЛ

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

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

Доказательство. Пусть имеется только конечное количество r простых чисел p1, p2, ... , pr.

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

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

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

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


график \pi(x)

Рис. 1. Функция π(x), x < 100.

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

  1. π(x) = π([x]) для любого вещественного x ≥ 0.
  2. π(pn) = n, где pnn-ое по порядку простое число.
  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 и, соответственно, pn > n для любого n, так как не все натуральные числа простые.

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

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

|L| = π(n) k = 0 Ckπ(n) = 2π(n),
Пусть M — множество, образованное произведением всех различных пар чисел из множеств Q и L: M = {ql | q ∈ Q, l ∈ L}. Легко видеть, что множество (2) содержится в M и |M| = |Q| |L|. Отсюда имеем неравенство n ≤ 2π(n)n или 2π(n) ≥ √n, откуда, с учетом свойства 5° функции π(x) получаем довольно слабую, как увидим далее, оценку 1 ln4 lnn ≤ π(n) < n

Заменяя в (4) npn и используя другое неравенство из свойства 5° получим столь же грубую оценку для n-го простого числа n < pn ≤ 4n.