Текст книги "Восемь этюдов о бесконечности. Математическое приключение"

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

Числа Мерсенна и Книга рекордов Гиннесса

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

Число, носящее почетный титул «самого большого простого числа, открытого до 2018 г.», равно 2^77 232 917 – 1[17]17
  В декабре 2018 г. было найдено еще большее простое число Мерсенна, равное 2^82 589 933 – 1. В десятичной записи оно содержит 24 862 068 цифр. К моменту выхода настоящего издания вполне могут устареть и эти сведения.


[Закрыть]. Я не советовал бы вам пытаться сосчитать это число и выписать его в тетради: в ней просто не хватит для этого страниц. Если учесть, что количество атомов во Вселенной меньше, чем 2³²⁰, наверное, можно составить некоторое представление о том, насколько огромно число 2^77 232 917 – 1. В нем 23 249 425 знаков – почти на миллион (!) больше, чем в числе, которое считалось самым большим простым числом до него: то было открыто в январе 2016 г., и его значение – 2^74 207 281 – 1 (в этом числе «только лишь» 22 338 618 знаков). При этом число 2³²⁰ всего-то 96-значное. Все относительно!

Кстати говоря, доказательство того, что это чудовищное число относится к простым числам, было получено не живым математиком из плоти и крови, а сетевым вычислительным проектом под названием GIMPS (Great Internet Mersenne Prime Search – «Великий интернет-поиск простых чисел Мерсенна»).

Что же такое «число Мерсенна»? Возможно, правильнее было бы спросить иначе: кто такой Мерсенн? Числа вида 2ⁿ – 1 называют числами Мерсенна в честь французского философа, богослова, музыковеда и математика Марена Мерсенна (1588–1648). Если вам кажется, что перечень его титулов недостаточно впечатляющ, позвольте мне добавить еще один: Мерсенн был первым человеком, измерившим скорость звука.

Все ли числа Мерсенна простые? Вовсе нет.

Например, 2⁴ – 1 = 15 – не простое число (15 = 3 × 5).

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

2⁶ – 1 = 2 ^2 × 3 – 1 = (2² – 1) (2 ⁴ + 2 ² + 1) = 3 × 21[18]18
  Или, если использовать формулу разности квадратов, 2^3 × 2 – 1 = (2³ – 1) (2³ + 1) = 7 × 9.


[Закрыть].

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

2^n · m – 1 = (2ⁿ – 1) (1 + 2ⁿ + 2²ⁿ + … + 2^{(m – 1) · n}).

Если эта формула не кажется вам особенно интересной, не беспокойтесь. Собственно говоря, сама формула не столь важна. Важен тот факт, что если в степенном показателе стоит не простое число, то и число Мерсенна с этим показателем не будет простым. Но если составной показатель гарантирует составное число Мерсенна, дальше, несомненно, естественно задать следующий вопрос: «Гарантирует ли простой показатель, что число Мерсенна будет простым?»

Попробуем проверить.

2² – 1, 2³ – 1, 2⁵ – 1 и 2⁷ – 1 – числа простые (соответственно 3, 7, 31 и 127). Пока что все хорошо. Сле– дующее простое число после 7 – это 11, но 2¹¹ – 1 – это не простое число: 2¹¹ – 1 = 2047 = 23 × 89.

Как ни печально, наличие простого числа в степенном показателе не гарантирует, что соответствующее число Мерсенна тоже будет простым числом. Будь это так, мы бы располагали простым способом находить все новые и новые простые числа. Например, можно было бы взять то колоссальное простое число, о котором мы говорили несколькими строчками выше, использовать его в качестве степенного показателя 2, вычесть единицу и получить новое – и еще более колоссальное – простое число. В его показателе стояло бы число, содержащее более 20 миллионов цифр. Подумайте только, каким ужасающе огромным было бы это число – оно выходило бы за пределы воображения простых смертных. Простое ли это число на самом деле? Я этого не знаю и не думаю, что когда-нибудь узнаю.

Мерсенн исследовал эти числа, носящие теперь его имя, в работе, опубликованной в 1644 г. Она вышла под величественным заголовком «Физико-математические размышления» (Cogitata Physico-Mathematica). Мерсенн проверил все простые степенные показатели до 257 и заключил, что числа вида 2^P – 1 должны быть простыми при P = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257. Правильный перечень немного отличается от этого и выглядит так: P = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127.

Судите сами, можно ли считать процент точных попаданий Мерсенна впечатляющим.

Числа Мерсенна и совершенные числа

Помните совершенные числа, с которыми мы познакомились в разделе, посвященном Пифагору? Если вы уже забыли про них, напомню, что совершенным называется число, сумма собственных делителей которого равна самому числу. Еще Евклид знал, что, если 2^P – 1 – простое число, то его умножение на 2^P – 1 всегда дает совершенное число. Разумеется, Евклид не называл такие числа числами Мерсенна. В его время не только еще не родился сам Мерсенн, но даже не познакомились родители прародителей его прародителей.

