3. Сколько существует простых чисел?

Чтобы ответить на этот вопрос, мы докажем следующую теорему.

Теорема 3. Если натуральное число то между содержится по меньшей мере одно простое число.

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

Итак, для каждого натурального числа существует простое число, большее его. Отсюда следует, что простых чисел бесконечно много, об этом знал уже Евклид. В частности, отсюда следует, что существует простое число, имеющее (в десятичной системе счисления) по крайней мере тысячу цифр. Однако ни одного такого числа еще в 1960 г. мы не знали. Наибольшее известное тогда простое число имело 969 цифр. (Подробнее об этом числе будет сказано в § 25.)

Стоит подчеркнуть, что в течение последнего десятилетия здесь наблюдался значительный прогресс. К началу 1951 г. наибольшим известным простым числом было число , имеющее 39 цифр (то, что это число простое, было доказано уже в 1876 г.). В настоящее же время наибольшим известным простым числом является число , имеющее 1332 цифры.

В связи с теоремой 3 заметим, что в 1850 г. П. Л. Чебышев доказал более сильную теорему (так называемый постулат Бертрана), согласно которой для натуральных содержится хотя бы одно Простое число. Отсюда следует, что в теореме 3 число можно заменить числом . В настоящее время имеется элементарное доказательство этой теоремы, оно довольно длинное. Можно также доказать, что для натуральных между содержатся по меньшей мере два простых числа.

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

и, следовательно, каждое из чисел имеет по цифр.

Для мы имеем четыре однозначных простых числа: 2, 3, 5 и 7. Двузначных простых чисел имеется 21, трехзначных — 143. Существуют хотя бы три простых числа, имеющие по сто цифр каждое. Недавно Р. М. Робинзон нашел такие числа:

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