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

Можно составить список всех простых чисел, не превышающих какого-то данного числа следующим образом. Напишем подряд все натуральные числа от 2 до затем вычеркнем все числа, являющиеся кратными 2 (не считая самого числа 2), все числа, являющиеся кратными 3 (не считая 3), и т.д. — пока не будут вычеркнуты все составные числа. Эта процедура, известная под названием «решета Эратосфена», позволит выловить все простые числа в пределах от 2 до Усовершенствования этого метода мало-помалу привели к тому, что в настоящее время составлены вполне надежные таблицы простых чисел примерно до 10 000 000. Они предоставляют в наше распоряжение обширнейший эмпирический материал,

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

а) Формулы, дающие простые числа

Были сделаны попытки найти элементарные арифметические формулы, которые давали бы только простые числа, хотя бы и не требуя того, чтобы они давали все простые числа. Ферма высказал предположение (не выставляя его в качестве положительного утверждения), что все числа вида

являются простыми. В самом деле при мы получаем

— только простые числа. Но в 1732 г. Эйлер разложил на множители число ; таким образом, число уже не простое. Позднее среди этих «чисел Ферма» удалось обнаружить другие составные числа, причем ввиду непреодолимых трудностей, с которыми были связаны непосредственные пробы, в каждом случае были выработаны более глубокие теоретико-числовые методы. В настоящее время остается неизвестным даже то, дает ли формула Ферма бесконечное множество простых чисел.

Вот другое простое и замечательное выражение, дающее много простых чисел:

При есть простое число; но уже при простого числа не получается:

Выражение

дает простые числа до включительно; при получается составное число.

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

b) Простые числа в арифметических прогрессиях

Если доказательство того, что в последовательности всех натуральных чисел содержится бесконечное множество простых чисел, носит вполне элементарный характер, то следующий шаг в сторону таких последовательностей, как, например, или или, вообще говоря, в сторону произвольной арифметической прогрессии а, а (где а и не имеют общих множителей) оказался связанным с гораздо большими трудностями. Все наблюдения только подтверждали тот факт, что в каждой такой прогрессии содержится бесконечное число простых чисел, как и в простейшей из них Но понадобились величайшие усилия для того, чтобы доказать эту общую теорему. Успех был достигнут Леженом Дирихле (1805-1859), одним из ведущих математиков прошлого столетия, который применил при доказательстве самые усовершенствованные средства математического анализа из известных в то время. Его замечательные работы в этой области даже для настоящего времени остаются непревзойденными; прошло около ста лет, но доказательства Дирихле все еще не упрощены настолько, чтобы они могли быть поняты теми, кто не овладел полностью техникой математического анализа и теорией функций.

Мы не будем здесь пытаться привести доказательство общей теоремы Дирихле и ограничимся рассмотрением более легкой задачи: обобщим Евклидово доказательство о существовании бесконечного множества простых чисел таким образом, чтобы оно охватило некоторые специальные прогрессии, например, или Рассмотрим первую из этих прогрессий. Заметим прежде всего, что всякое простое число, большее чем 2, — непременно нечетное (иначе оно делилось бы на 2) и, следовательно, имеет вид или (при целом Далее, произведение двух чисел вида также есть число того же вида, так как

Допустим теперь, что существует лишь конечное число простых чисел вида обозначим их и рассмотрим число

Одно из двух: или число простое, или оно разлагается на произведение простых чисел, среди которых, однако, не может быть ни одного из чисел так как эти числа делят N с остатком —1.

Заметим дальше, что все множители, входящие в не могут быть вида так как само не этого вида, тогда как мы видели, что произведение чисел вида является числом того же вида. Итак, хоть один из множителей, входящих в должен быть вида а это невозможно, так как ни одно из чисел не входит множителем в а числами все простые числа вида по предположению, исчерпываются. Таким образом, допуская, что существует лишь конечное число простых чисел вида мы приходим к противоречию, и значит, число таких чисел бесконечно.

Упражнение. Докажите соответствующую теорему для прогрессии

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

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

При всяком целом обозначим через число простых чисел среди чисел Если мы выделим среди первых чисел натурального ряда

те, которые являются простыми, то не представит труда подсчитать ряд значений

Возьмем теперь какую-нибудь неограниченно возрастающую последовательность значений например,

тогда соответствующие значения

также будут возрастать безгранично (хотя и более медленно). Действительно, множество простых чисел, как мы уже знаем, бесконечно, и потому значения рано или поздно станут больше любого назначенного числа. «Плотность» распределения простых чисел среди первых чисел натурального ряда дается отношением не представляет особого труда с помощью таблиц простых чисел подсчитать значения при достаточно больших значениях

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

Рис. 5. Площадь заштрихованной области под гиперболой определяет

Распределение отдельных простых чисел отличается чрезвычайно неправильным характером. Но эта неправильность «в малом» исчезает, если мы направим внимание к распределению «в среднем», находящему свое выражение в изменениях отношения при неограниченно растущем Простой закон, которому подчиняется поведение этого отношения, следует отнести к числу самых замечательных открытий, сделанных во всей математике. Для того чтобы сформулировать теорему о распределении простых чисел, к которой мы теперь подходим, необходимо предварительно разъяснить, что такое «натуральный логарифм» числа Для этой цели возьмем в плоскости две взаимно перпендикулярные оси и рассмотрим геометрическое место таких точек на плоскости, для которых произведение расстояний х и у от двух осей равно единице. В терминах координат х

и у это геометрическое место есть равносторонняя гипербола, уравнение которой имеет вид Мы определим как площадь (рис. 5) фигуры, ограниченной гиперболой и двумя вертикальными прямыми . (Более детально логарифм и его свойства будут рассмотрены в главе VIII.) Чисто случайно, в связи с изучением таблицы простых чисел, Гаусс заметил, что отношение приблизительно равно и что точность этого приближения, по-видимому, улучшается при возрастании Насколько удовлетворительно приближение, можно судить по отношению значения которого при показаны в следующей табличке:

Основываясь на такого рода эмпирической очевидности, Гаусс высказал в качестве предположения, что отношение «асимптотически равно» Смысл этого утверждения заключается в следующем: если возьмем последовательность значений становящихся все больше и больше, например,

(как мы делали и раньше), то отношение

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

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

Хотя схватить содержание высказанного Гауссом предположения не представляет особой трудности, однако его строгое математическое доказательство во времена Гаусса было за пределами возможностей математической науки. Для того чтобы доказать теорему о распределении простых чисел, говорящую лишь о самых элементарных математических понятиях, неизбежно нужно прибегнуть к самым мощным методам современной математики. Пришлось ждать почти сто лет, пока анализ получил достаточное развитие для того, чтобы Адамар (1896) в Париже и Валле-Пуссен (1896) в Лувэне смогли дать исчерпывающее доказательство теоремы о распределении простых чисел. Упрощения и важные дополнения были затем внесены Мангольдтом и Э. Ландау. Задолго до Адамара значительное продвижение в этой области было сделано Риманом (1826-1866) в его знаменитой работе, намечающей основные стратегические линии предстоящей атаки. Совсем недавно американский математик Норберт Винер сумел видоизменить доказательство таким образом, чтобы избежать применения комплексных чисел в узловых моментах проводимых рассуждений. Но все же доказательство теоремы о распределении простых чисел остается слишком сложным для того, чтобы его можно было предложить начинающему. Мы вернемся к этому вопросу на стр. 548 и следующих.

d) Две еще не решенные задачи о простых числах

