ре на Венере: на этой планете есть кратер Жермен.
Простые числа Софи Жермен
Вернемся теперь к простым числам и открытым проблемам.
Простое число p называется числом Софи Жермен, если 2p + 1 – также простое число{18}. Вот несколько примеров простых чисел Жермен: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89… Например, число 5 входит в этот список, потому что 2 × 5 + 1 = 11, а 11 – простое число. А вот число 7 в него не входит, потому что 2 × 7 + 1 = 15 (а 15 – число составное).
Умудренный читатель, наверное, уже может догадаться, какую задачу до сих пор никому не удалось решить: бесконечно ли количество простых чисел Жермен? Да, на этот вопрос ответа нет. Однако можно придумать и несколько других интересных задач.
Подумайте, не торопитесь.
Рассмотрим последовательность чисел 2, 5, 11, 23, 47. Число 2 – простое число Жермен. Умножив его на 2 и прибавив единицу, мы получим простое число 5, которое также относится к простым числам Жермен и приводит нас к 11, которое также относится к простым числам Жермен и приводит нас к 23, которое также относится к простым числам Жермен и приводит нас к 47. Тут, однако, эта цепочка заканчивается, потому что 2 × 47 + 1 = 95, а это число составное. Таким образом, эта последовательность состоит из четырех чисел Жермен и еще одного простого числа.
Такого рода последовательности простых чисел Жермен называются цепочками Каннингема по имени британского военного и математика Алана Дж. Каннингема (1842–1928).
Вот еще несколько задач:
• Существуют ли более длинные цепочки? На самом деле да. Мой домашний компьютер совершенно обессилел, но сумел выдать следующий скромный пример цепочки из шести чисел: 89, 179, 359, 719, 1439, 2879.
• Существуют ли цепочки любой длины?
• Что будет, если заменить 2p + 1 на 2p – 1?
• Имеет ли смысл исследовать выражения 4p + 1 или 4p – 1?
Ха! Задавать-то сложные вопросы легко!
Загадка Гольдбаха, или Кто хочет стать миллионером?
В 1742 г. произошло несколько важных событий. Иоганн Себастьян Бах сочинил «Вариации Гольдберга» (нет почти ни одного настоящего математика, который бы не боготворил это произведение), поэт Эдуард Юнг написал «Ночные размышления о жизни, смерти и бессмертии», в Перу восстали индейцы. А 7 июня этого года почти никому не известный прусский математик Христиан Гольдбах написал письмо великому швейцарскому математику (с которым мы сталкиваемся снова и снова) Леонарду Эйлеру.
Эйлер и по нынешний день остается самым плодовитым математиком в истории – его наследие составляет около 80 томов трудов в разных областях математики. Наивысшим достижением Гольдбаха была служба учителем русского царя Петра II (внука Петра Великого). Хотя один из них был из Пруссии, а другой – из Швейцарии, и Эйлер, и Гольдбах работали в Санкт-Петербургской академии наук, основанной Петром Великим.
В письме к Эйлеру Гольдбах выдвинул гипотезу, известную теперь под названием «гипотеза Гольдбаха». Она представляет собой одну из самых старых и самых известных открытых проблем теории чисел, да и всей математики. Эта гипотеза утверждает, что любое четное целое число начиная с 4 может быть представлено в виде суммы двух простых чисел (так звучит современная формулировка гипотезы). Например, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5… Бо́льшие четные числа часто можно записать в виде суммы двух простых чисел не одним, а несколькими способами. Например, 40 = 3 + 37 = = 11 + 29 = 17 + 23.
Рассмотрим число 1742, то есть номер года, в котором была выдвинута эта гипотеза. Попробуем, например, такой вариант: 1742 = 13 + 1729.
Заметили ли вы, кстати говоря, что 1729 – это тот самый номер такси, на котором Харди приехал навестить больного Рамануджана? Так вот, сложение 1729 с несчастливым числом 13 дает 1742. Есть только одна крупная неувязка: 1729 (как вы уже должны знать) – число составное: 1729 = 19 × 91. Разумеется, мы с легкостью можем найти другие решения, например, 1742 = 19 + 1723 или 1742 = 43 + 1699… Проверьте, простые ли все эти числа! Вы также можете предложить свои собственные варианты разложения 1742 на два простых слагаемых.
При всем уважении к многочисленным открытым проблемам, касающимся простых чисел, о которых мы говорили до этого, гипотеза Гольдбаха, несомненно, самая знаменитая из них. Гипотеза о простых числах-близнецах занимает лишь второе место. Все же остальные задачи далеко отстают от этих двух по части известности и интереса, который они вызывают.
В 2000 г. была опубликована книга греческого математика-вундеркинда Апостолоса Доксиадиса «Дядя Петрос и проблема Гольдбаха». Издатель Тоби Фабер предложил приз миллион долларов любому, кто решит задачу Гольдбаха в течение двух лет после выхода книги[24]. Это был настоящий шедевр маркетинга – максимальная шумиха при минимальном риске, – и действительно, претендентов на этот приз не нашлось. Так что теперь тому, кто решит эту задачу, придется удовольствоваться гораздо более скромным (хотя и гораздо более почетным) призом, который назначил Пал Эрдёш.
Решение задачи Гольдбаха, когда и если оно наконец будет найдено, может появиться с двух разных сторон: либо будет открыто четное число, которое невозможно представить в виде суммы двух простых чисел (что называется опровержением, или контрпримером), либо кто-нибудь обоснует причину, по которой все четные числа можно представить таким образом. Пока что было исследовано огромное множество четных чисел (до 1018), и все они могут быть записаны в виде суммы двух простых чисел. Тем не менее это ничего не значит. Даже если мы проверим все до единого четные числа вплоть до 1 000 000 000 000 000! (а это квадриллион факториал!) и выясним, что все они до единого могут быть представлены в виде суммы двух простых чисел, вполне может оказаться, что следующее же четное число, 1 000 000 000 000 000! + 2, станет первым исключением из действовавшего в наших результатах правила и опровергнет гипотезу.
В книге «Гёдель, Эшер, Бах: эта бесконечная гирлянда» Дуглас Хофштадтер предлагает рассмотреть следующую вариацию гипотезы Гольдбаха: можно ли представить любое четное число в виде разности двух простых чисел? Интересно, нельзя ли назвать эту гипотезу «вариацией Гольдбаха – Гольдберга»?
Начнем с начала: 2 = 5 – 3, 4 = 7 – 3, 6 = 11 – 5, 8 = 11 – 3. Разумеется, для некоторых чисел существует несколько вариантов: 10 = (41 – 31) = = (29 – 19) = (23 – 13) = (17 – 7) = (13 – 3).
Несмотря на ярко выраженное сходство этих двух задач, между ними есть фундаментальное различие. Рассматривая исходный вариант гипотезы Гольдбаха, мы можем запустить для любого четного числа компьютерную программу, которая проверит, дает ли это значение сумма двух простых чисел, причем сделает это за конечное время. Даже если такое число очень велико, мы можем быть уверены, что к какому-то моменту программа завершит работу – даже если мы сами до этого момента и не доживем. Во втором же варианте нет никакой гарантии, что компьютер когда-либо закончит свои вычисления. Возьмем произвольное число – скажем, 2010. Абсолютно невозможно определить заранее, когда компьютер закончит вычисления (и закончит ли их когда-либо), потому что, даже если мы проверим все до единого простые числа, скажем, до 12 345 678 910 и не найдем пары простых чисел, разность которых равна 2010, это не значит, что мы не найдем такой пары в будущем. Я использовал здесь число 2010 только для иллюстрации этой идеи. На самом деле компьютеру не составит особого труда выяснить, что число 2010 может быть выражено в виде разности двух простых чисел, например 2017 – 7, 2029 – 19, 2039 – 29 и других. Во всяком случае, эта задача радикально отличается от проверки возможности выражения числа 2010 в виде суммы двух простых чисел (что, как вы уже знаете, возможно: самый простой из нескольких существующих вариантов – 2003 + 7).
Различие состоит в следующем: при поиске ответа в отношении суммы существует конечное число возможностей: нужно лишь проверить все простые числа, меньшие самого искомого числа. В случае 2010 необходимо исследовать только лишь все простые числа до 2007 (самого большого простого числа до 2010). Даже если бы мы взяли не 2010, а 2010! это число все равно было бы конечным, и программа в конце концов пришла бы к тому или иному выводу, проработав в течение конечного времени (более долгого, чем кажется, но тем не менее конечного).
Когда же мы ищем ответ в отношении разности, количество чисел, больших заданного числа, бесконечно. Следовательно, количество разностей, которые, возможно, придется проверить, не ограничено, и может случиться так, что этот процесс не завершится никогда.
Харди хвалит Ферма
Пьер де Ферма (1607–1665) открыл одно интересное обстоятельство, связанное с простыми числами; оно называется «рождественской теоремой Ферма»[25]. Он показал, что любое простое число вида 4n + 1 (например, 5, 13, 17, 29…) есть сумма двух квадратов, а любое простое число вида 4n – 1 (например, 3, 7, 11, 19…) не может быть представлено в виде суммы двух квадратов. Каждое простое число, кроме 2, – либо число вида 4n + 1, либо число вида 4n – 1 (докажите это утверждение самостоятельно). Например, 41 – простое число вида 4n + 1 (4 × 10 + 1), и его можно представить в виде суммы двух квадратов (5² + 4²). А вот 19 – простое число второго вида (4 × 5 – 1), и его невозможно представить в виде суммы двух квадратов. Хотя показать, что, например, число 19 не является суммой двух квадратов, легко, доказать рождественскую теорему Ферма в общем случае не так-то просто.