Приведем несколько примеров. 2³ – 1 – простое число (7); следовательно, (2³ – 1) × 2² = 28 – число совершенное. Аналогичным образом, 2⁵ – 1 – простое число (31); следовательно, (2⁵ – 1) × 2⁴ = 496 – число совершенное. Воспользовавшись любезной помощью наибольшего из известных на сегодня простых чисел, мы теперь можем построить и самое большое из известных совершенных чисел: (2^77 232 917 – 1) × 2^77 232 916.

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

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

Головоломки для тех, кто изучал математику

1). Докажите, что, если 2^P – 1 – простое число, то число (2^P – 1) × 2^P – 1 должно быть совершенным.

2). 28 – треугольное число.

Являются ли все совершенные четные числа треугольными?

Знаменитый швейцарский математик Леонард Эйлер (с которым мы вскоре познакомимся) доказал, что верно и обратное. Другими словами, любое четное совершенное число имеет форму (2^P – 1) × 2^P – 1, где P и 2^P – 1 – простые числа. Попробуйте свои силы и докажите это утверждение – или же найдите доказательство Эйлера{14}14
  Подсказка: Найдите наибольшую степень 2, на которую делится ваше число. Ее и следует взять в качестве P – 1.


[Закрыть].

Поиски чудотворной формулы

Ну ладно, мы поняли, что простых чисел существует бесконечное количество. После этого логично было спросить, есть ли в их появлении какой-либо порядок. Существует ли формула, дающая только простые числа? Существует ли формула, дающая все простые числа? Как могла бы выглядеть формула количества простых чисел до некоторого числа n?

Не успели мы расстаться с великим швейцарским математиком Леонардом Эйлером (1707–1783), как снова встречаемся с ним.

В 1772 г. Эйлер выяснил, что выражение n² + n + 41 (напомним, что любое выражение вида ax² + bx + c называется квадратным многочленом) дает простые числа при условии, что n меньше 40. Например, для n = 0, 1, 2, 3, 4, 5, 6 мы получаем, соответственно, следующие значения: 41, 43, 47, 53, 61, 71, 83. Отметим, что разности между этими значениями равны 2, 4, 6, 10, 12.

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

А если подумать еще немного, мы поймем, что эта формула не может давать простого числа и при n = 40. Запишем ее в таком виде:

40² + 40 + 41 = 40 (40 + 1) + 41 = 40 · 41 + 41 = 41 (40 + 1) = 41².

Получившееся значение – не только не простое число: это еще и полный квадрат, 1681.

Отметим, что число 1681 обладает одним весьма интересным свойством: это единственное четырехзначное число, которое не только само является полным квадратом, но и состоит из двух частей, 16 и 81, каждая из которых тоже само является полным квадратом (если не учитывать тривиальные случаи чисел вроде 1600).

Примечание. До сих пор не доказано, что какой-либо квадратный многочлен вида 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]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}15
  Теорема о распределении простых чисел утверждает (более или менее) следующее: вероятность того, что число, близкое к n, окажется простым, пропорциональна натуральному логарифму n, деленному на n. Поскольку это отношение стремится к 0 при n, стремящемся к бесконечности, это гарантирует редкость появления простых чисел среди всех натуральных чисел.


[Закрыть].

Еще о частоте простых чисел

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

где P_i – значение i-го простого числа, приближается к нулю по мере приближения i к бесконечности.

Я переведу это утверждение с математического жаргона на язык понятный и нематематикам. Теорема эта означает, что отношение длины промежутка между простыми числами к самим простым числам становится меньше с увеличением i. Ниже приведен список значений начиная с i = 1. Чтобы было яснее, уточню, что в первой строке i равно 1; следовательно, P_i – это первое простое число, то есть 2, а P_i+1 – второе простое число, то есть 3. Во второй строке i = 2, а простые числа – P₂ = 3 и P₃ = 5 и так далее.

Как вы видите, значение выражения

имеет тенденцию становиться все меньше и меньше по мере увеличения i (значение этого выражения не уменьшается монотонно; оно лишь проявляет общее снижение с ростом P), потому что при больших простых числах его числитель становится много меньше знаменателя. Это означает, что разность последовательных простых чисел (чисел, стоящих в числителе) растет медленнее, чем значения самих этих чисел, что и приводит к уменьшению отношения. Хотя в первых строках списка есть некоторая нестабильность, если рассмотреть общую тенденцию, можно увидеть, что промежутки между простыми числами становятся все меньше по сравнению с самими этими числами.

Прямая дорога к докторской степени

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

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

