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

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

Теорема. Простых чисел бесконечно много.

Доказательство, которое мы здесь приводим, можно найти в «Элементах» Эвклида как предложение 20 книги IX. Доказываем «от противного». Предположим, множество простых чисел конечно. Это означает, что существует наибольшее простое число; скажем, Другими словами, мы предполагаем, что все числа, большие составные. Однако, как мы видели в предыдущем параграфе, число не может иметь простых делителей меньших или равных Из предположения и последнего утверждения вытекает, что нет простых делителей, т.е. оно само является простым числом. А поскольку мы получаем противоречие с предположением: наибольшее простое число. Итак, простых чисел должно существовать бесконечно много.

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

по одному для каждого простого числа. Естественно, это произведение равно некоторому положительному вещественному числу. Более того, аккуратно перемножая члены произведения, можно показать, что

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

попытаемся привести его к противоречию. Хотя число слагаемых в выражении (5.2) бесконечно, его сумма еще могла бы оказаться конечным числом; например, бесконечная сумма как сумма бесконечной геометрической прогрессии со знаменателем 1/2, равна

Но нетрудно увидеть, что сумма, соответствующая не может быть равной ни одному вещественному числу. Для начала заметим, что

Следовательно,

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

Теперь вернемся к доказательству равенства (5.2). Фактически, нам нужно показать, что произведение (5.1) совпадает с бесконечной суммой (5.2). Напомним, что дробь (при можно интерпретировать как сумму бесконечной геометрической прогрессии со знаменателем

Таким образом, равенство (5.1) можно переписать в виде:

Раскроем скобки в этом произведении. Такую операцию можно сделать двумя способами. Один из них заключается в последовательном перемножении скобок: сначала раскрываем произведение первых двух скобок, затем полученный результат умножаем на третью, и т.д. Это привычный способ, но длинный и малоэффективный. Действительно, мы не знаем точное количество перемножаемых скобок, да и каждая скобка представляет собой бесконечную сумму.

Другой способ, менее привычный, но более грамотный, основан на простом наблюдении: если бы у нас хватило терпения и сил раскрыть скобки первым методом, то мы получили бы бесконечную сумму произведений , по одному сомножителю из каждой скобки (значение показателя говорит о том, что из скобки в качестве сомножителя мы берем 1). Мы не будем объяснять это наблюдение более подробно, поскольку такого сорта утверждения легче осознать самостоятельно, нежели понять их доказательство.

Итак, число из равенства (5.1) представляет собой бесконечную сумму слагаемых вида

Упорядочим эти слагаемые по убыванию. Самым большим будет член затем идет потом после него — и т.д. Как видите, мы получили начало бесконечной суммы (5.2). Нам осталось показать, что число на самом деле совпадает с этой суммой. Для этого необходимо проверить две вещи:

(а) для любого натурального числа среди дробей (5.3) найдется такая, что

(б) каждая дробь вида встречается в бесконечной сумме, представляющей только один раз.

Начнем, как ни странно, с проверки второго утверждения (оно несколько проще). Предположим, что нашлись две разные дроби, равные т.е.

Поскольку числители всех этих дробей равны 1, мы получаем равенство знаменателей:

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

Перейдем к утверждению (а). По основной теореме арифметики любое натуральное число представляется в виде произведения простых сомножителей: С другой стороны, знаменатель каждой из дробей (5.3) — это произведение степеней всех простых чисел: причем их показателями могут быть любые неотрицательные целые числа. Таким образом, чтобы приравнять дробь вида (5.3) числу достаточно выбрать подходящие показатели «Ага! — скажете Вы, — Вот я и поймал педанта-лектора! Как же могут быть равными дроби

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

утверждение (а) также проверено. То есть мы доказали, что произведение (5.1) и бесконечная сумма (5.2) равны одному и тому же числу

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

Вот теперь мы полностью привели доказательство Эйлера бесконечности простых чисел.

Конечно, если бы множество простых чисел было ограничено, жизнь была бы проще, но мир стал бы скучнее. Тот факт, что простых чисел бесконечно много, ставит много интересных проблем. Например, что можно сказать об их распределении? Растет или убывает «плотность» простых чисел, когда мы переходим ко все большим и большим числам? Существует ли возможность измерить эту «плотность»? Наилучший способ точно сформулировать проблему о распределении простых чисел состоит в использовании -функции. Для вещественного положительного числа х обозначим через количество простых чисел, не превосходящих х. Хорошая оценка функции важная задача теории чисел.

Упомяните при математиках о распределении простых чисел, и вы тут же услышите имя Римана. Идеи, рожденные

докасательством Эйлера бесконечности ряда простых чисел, легли в основу работы Б. Римана, ставшей фундаментальным трудом, посвященным функции и родственным вопросам. Эта статья, опубликованная в 1895 году, содержит много интересных очаровательных результатов, часть которых приведена без доказательства. К сожалению, Риман умер от туберкулеза семь лет спустя, не закончив детальную проработку своих доказательств. Эту работу взвалило на свои плечи несколько математиков, в первую очередь Адамар (Hadamard).

Одним результатов усилий Адамара по заполнению пробелов, оставленных Риманом, стало доказательство знаменитой теоремы о простых числах, которая говорит, что

где логарифм по основанию (т.е. натуральный логарифм). Этот результат даже старше работы Римана; его сформулировал Гаусс в качестве гипотезы. Доказан же он был в 1896 году независимо друг от друга Адамаром и де ля Валле-Пуссеном (de la Valle-Poussin).

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

будет величиной порядка . Поскольку в этом случае имеет порядок , то ошибка действительно значительна. Есть много других простых функций, дающих неплохую аппроксимацию функции при больших Одна из них изучается экспериментальным образом в упражнении 11. Подробное обсуждение распределения простых чисел можно найти в [23] и [24] ([Д.10]). История теоремы о простых числах содержится в [7].