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

В качестве завершения темы снова вернусь в 1950-е гг. Посетителя редакции на Большой Калужской мне довелось увидеть ещё один раз, теперь уже на третьем этаже дома 9 по Моховой улице, в канцелярии мехмата, на котором я тогда учился. Всё с той же скрипкой в авоське он вошёл в канцелярию, попросил лист бумаги и, примостившись у стола, стал писать. Не в силах сдержать любопытства, я заглянул ему через плечо. Каллиграфическим почерком он вывел: «Бывшего студента… императорского университета прошение…» (какого именно университета, не помню). Затем попросил указать ему специалиста по теории чисел. В качестве такового ему был назван заведующий кафедрой теории чисел член-корреспондент Гельфонд. В это время по коридору шёл член-корреспондент Гельфанд, к теории чисел отношения не имеющий. Услышав его фамилию, бывший студент императорского университета бросился к нему навстречу. Всем было известно, что Гельфанд – математик великий, но человек непредсказуемый и легко может нахамить. Я не стал дожидаться катастрофического столкновения двух тел и в страхе убежал.

Глава 3

Проблемы нерешённые и проблемы нерешимые

Проблема – это всегда требование что-то найти, указать, предъявить. Это «что-то» может иметь самую различную природу; этим «чем-то» может быть ответ на заданный вопрос, законопроект, доказательство теоремы, число (при решении уравнений), последовательность геометрических построений (при решении геометрических задач на построение). Опыт математики позволяет провести чёткую грань между проблемами нерешёнными и проблемами нерешимыми. Первые ждут своего решения, вторые же решения не имеют и иметь не могут, у них решения просто-напросто не существует. Вот одна из наиболее знаменитых нерешённых проблем: дать ответ на вопрос, есть ли жизнь на Марсе. А вот два простых примера нерешимой проблемы: указать целое число, квадрат которого равен 17; указать наибольшее целое число.

К числу нерешённых долгое время относилась проблема Ферма. В математике таких проблем много, но понять формулировки абсолютного большинства из них может лишь тот, кто получил специальное образование. Нерешённых проблем с простыми формулировками гораздо меньше. Из них наиболее известны, пожалуй, четыре обсуждаемые ниже проблемы теории чисел: две проблемы совершенных чисел и две – чисел простых. Теория чисел (в ортодоксальном понимании этого термина) занимается только положительными целыми числами. Поэтому только такие числа разумеются в данной главе под словом «число». Желание сделать текст понятным как можно более широкому кругу читателей побуждает нас для начала напомнить некоторые определения и факты, каковые теоретически должны быть известны из курса средней школы.

Напоминание: делимость, чётность и простота

Некоторые числа нацело делятся на другие. Предлагаем читателю дать по возможности строгую, недвусмысленную формулировку того, чтó это значит – число a делится на число b. Математик ответит так: говорят, что (вариант: по определению) число a делится на число b, если (вариант: коль скоро) существует такое число s, которое в произведении с числом b даёт число a:

a = b · s.

Например, 48 делится на 1, 2, 3, 16, 48 и ряд других чисел. Всякое число делится на единицу и на само себя (почему?). Выражение «a делится на b» имеет тот же смысл, что и «b является делителем числа a»; так что 1, 2, 3, 16, 48 и некоторые другие числа являются делителями числа 48. Ясно, что делитель не может быть больше того числа, делителем которого он является. Если a делится на b, а b делится на c, то и a делится на c. Попробуйте это доказать исходя из определения слова «делится». Никакие два соседних числа (т. е. n и n +1) не могут делиться на одно и то же число, кроме как на единицу (почему?). Числа, делящиеся на 2, называются чётными, все остальные – нечётными. В натуральном ряду 1, 2, 3, 4, 5, 6, 7,… нечётные и чётные числа чередуются друг с другом. Сумма любого количества чётных чисел есть чётное число (почему?). А вот при суммировании нечётных чисел чётность результата зависит от чётности количества слагаемых: если это количество чётно, то и сумма будет чётным числом, а если оно нечётно, то и сумма окажется нечётной (почему?).

Число называется простым, если обладает двумя свойствами: во-первых, оно больше единицы; во-вторых, оно не имеет других делителей, кроме единицы и самого себя. Вот первые 7 простых чисел: 2, 3, 5, 7, 11, 13, 17. Упражнение для читателей: найдите несколько следующих простых чисел. (И ещё одно упражнение: ответьте на вопрос, сколько существует чётных простых чисел.) Числа, бóльшие единицы и не являющиеся простыми, называются составными.

Две проблемы о совершенных числах