Если проблема распределения простых чисел («в среднем») была разрешена удовлетворительно, то справедливость ряда других гипотез, эмпирически совершенно несомненная, все еще не доказана.

Сюда относится прежде всего знаменитая гипотеза Гольдбаха. Гольдбах (1690-1764) сам по себе не оставил никакого следа в истории математики: он прославился только проблемой, которую предложил Эйлеру в письме, относящемся к 1742 г. Он обратил внимание на тот факт, что ему всегда удавалось представить любое четное число (кроме 2, которое само есть простое число) в виде суммы двух простых. Например,

Гольдбах спрашивал у Эйлера, может ли он доказать, что такого рода представление возможно для всякого четного числа, или же, напротив, сможет указать пример, опровергающий такое предположение. Эйлер так и не дал ответа; не дал его никто и в дальнейшем. Эмпирическая очевидность гипотезы Гольдбаха, как легко проверить, вполне убедительна. Источник же возникающих затруднений — в том, что понятие простого числа определяется в терминах умножения, тогда как сама проблема касается сложения. Вообще, находить связи между мультипликативными и аддитивными свойствами чисел очень трудно.

До недавнего времени доказательство гипотезы Гольдбаха казалось задачей совершенно неприступной. Сегодня дело обстоит уже не так. Очень значительный успех, оказавшийся неожиданным и поразительным для всех специалистов по данному вопросу, был достигнут в 1931 г. тогда неизвестным молодым русским математиком Шнирельманом (1905-1938), который доказал, что всякое целое положительное число может быть представлено в виде суммы не более чем 800 000 простых. Хотя этот результат и производит несколько комическое впечатление (по сравнению с первоначально поставленной целью доказать гипотезу Гольдбаха), тем не менее он представлял первый шаг в должном направлении. Доказательство Шнирельмана — прямое и носит конструктивный характер, хотя и не обеспечивает практического метода для представления произвольного целого числа в виде суммы простых. Еще позднее русский же математик Виноградов, пользуясь методами Гарди, Литтлвуда и их поистине великого сотрудника по работе индуса Рамануджана, сумел понизить число слагаемых в формулировке Шнирельмана с 800 000 до 4. Это уже гораздо ближе к решению проблемы Гольдбаха. Но существует очень резкое различие между результатами Шнирельмана и Виноградова: более резкое, чем различие между числами 800 000 и 4. Теорема Виноградова была им доказана лишь для всех «достаточно больших» чисел; точнее говоря, Виноградов установил существование такого числа что всякое целое число может быть представлено в виде суммы четырех простых чисел. Метод Виноградова не позволяет никак судить о величине в противоположность методу Шнирельмана он — существенно «косвенный» и неконструктивный. По существу Виноградов доказал следующее: допуская, что существует бесконечное множество чисел, не представимых в виде суммы четырех (или менее того) простых чисел, можно получить противоречие. Здесь перед нами прекрасный пример, показывающий глубокое различие между двумя типами

доказательств — прямым и косвенным (см. общее обсуждение этого вопроса на стр. 49).

Следующая проблема, еще более любопытная, чем проблема Гольдбаха, нисколько не приблизилась к своему разрешению. Было подмечено, что простые числа нередко встречаются парами в виде Таковы 3 и 5,11 и 13, 29 и 31 и т. д. Предположение о существовании бесконечного множества таких «близнецов» кажется весьма правдоподобно, но до сих пор не удалось даже приблизиться к его доказательству.