Владимир Успенский – Апология математики (сборник статей) (страница 19)

В свои «Начала» Евклид поместил следующую теорему: если число 2^p − 1 является простым, то число 2^p−1 (2^p − 1) является совершенным. Например, число 2³ – 1 простое, и в соответствии с теоремой Евклида число 28 = 2^3–1 (2³–1) является совершенным. Заметим, что 2^p − 1 может быть простым только при простом p. В самом деле, если p = r · s, r > 1, s > 1, то, как известно из курса средней школы, выражение 2^r·s – 1 = (2^r)^s – 1 делится на 2^r – 1. Однако обратное неверно: из простоты числа p не следует простота числа 2^p – 1; так, 2¹¹ – 1 = 23 · 89.

Более чем через тысячу лет после Евклида, примерно в 1000 г. н. э., великий арабский учёный Ибн аль-Хайсам (965–1040) высказал гипотезу, что всякое чётное совершенное число имеет вид 2^p−1 (2^p – 1), где число 2^p − 1 является простым. И действительно, совершенное число 496, например, представимо в виде 2^5–1(2⁵ – 1). Лишь в 1747 г. великий швейцарско-российский математик Леонард Эйлер сумел доказать гипотезу Ибн аль-Хайсама. Тем самым было установлено взаимно однозначное, т. е. однозначное в обе стороны, соответствие между чётными совершенными числами и простыми числами вида 2^p − 1: каждому простому числу названного вида однозначно соответствует чётное совершенное число, и наоборот, каждому чётному совершенному числу однозначно соответствует простое число вида 2^p − 1.

Из сказанного видно, что числа вида 2ⁿ – 1 представляют специальный интерес. Они названы числами Мерсенна в честь французского монаха Марена Мерсенна (Marin Mersenne, 08.09.1588–01.09.1648), теолога, философа, математика, акустика и теоретика музыки. В честь Мерсенна принято также и обозначение: число 2ⁿ – 1 обозначается M_n. Таким образом, теорему Евклида – Эйлера можно записать так: чётное число тогда и только тогда является совершенным, когда оно представимо в виде 2ⁿ⁻¹ M_n, где M_n – простое.

Марен Мерсенн был личностью замечательной. Ему принадлежат серьёзные работы по акустике колеблющейся струны. Но главное, в первой половине XVII в. он был центральной фигурой и координатором исследований в области естествознания и математики в Европе. По замечанию Паскаля, Мерсенн имел уникальный талант ставить новые научные проблемы, а не разрешать их. Он создал научный кружок, к которому принадлежали многие выдающиеся учёные того времени, в том числе математики Декарт, Дезарг, Паскаль.

Из этого кружка уже после смерти Мерсенна, в 1666 г., выросла Французская академия наук. Не меньшее значение имела переписка, которую Мерсенн вёл с большинством светил европейской науки XVII в. (в том числе, например, с Галилеем и Торричелли). Практически только из переписки Мерсенна с Ферма, изданной уже после смерти последнего, мы знаем об открытиях этого великого математика и физика. Необходимо учесть, что при отсутствии научных журналов – а первый такой журнал вышел лишь в 1665 г. – их роль выполняли кружки и переписка.

Разумеется, когда Мерсенн занялся числами, ныне носящими его имя, они так не назывались. Его вклад заключался в попытке составить список первых последовательно идущих простых чисел Мерсенна. Этот список, включавший 11 чисел, страдал значительными погрешностями. Так, последним в нём стояло число M₂₅₇, каковое – как и число M₆₇, включённое Мерсенном в свой список, – оказалось составным.

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