Число 6 делится на 1, на 2, на 3 и на 6 – эти числа 1, 2, 3, 6 образуют полный список делителей числа 6. Если из этого списка удалим само число 6, а остальные сложим, получим то же самое число 6. Действительно, 1 + 2 + 3 = 6. Тем же свойством обладает число 28. Его делителями служат числа 1, 2, 4, 7, 14, 28, и только они. Если их все, кроме 28, сложить, получим как раз 28: действительно, 1 + 2 + 4 + 7 + 14 = 28. В VI в. до н. э. это редкое свойство чисел вызывало мистический восторг у Пифагора и его учеников: по их мнению, оно свидетельствовало об особом совершенстве числа, обладающего таким свойством. А потому каждое число, совпадающее с суммой всех своих делителей, отличных от самого этого числа, получило титул совершенного. Мистический восторг пифагорейцев перед совершенством совершенных чисел продолжался и в учениях христианских отцов церкви. В V в. Блаженный Августин писал в сочинении «Град Божий»:

Число 6 совершенно само по себе, а не потому, что Господь сотворил всё сущее за 6 дней; скорее, наоборот, Бог сотворил всё сущее за 6 дней потому, что это число совершенно. И оно оставалось бы совершенным, даже если бы не было сотворения за 6 дней.

Пифагорейцы знали только три первых совершенных числа. Первые четыре совершенных числа: 6, 28, 496, 8128 приведены в «Арифметике» Никомаха Герасского[31]. Пятое совершенное число 33 550 336 обнаружил выдающийся немецкий математик, астроном и астролог Региомонтан (XV в.). В XVI в. были найдены ещё два совершенных числа: 8 589 869 056 и 137 438 691 328. В дальнейшем поиск затормозился вплоть до середины XX в., когда с появлением компьютеров стали возможными вычисления, превосходящие человеческие возможности.

Про первые 45 из известных совершенных чисел известно, что они идут без пропусков. Это значит, что если занумеровать совершенные числа в порядке их открытия, то, скажем, между 40-м и 41-м числами совершенных чисел нет. Но про последние четыре открытые числа это неизвестно. Так что между 45-м и 46-м совершенными числами могут оказаться другие совершенные числа, равно как между 46-м и 47-и, между 47-м и 48-м, 48-м и 49-м. Можно сказать, что каждое совершенное число имеет два номера – один абсолютный и другой хронологический. До сих пор мы имели дело с хронологическими номерами – это те номера, которые присваиваются числам в порядке их открытия. Абсолютный номер – это порядковый номер совершенного числа, если совершенные числа выстроить в порядке их возрастания. До 45-го совершенного числа включительно их абсолютные и хронологические номера совпадали. А дальше – неизвестность.

Первые четыре совершенных числа (6, 28, 496 и 8128) были известны уже во II в. н. э. К октябрю 2008 г. было обнаружено 46 совершенных чисел; для записи наибольшего из них требуется 25 956 377 десятичных знаков. К настоящему моменту (август 2017 г.) известно уже 49 совершенных чисел. Самое большое известное совершенное число имеет вид 2^74207280 × (2^74207281 − 1) и содержит в своей записи 44 677 235 десятичных знаков.

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

Может ли случиться, что 49-е совершенное число – последнее не только из найденных к настоящему времени, но вообще из всех существующих? Может быть, оно самое большое из всех и совершенных чисел, бóльших его, уже нет? Никто не знает, эта проблема тоже до сих пор не решена. Однако имеется гипотеза, что в ряду чисел за каждым совершенным числом встретится ещё большее совершенное число, иными словами, совокупность всех совершенных чисел бесконечна. Но пока это только гипотеза. Доказать или опровергнуть гипотезу о бесконечности количества совершенных чисел – это и есть вторая из двух проблем, упомянутых в заголовке этой главки.

Заметим, что на самом деле ищут не сами совершенные числа, а теснейшим образом с ними связанные простые числа Мерсенна, получившие в конце XX в. практическое применение в криптографии и в создании широко используемых в информатике псевдослучайных чисел[32]. О числах Мерсенна – в следующей главке.

Числа Мерсенна. Число Первушина

Биографические сведения о великом древнегреческом математике Евклиде крайне скудны. Считается установленным, что он родился во второй половине IV в. до н. э., а скончался в первой половине III в. до н. э. В историю математики Евклид вошёл благодаря своему прославившему его сочинению, известному в русском переводе под названием «Начала». В нём он собрал и изложил всю известную к тому времени математику. Нас здесь интересует вклад Евклида в теорию совершенных чисел.