Плохие же новости по-настоящему плохи. В том, что никому до сих пор не удалось решить эти задачи, нет ничего случайного. Они исключительно сложны! Трудно представить себе, сколько усилий математики потратили на попытки их решить. «Бесплатных завтраков не бывает», – говорят нам наши экономисты. Я бы еще добавил к этому, что «не бывает и роскошных банкетов, которые обходились бы дешево».

Близнецы, тройняшки, кузены и сексуальные простые числа

Два простых числа считают близнецами, если их разность равна 2. Например, пары (3, 5), (5, 7), (11, 13), …, (431, 433)… – это пары чисел-близнецов.

Бесконечно ли количество простых чисел-близнецов?

Из одного того, что количество простых чисел бесконечно, не следует, что ответ на этот вопрос должен быть утвердительным.

Триплеты простых чисел: мини-опрос

Перед вами триплет простых чисел{16}16
  Триплет простых чисел – это набор из трех простых чисел вида (p, p + 2, p + 6) или (p, p + 4, p + 6). Это самое тесное из возможных расположений трех простых чисел, так как одно из любых трех последовательных нечетных чисел оказывается кратно трем и, следовательно, не является простым (за исключением самого числа 3) – кроме случаев (2, 3, 5) и (3, 5, 7).


[Закрыть]: (3, 5, 7). Докажите, что это единственная возможная «тройка близнецов».

Простые кузены

Пары простых чисел, разность которых равна 4, – например (3, 7), (7, 11), (19, 23), …, (223, 227), – называют двоюродными простыми числами или кузенами. Бесконечно ли количество таких пар?

Сексуальные простые числа

Пары простых чисел, отличающихся на 6, называются по-английски sexy primes[20]20
  По совпадению латинского слова sex (шесть) со словом «секс» в современных языках. Заметим, что в латыни это слово, по-видимому, не имело никакого отношения к полу (sexus).


[Закрыть], то есть «сексуальными простыми числами». Ну и представления о сексуальности у этих математиков! Вот некоторые из победителей на конкурсе самых сексуальных пар: (5, 11), (7, 13), (11, 17), (17, 23), (23, 29), …, (191, 197)…

Вы только посмотрите, какое тут царит распутство! Партнер числа 5, число 11, состоит в связи еще и с 17, а то заигрывает с 23, а оно изменяет ему с 29. Но число 29 хранит верность 23. Сколько тут сюжетных возможностей для поистине кошмарного любовного романа!

Конечно или бесконечно количество простых чисел-близнецов, простых кузенов или сексуальных пар, никто не знает.

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

Рассмотрим следующий ряд, состоящий только из простых чисел-близнецов:

(1/3 + 1/5) + (1/5 + 1/7) + (1/11 + 1/13) + … + (1/857 + 1/859)…

В 1915 г. норвежский математик Вигго Брун доказал теорему, которая стала знаменитой и носит теперь его имя. В этой теореме Брун показал, что приведенный выше ряд сходится, и его сумма равна приблизительно 1,9 (1,90216…).

Если бы этот ряд расходился, мы бы точно знали, что количество пар чисел-близнецов бесконечно. Однако тот факт, что он сходится, абсолютно ничего не говорит нам о конечности или бесконечности количества пар близнецов.

Если бы мы могли доказать, что сумма этого ряда не может быть выражена дробью – такие числа называются иррациональными, – это также решило бы задачу, так как означало бы, что существует бесконечно много пар простых чисел-близнецов (сумма конечного количества рациональных чисел всегда равна рациональному числу). Однако эта сумма рациональна, что опять же не проливает света на вопрос о бесконечности (или конечности) чисел-близнецов. Вскоре я расскажу нематематикам о рациональных и иррациональных числах.

Ряд для двоюродных простых чисел выглядит так:

(1/7 + 1/11) + (1/13 + 1/17) + (1/19 + 1/23) + …

Он сходится к сумме, приблизительно равной 1,197 (1,1970449…).

Устойчивые простые числа

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


[Закрыть]. Например, простое число 199 стабильно, потому что числа 919 и 991 также являются простыми. 13 – тоже устойчивое простое число, так как оба числа 13 и 31 относятся к простым. Если запустить компьютерную программу по поиску устойчивых простых чисел, обнаружится, что после сравнительно небольшого количества чисел (последнее из которых – 991) устойчивыми, по-видимому, могут быть только простые числа, состоящие из одних лишь повторяющихся единиц. Первое из них – число 1 111 111 111 111 111 111.

И вот вам еще одна открытая проблема: существуют ли устойчивые простые числа, большие 991, но состоящие не только из единиц? Небольшая подсказка: устойчивое простое число может содержать только цифры 1, 3, 7 и 9. Вполне очевидно, что, если в числе содержится цифра 5, то одна из перестановок его цифр даст составное число.