4.3 ПРОСТЫЕ ПРИМЕРЫ

Сколько всего простых чисел? Много. На самом деле — бесконечно много. Это давным-давно доказал Евклид в своем предложении 20 книги IX, и вот как. Предположим, что имеется лишь конечное число простых, скажем, к чисел Тогда, говорил Евклид, следует рассмотреть число

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

Евклидово доказательство наводит на мысль определить рекуррентно числа Евклида:

Их последовательность начинается с чисел

все из которых простые. Но уже следующее число, есть Оказывается, что простое число, в то время как

Известно, что — составные числа, так же как, по всей видимости, и остальные . Однако все числа Евклида являются попарно взаимно простыми, т. е.

Алгоритм Евклида (а как иначе?) подтверждает это за три коротких шага: поскольку при то

Следовательно, если положить равным наименьшему множителю числа при каждом то все простые числа будут различны — они образуют бесконечную последовательность простых чисел.

Теперь ненадолго отвлечемся, чтобы рассмотреть числа Евклида с позиций гл. 1. Можно ли выразить числа в замкнутой форме? Рекуррентность (4.16) можно упростить, избавившись от многоточия. Если то

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

А в упр. 60 обосновывается подобная этой формула

которая доставляет только лишь простые числа при некоторой постоянной Р. Но на самом деле формулы типа (4.17) и (4.18) не могут рассматриваться как формулы в замкнутой форме, поскольку постоянные Е и Р вычисляются по тем же самым числам бы заметая проблему под ковер. Не известно (и его существование маловероятно) какое-либо соотношение, которое связывало бы эти числа с другими математически важными постоянными.

И, действительно, никто не знает никакой полезной формулы, которая бы давала сколь угодно большие простые, но только простые числа. Тем не менее, проводя в испытания нового суперкомпьютера специалисты из геологической компании Chevron Geosciences все-таки наткнулись на математический клад. Используя программу, которую разработал Дэвид

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

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

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

— простое, как и везде в этой главе) называются числами Мерсенна, в честь преподобного Марена Мерсенна, который еще в семнадцатом веке занимался исследованием некоторых свойств подобных чисел [218]. Известные к настоящему времени простые числа Мерсенна получаются при .

Число всегда не простое, если — составное, поскольку имеет одним из сомножителей :

Однако не всегда простое число, если — простое: — наименьшее из таких не простых чисел. (Мерсенн знал это)

В наши дни разложение на множители и испытание на простоту больших чисел — темы оживленных исследований. Сводка того, что было известно об этом вплоть до содержится в разд. 4.5.4 книги [140], а тем временем становятся известными многие новые результаты. На (русского перевода) объясняется специальный метод проверки на простоту чисел Мерсенна.

На протяжении последних пяти столетий наибольшим известным простым числом оказывается, по большей части, простое число Мерсенна, хотя известно всего лишь несколько десятков простых чисел Мерсенна. Многим не дают покоя большие числа, но они поддаются исследованию с трудом. Поэтому тем, кто рассчитывает на действительно заслуженную известность (а не просто на везение) и место в Книге мировых рекордов Гиннесса, вместо

этого можно было бы попытать счастья с числами вида при малых к, скажем, 3 или 5. Эти числа могут быть проверены на простоту почти столь же быстро, сколь и числа Мерсенна (подробности см. в упр. 4.5.4-27 книги [140]).

Но мы еще не полностью ответили на наш первоначальный вопрос относительно того, сколько имеется простых чисел. Их бесконечно много, но дело в том, что одни бесконечные множества „гуще" нежели другие. Так, среди целых положительных чисел бесконечно много четных чисел и бесконечно много полных квадратов, хотя с некоторых не лишенных смысла точек зрения четных чисел больше, чем полных квадратов. Одна из таких точек зрения — сравнить величину: целое четное — это полный квадрат — это так как гораздо меньше при большом то целое четное встречается значительно раньше, чем полный квадрат, так что можно считать, что целых четных чисел много больше, чем полных квадратов. Сходная точка зрения — сравнить число величин, не превосходящих имеется таких целых четных чисел и таких полных квадратов; а поскольку гораздо больше при большом х, то снова можно считать, что целых четных чисел много больше.

Но что же можно сказать о простых числах с этих двух точек зрения? Оказывается, что простое число приблизительно в раз больше натурального логарифма :

(Знак может быть прочитан как „асимптотически равно" — это значит, что предел отношения равен 1, когда стремится к бесконечности.) Подобно этому, для числа — простых чисел, не превосходящих х, мы располагаем фактом, который известен как „теорема о распределении простых чисел":

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

Эти формулы, справедливые только в пределе при или могут быть заменены более точными оценками. Так, Россером и Шенфельдом [263] установлены следующие удачные границы:

Если выбрать „случайное" целое число то его шансы оказаться простым составляют примерно один к Так, если выбирать числа вблизи 1016, то мы должны проверить примерно и 36.8 из них, прежде чем найдем простое число. (Оказывается, что между 1016 — 370 и 1016 — 1 имеется ровно 10 простых чисел.) Тем не менее в распределении простых чисел имеется много нерегулярностей. Так, числа между включительно — абсолютно все составные. Известно много примеров „парных простых чисел" однако никто не знает, бесконечно много или нет пар таких простых чисел. (См. Харди и Райт [335, § 1.4 и §2.8].)

Один из простых способов подсчитать все простых чисел — просеять их через так называемое „решето Эратосфена" Сначала выписываются все целые числа от 2 до х. Затем обводится число 2, т. е. оно выделяется в качестве простого, и вычеркиваются все другие числа, кратные 2. Затем последовательно обводятся наименьшие из необведенных и невычеркнутых чисел и вычеркиваются все кратные им. Когда все окажется обведенным или вычеркнутым, обведенные числа — суть простые. Если, например, то выписываются числа от 2 до 10, обводится число 2 и вычеркиваются кратные ему числа 4, 6, 8 и 10. Затем наименьшим необведенным, невычеркнутым числом оказывается число 3, поэтому оно обводится и вычеркиваются числа 6 и 9. Теперь наименьшим является число 5, так что оно обводится и вычеркивается число 10. В заключение обводится число 7. Обведенные числа суть 2, 3, 5, 7 — вот вам простых числа, не превосходящих 10.