ax ² + bx + c генерирует бесконечное количество простых чисел.
Теорема Дирихле
Когда я слушал в Тель-Авивском университете курс теории чисел, лектор, профессор Григорий Фрейман, показал нам доказательство следующей теоремы:
Арифметическая прогрессия an + b содержит бесконечное количество простых чисел, если a и b – взаимно простые числа, то есть не имеют общих делителей, больших, чем 1.
Доказательство теоремы Дирихле, названной по имени Густава Лежёна Дирихле (1805–1859), исключительно красиво, но нашему лектору понадобилось для его объяснения четыре занятия, и оно заходит в области математики, лежащие далеко за пределами темы этой книги. Поскольку я обещал использовать только основные арифметические операции, я объясню, причем как можно проще, лишь утверждение этой теоремы.
Выберем два взаимно простых числа (то есть два числа, не имеющих общих делителей), например a = 3 и b = 4. Следует помнить, что сами эти числа могут и не быть простыми; они лишь должны быть взаимно простыми по отношению друг к другу. Итак, формула нашей прогрессии имеет вид 3n + 4. Вычислим несколько последовательных членов прогрессии, начиная с n = 1.
Мы получим такую последовательность чисел: 7, 10, 13, 16, 19, 22, 25, 28, 31…
Вы, вероятно, уже заметили, что не все числа в этой последовательности простые. Но теорема Дирихле и не утверждает, что все они должны быть простыми числами. Теорема Дирихле гласит, что в последовательности появится бесконечное количество простых чисел – как и в любой последовательности, для которой aи b – взаимно простые числа. Разумеется, ясно, что в этих же последовательностях появится и бесконечное количество составных чисел. Например, в последовательности 3n + 4 результат, несомненно, будет составным числом каждый раз, когда число n кратно 4.
Кстати говоря, фамилия Лежён Дирихле имеет интересную историю. Семья Дирихле происходила из деревушки Ришлет, расположенной вблизи бельгийского города Льежа. Поэтому его прозвали «юнцом из Ришлет» – le jeune de Richelette[19].
Царство составных чисел
Много лет назад меня назначили преподавателем очень особой программы в рамках Математической школы при Тель-Авивском университете. Профессор Бено Арбель отвечал за выявление старшеклассников с исключительными способностями к математике, а я должен был понемногу учить их и готовить к исследовательской работе параллельно с их школьными занятиями. Основной целью этой программы было дать им возможность получить бакалаврскую или даже магистерскую степень еще до окончания старшей школы или вскоре после него. Я часто давал им решать задачи, которые выбирал из своей личной коллекции Международных математических олимпиад, потому что считаю, что лучше всего развивают именно трудные задачи. Одной из задач, которые я задавал на разминочном этапе, была следующая.
Выпишите 100 последовательных чисел, среди которых не будет ни одного простого числа.
К этому моменту вы, вероятно, уже знаете, что я собираюсь написать дальше. Если вы думаете, что я напишу «попытайтесь немного подумать, прежде чем читать дальше», вы совершенно правы.
Это непростое упражнение. Первым делом вы, несомненно, подумали, что такая сплошная последовательность чисел должна начинаться с весьма большого числа, – мы уже знаем, что среди малых значений не найдется ста последовательных чисел, среди которых не было бы ни одного простого.
Продолжайте думать.
Пока вы думаете, я воспользуюсь этой возможностью, чтобы познакомить вас (или возобновить ваше знакомство) с одним очень важным обозначением, которое упрощает запись и размышления. Разумеется, то, что я ввожу это обозначение именно сейчас, не случайно: оно поможет нам решить эту задачу. Речь идет о символе факториала, который обозначается восклицательным знаком (!). Запись n! обозначает в математике произведение всех чисел от 1 до n, то есть n! = 1 × 2 × 3 × 4 × 5 × … × (n – 1) × n.
Например, 5! = 1 × 2 × 3 × 4 × 5. Однажды один из моих учеников пропустил занятие, на котором я вводил факториалы. Когда он увидел обозначение 5! он назвал его «пять ух!». Сразу же очевидно, что 5! делится на все числа, входящие в произведение. Другими словами, n! делится на все числа от 1 до n.
Добросовестности ради отмечу, что 0! принимают равным 1, чтобы не вносить противоречий в основную формулу определения факториала: n! = (n – 1)! × n.
А теперь попробуем еще раз взяться за нашу задачу.
У вас появились какие-нибудь идеи? Если нет, читайте дальше.
Я надеюсь, что за то время, которое мы провели за разговором о факториалах, вы приблизились к решению. Нет никаких сомнений, что факториалы играют в нем какую-то роль. Но какую?
С какого числа следует начать? Может быть, с 100!? Нет, этот вариант не годится. Ведь следующее число, 100! + 1, вполне может оказаться простым, не так ли?
А вот если… Вы уже видите решение?
Может быть, начать с 100! + 2? Такая идея кажется более привлекательной. Это число делится на 2, поскольку на 2 делятся и 100! и 2; следовательно, оно не может быть простым. Мы на верном пути.
Следующее число, 100! + 3, точно так же делится на 3, и, если продолжать в том же духе… 100! + 100 делится на 100. К сожалению, мы никак не можем немедленно установить, составное ли число 100! + 101.
Решение было так близко. Но увы, между 100! + 2 и 100! + 100 всего 99 чисел. Как жаль! Такая прекрасная идея отправляется в помойку.
Минуточку! В помойку? Ни в коем случае! Ее всего лишь нужно немножко подправить.
Мы можем начать свою последовательность чисел с 101! + 2 и закончить ее на 101! + 101. Тогда мы получим непрерывную последовательность из 100 идущих друг за другом чисел, и все они, вне всякого сомнения, – числа составные.
Очевидно, теперь мы можем найти последовательность чисел любой длины, в которой не будет ни одного простого числа. Например, чтобы получить набор из 1000 последовательных составных чисел, нужно просто начать эту последовательность с 1001! + 2. Из этого, разумеется, следует, что среди по-настоящему больших чисел простые числа будут встречаться все реже и реже{15}.
Еще о частоте простых чисел
По мере увеличения чисел средняя разность двух последовательных простых чисел тоже становится больше. Однако существует теорема, которая устанавливает верхний предел редкости появления простых чисел среди чисел натуральных. Она утверждает, что отношение
где Pi – значение i-го простого числа, приближается к нулю по мере приближения i к бесконечности.
Я переведу это утверждение с математического жаргона на язык понятный и нематематикам. Теорема эта означает, что отношение длины промежутка между простыми числами к самим простым числам становится меньше с увеличением i. Ниже приведен список значений начиная с i = 1. Чтобы было яснее, уточню, что в первой строке i равно 1; следовательно, Pi – это первое простое число, то есть 2, а Pi+1 – второе простое число, то есть 3. Во второй строке i = 2, а простые числа – P2 = 3 и P3 = 5 и так далее.
Как вы видите, значение выражения
имеет тенденцию становиться все меньше и меньше по мере увеличения i (значение этого выражения не уменьшается монотонно; оно лишь проявляет общее снижение с ростом P), потому что при больших простых числах его числитель становится много меньше знаменателя. Это означает, что разность последовательных простых чисел (чисел, стоящих в числителе) растет медленнее, чем значения самих этих чисел, что и приводит к уменьшению отношения. Хотя в первых строках списка есть некоторая нестабильность, если рассмотреть общую тенденцию, можно увидеть, что промежутки между простыми числами становятся все меньше по сравнению с самими этими числами.
Прямая дорога к докторской степени
Несмотря на многолетние исследования, аспектов простых чисел, которых мы не понимаем, все еще гораздо больше, чем понятных нам.
Вот лишь некоторые из (множества) задач, которые, насколько мне известно, до настоящего времени никто не решил. Может быть, вы захотите попытаться найти их решение. Могу вам гарантировать, что, если вы решите даже одну из них, вы немедленно получите докторскую степень по математике и прославитесь. А если вы еще учитесь в школе или университете, решение этих задач принесет вам полное освобождение от всех дальнейших уроков или лекций. Таковы хорошие новости.
Плохие же новости по-настоящему плохи. В том, что никому до сих пор не удалось решить эти задачи, нет ничего случайного. Они исключительно сложны! Трудно представить себе, сколько усилий математики потратили на попытки их решить. «Бесплатных завтраков не бывает», – говорят нам наши экономисты. Я бы еще добавил к этому, что «не бывает и роскошных банкетов, которые обходились бы дешево».
Близнецы, тройняшки, кузены и сексуальные простые числа
Два простых числа считают близнецами, если их разность равна 2. Например, пары (3, 5), (5, 7), (11, 13), …, (431, 433)… – это пары чисел-близнецов.
Бесконечно ли количество простых чисел-близнецов?
Из одного того, что количество простых чисел бесконечно, не следует, что ответ на этот вопрос должен быть утвердительным.