Другой недостаток, о котором мы обещали сказать, состоит в неполноте списка. Некоторые простые числа были в нём пропущены. В 1883 г. сельский священник Пермской губернии Иван Михеевич Первушин доказал, что число М₆₁, квалифицированное Мерсенном как составное и потому не вошедшее в его список, на самом деле является простым. Это была первая демонстрация неполноты списка Мерсенна: число М₆₁ явилось первым примером простого числа, пропущенного автором списка, и ввиду этого получило наименование числа Первушина (Pervushin's number). За это и другие достижения в теории чисел Первушин был избран членом-корреспондентом Санкт-Петербургской, Неаполитанской и Французской академий наук, членом Московского и Казанского математических обществ.

Число Первушина, записываемое в десятичной записи как 2 307 843 009 213 693 951, оказалось вторым по величине найденным простым числом. Первым по величине было число M₁₂₇, стоявшее в списке Мерсенна предпоследним; его простота была подтверждена в 1876 г. Второе место число Первушина удерживало вплоть до 1911 г., когда было доказано, что число M₈₉ – простое.

Иван Михеевич Первушин [21.01 (02.02) 1821 – 17 (30).06.1900] достоин того, чтобы о нём рассказать подробнее. В 1838 г. он поступил в Пермское духовное училище, в 1842 г. был переведен в Пермскую духовную семинарию, где впервые и обнаружилась его склонность к занятиям математикой. С переходом его в 1848 г. в Казанскую духовную академию пристрастие к математике усилилось, и присутствовавший на экзамене в академии П. Л. Чебышёв просил обратить внимание на молодого человека. На первых порах всё шло хорошо. По окончании академии Первушин был направлен в семинарию, которую окончил, где стал преподавать математику. Однако с 1856 г. и до своей кончины с небольшим перерывом на служение в уездном городе Шадринске Первушин был сельским священником. Известный уральский краевед Владимир Павлович Бирюков писал, что назначение лица, окончившего духовную академию, в сельскую церковь можно сравнить с назначением профессора учителем деревенской школы. Причину «административной ссылки» Бирюков видит в прямом и насмешливом характере Первушина.

Конечно или бесконечно множество простых чисел Мерсенна? Этот вопрос, как мы знаем, равносилен вопросу о конечности или бесконечности множества чётных совершенных чисел и потому ждёт своего ответа. На октябрь 2014 г. было известно 48 простых чисел Мерсенна – ровно столько же, сколько известно чётных совершенных чисел. Наибольшее найденное простое число Мерсенна – это число М57885161. Оно и было наибольшим найденным к тому времени простым числом.

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа. Один из рекордов поставил в своё время Эйлер, найдя простое число 2³¹ – 1 = 2 147 483 647.

Наибольшим известным простым числом по состоянию на август 2017 г. является 2^{74 207 281} – 1. Его нашли 17 сентября 2015 г. в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS[33], однако все проверки завершились лишь 7 января 2016 г. В этот день в 22 часа 30 минут Всемирного координированного времени (UTC), когда в Москве было уже половина третьего ночи 8 января, проект GIMPS отметил двадцатую годовщину своего существовании открытием нового простого числа, наибольшего из известных. Это было число Мерсенна M_74207281, содержащее в своей записи 22 338 618 десятичных знаков. За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF[34] назначила денежные призы соответственно в 150 000 и 250 000 долларов США. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

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

Каждое число n, кроме единицы, имеет хотя бы один простой делитель. Доказать этот факт весьма просто. Возьмём какое угодно число n, большее единицы. Среди делителей нашего числа n заведомо присутствуют числа, отличные от единицы: например, само число n. Составим список всех отличных от единицы делителей числа n, выберем из них наименьший (т. е. самый маленький) и как-нибудь его обозначим: например, q. Вот это q и будет тем простым делителем числа n, который мы ищем. Мы уже знаем, что q отлично от единицы. Осталось убедиться, что q не делится ни на что, кроме единицы и самого себя. Возьмём какое-то отличное от единицы число x, на которое делится q, и покажем, что оно равно q. В самом деле, это x служит делителем числа q, а q служит делителем числа n; значит, x также служит делителем числа n (см. раздел «Напоминание: делимость, чётность и простота»). Значит, оно входит в составленный нами список и потому не может быть меньше, чем наименьший член этого списка, каковым является q. Вместе с тем x, будучи делителем числа q, не может быть больше, чем q (см. раздел «Напоминание: делимость, чётность и простота»). Для x остаётся одна возможность – совпасть с q.

Ещё в III в. до н. э. в «Началах» Евклида было доказано, что среди простых чисел нет наибольшего: их ряд 2, 3, 5, …, 829, 839, 853, …, 2797, 2801, 2803, … никогда не кончается; иными, современными, словами, совокупность простых чисел бесконечна. Предложение 20 книги IX «Начал» гласит, что простых чисел больше, чем в любом предъявленном списке таковых; доказательство же этого предложения состоит в описании способа, позволяющего для любого списка простых чисел указать простое число, в этом списке не содержащееся. Отметим, что Евклид нигде не говорит о совокупности всех простых чисел в целом – само представление о бесконечных совокупностях как об особых сущностях появилось значительно позже.