Текст книги "Величайшие математические задачи"

Однако такое правильное и «причесанное» представление о доказательстве – еще не вся история и даже не самая главная ее часть. Это все равно что сказать: симфония – последовательность музыкальных нот, которая подчиняется законам гармонии. Определение верно, но где же творчество? Такое определение ничего не говорит нам не только о том, как искать доказательство, но и о том, как проверить его, когда оно предложено кем-то другим. Это определение ничего не говорит нам о том, какие места в лабиринте важнее других. Не говорит и о том, какие проходы в нем элегантны, а какие безобразны, какие значительны, а какие бесполезны. Это всего лишь формальное, механическое описание процесса, у которого немало и других аспектов, в частности человеческое измерение. Доказательства ищут люди, и математические исследования – отнюдь не воплощение пошаговой логики.

Формальный подход к определению доказательства может породить доказательства почти нечитаемые, поскольку основные усилия придется бросить на копание в мелочах и «расставление точек над логическими i», в то время как решающий вывод будет буквально бросаться в глаза. Поэтому практикующие математики спрямляют путь и оставляют за бортом все рутинные или очевидные шаги. На пропуски обычно указывают фразы вроде «несложно показать, что…» или «из стандартных расчетов следует, что…» Зато ни один математик не пройдет – по крайней мере сознательно – мимо логической трудности и не попытается сделать вид, что ее нет. Более того, компетентный математик постарается обратить особое внимание на слабые с точки зрения логики звенья цепочки рассуждений и потратит бо́льшую часть времени и усилий на то, чтобы укрепить их и сделать достаточно надежными. Дело в том, что на практике доказательство – это математическая история с собственным сюжетом. У нее есть завязка, кульминация и развязка. В ней часто можно обнаружить боковые сюжетные ходы, которые вырастают из основного ствола, но ведут каждый к своему результату. Британский математик Кристофер Зиман однажды заметил, что любая теорема – это своего рода интеллектуальная точка покоя, где можно сделать остановку, перевести дыхание и ощутить некоторую определенность. Побочная сюжетная линия помогает свести концы с концами в основном сюжете. Доказательство напоминает литературный сюжет и в других отношениях: в них часто имеются один или несколько главных героев – конечно, это не люди, а идеи, – сложные взаимоотношения которых ведут к развязке и финалу.

Как явствует из формального определения, доказательство начинается с неких четких предположений, движется шаг за шагом от одного логического вывода к другому и заканчивается выводом о том, что вы, собственно, хотели доказать. Но доказательство – не просто список последовательных умозаключений, и логика в нем – не единственный критерий. Доказательство – это рассказ, который выслушивают и разбирают по косточкам люди, посвятившие большую часть жизни искусству прочтения таких историй и поиска в них ошибок и противоречий. Основная цель этих людей – доказать, что автор доказательства не прав. Эти люди обладают поразительной способностью замечать слабые места и без устали долбить в них, пока вся конструкция не рухнет, подняв облако пыли. Вообще, если какой-нибудь математик заявляет, что ему удалось решить крупную проблему (одну из великих, например, или что-нибудь попроще, но тоже достойное), остальные математики не спешат кричать «Ура!» и открывать шампанское. Профессиональный инстинкт велит им прежде всего постараться опровергнуть предложенное доказательство.

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

Как математики решают задачи? Этот вопрос почти не изучался. Современные образовательные исследования на базе когнитивистики в основном ограничиваются изучением образования от начальной до высшей школы. Есть исследования, посвященные преподаванию математики в вузах, но их не так уж много. Кроме того, есть большая разница между освоением и преподаванием математики и новыми исследованиями в этой области. Многие из нас умеют играть на каком-нибудь музыкальном инструменте, но мало кто способен сочинить симфонический концерт или хотя бы написать популярную песенку.

Когда речь заходит о творчестве на высочайшем уровне, почти все, что мы знаем – или думаем, что знаем, – мы получаем путем самоанализа. Мы просим математиков объяснить ход их мыслей и пытаемся выделить в этих описаниях общие принципы. Одной из первых серьезных попыток понять, как думают математики, можно считать книгу Жака Адамара «Исследование психологии процесса изобретения в области математики»[1]1
  Адамар Ж. Исследование психологии процесса изобретения в области математики. – М.: Советское радио, 1970.


[Закрыть], вышедшую в 1945 г. Адамар расспросил ведущих математиков и физиков своего времени и попросил описать, как они думают в процессе работы над сложной задачей. И тут выявилась важная и даже необходимая роль того, что за неимением лучшего термина следует назвать интуицией. Их мысли направляло нечто подсознательное. Самые плодотворные их идеи и озарения не приходили постепенно, в результате логической пошаговой проработки, а возникали неожиданно, и весь процесс развивался скачкообразно.

Одно из самых подробных описаний этого на первый взгляд нелогичного подхода к логическим вопросам дал французский математик Анри Пуанкаре – один из ведущих ученых конца XIX – начала XX в. Пуанкаре отметился едва ли не во всех областях математической науки, внес радикальные изменения во многие из них и основал несколько новых ее разделов. В последующих главах мы не раз будем возвращаться к его работам. Кроме того, Пуанкаре писал научно-популярные книги, и, возможно, именно огромный опыт и широта кругозора помогли ему глубже понять процесс собственного мышления. Во всяком случае, он был твердо убежден, что осознанная логика – лишь часть творческого процесса. Да, бывают моменты, когда без нее не обойтись: к примеру, без логики невозможно понять, в чем именно состоит проблема, как невозможно и проверить полученный ответ. Но в промежутке, считал Пуанкаре, его мозг нередко работал над задачей самостоятельно, ничего не сообщая хозяину, причем работал так, что хозяин был просто не в состоянии постичь его методы.

Его описание творческого процесса различает три ключевых этапа: подготовка, вынашивание и озарение. Подготовка представляет собой сознательные логические усилия, направленные на то, чтобы увидеть проблему, точно сформулировать ее и попробовать решить традиционными методами. Этот этап, когда подсознание получает задание и материал для работы, Пуанкаре считал очень важным. Вынашивание происходит, когда вы прекращаете думать о задаче, отвлекаетесь от нее и занимаетесь чем-то другим. А подсознание тем временем начинает перебирать и комбинировать идеи, часто довольно дикие, и продолжается это до тех пор, пока вдали не забрезжит свет. Если повезет, результатом станет озарение: подсознание даст вам сигнал, и в вашем мозгу как будто вспыхнет лампочка – возникнет готовый ответ.

Такое творчество подобно хождению по натянутому канату. С одной стороны, вы не можете решить сложную проблему, пока не познакомитесь как следует с областью, к которой она относится, а также с множеством других тем, которые могут пригодиться, а могут и не пригодиться в работе, просто на всякий случай. С другой стороны, если, изучая все нужные области математики, вы обратитесь к стандартному, уже много раз безрезультатно опробованному пути, то, возможно, уже не сумеете выбраться из наезженной колеи и ничего нового не откроете. Фокус в том, чтобы много знать и сознательно собирать свои знания воедино, работать над этим неделю за неделей… а затем отложить проблему в сторону. Тогда за дело возьмется интуитивная часть вашего сознания: она отсмотрит все идеи, повертит их так и эдак, оценит, где «холодно», а где «горячо», и сообщит вам, если что-нибудь найдет. Произойти это может в любой момент: Пуанкаре однажды понял, как нужно решать задачу, мучившую его несколько месяцев, выходя из автобуса. Шриниваса Рамануджан, индийский математик-самоучка, создававший замечательные формулы, часто видел новые идеи во сне. А Архимед, согласно легенде, нашел способ определить содержание золота в сплаве, принимая ванну.

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

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

Зачастую главное, чем помогает в работе интуиция, – она подсказывает, где у задачи слабые места, где к ней можно подступиться с максимальными шансами на успех. Математическое доказательство подобно сражению или, если вы предпочитаете менее воинственные сравнения, шахматной партии. Как только потенциально слабое место выявлено, исследователь бросает в бой (т. е. на его изучение) все свои возможности исследователя, весь математический аппарат, которым владеет. Как Архимед нуждался в точке опоры, чтобы перевернуть Землю, так и математик-исследователь нуждается в рычагах воздействия на задачу. Одна-единственная ключевая идея может раскрыть ее, сделать доступной для стандартных методов. Ну а после этого довести решение задачи до конца – дело техники.

Мой любимый пример рычагов такого рода – задачка, которая не имеет особого математического смысла, но помогает объяснить важный момент. Предположим, у вас есть шахматная доска из 64 клеток и набор костяшек домино, каждая из которых по размеру точно закрывает две соседние клетки доски. Очевидно, 32 костяшек достаточно, чтобы закрыть всю доску. Но теперь представьте, что из доски удалили две противоположных по диагонали угловых клетки, как показано на рис. 1. Можно ли закрыть оставшиеся 62 клетки при помощи 31 костяшки? Попробовав, вы поймете, что ничего не получается. С другой стороны, явных причин, по которым это задание можно было бы счесть невыполнимым, вроде бы тоже не видно. Но ровно до тех пор, пока вы не сообразите, что каждая костяшка домино, как их ни раскладывай, должна закрывать одну черную и одну белую клетку доски. Вот ваш рычаг, и теперь остается только применить его. Он подразумевает, что любая площадь, закрытая костяшками домино, содержит равное число черных и белых клеток. Но противоположные по диагонали клетки – одного цвета (в данном случае – белые), так что при их удалении возникает фигура, в которой черных клеток на две больше, чем белых. А никакую фигуру такого рода полностью закрыть костяшками невозможно. Наблюдение о том, что любая костяшка домино обязательно закрывает две клетки разного цвета, и есть слабое место этой головоломки. Поняв это, вы получаете точку, к которой можно приложить логический рычаг – и нажать. Если бы вы были средневековым бароном и осаждали замок, это стало бы для вас слабым местом замковой стены – местом, где следует сосредоточить огонь требушетов или начать делать подкоп.

Однако в одном существенном моменте математические исследования отличаются от сражения. Любая территория, которую вам однажды удалось оккупировать, остается вашей навсегда, и после этого вы можете сосредоточить усилия на чем-то ином. Но доказанная теорема никуда не исчезает. И именно благодаря этому математики достигают прогресса в решении задачи, даже если дойти до конца им не удается. Однажды установленный факт становится доступен всем, и воспользоваться им может кто угодно и совершенно в любом контексте. Нередко отправной точкой новой атаки на древнюю как мир проблему становится незамеченное ранее сокровище, затерявшееся в целой куче разнообразных фактов. И это одна из причин, по которым любые новые математические расчеты ценны сами по себе, даже если польза от них не видна сразу. Это еще один кусок завоеванной территории, еще одно оружие в арсенале. Возможно, его время еще придет – но этого не случится, если его посчитают «бесполезным» и забудут или просто не дадут увидеть свет, потому что не поймут, какой в нем смысл.

2. Территория простых чисел. Проблема Гольдбаха

Некоторые великие задачи встречаются и в начальном курсе математики, хотя мы этого не замечаем. Вскоре после того, как ребенок осваивает умножение, он знакомится с концепцией простого числа. Известно, что некоторые числа могут быть получены при перемножении двух меньших чисел, к примеру: 6 = 2 × 3. Другие, такие как 5, невозможно разложить подобным образом на сомножители. Максимум, что можно сделать, это записать 5 = 1 × 5, но в этом выражении нет двух меньших чисел. Числа, которые можно разбить на сомножители, называют составными, а те, что разложить невозможно, – простыми. Простые числа кажутся такой несложной темой! Если вы уже умеете перемножать натуральные числа, то способны разобраться и в том, что представляет собой простое число. Простые числа – первичные строительные кирпичики для всех натуральных чисел, и обнаружить их можно в самых разных разделах математики. Но в них есть тайна, и, на первый взгляд, они раскиданы среди положительных целых чисел почти случайным образом. Нет никаких сомнений: простые числа – настоящая загадка. Возможно, это естественное следствие их определения – ведь определяются они не через какое-либо присущее им свойство, а напротив – через свойство, которое у них отсутствует. С другой стороны, для математики это фундаментальное понятие, поэтому мы не можем просто так в ужасе поднять руки и сдаться. Нам необходимо с ними освоиться и каким-то образом вызнать их потаенные секреты.

Некоторые свойства простых чисел очевидны. За исключением самого маленького из них, двойки, все они нечетные. Сумма цифр простого числа, за исключением тройки, не может быть кратна трем. Они, за исключением пятерки, не могут заканчиваться на цифру 5. Если же число не подпадает под эти правила – и под несколько других, более тонких, – то невозможно посмотреть на него и сразу сказать, простое это число или нет. Да, существуют формулы для простых чисел, но это в значительной степени обман. Эти формулы не дают никакой полезной новой информации о простых числах; это просто хитрый способ зашифровать определение «простоты» в виде формулы. Простые числа – как люди: каждое из них – личность, и они не подчиняются общим правилам.

За тысячелетия математики сумели постепенно расширить свои знания о простых числах. Время от времени и сегодня решаются новые серьезные проблемы, с ними связанные. Однако многие вопросы по-прежнему остаются нерешенными. Некоторые из них фундаментальны и легко формулируются, другие понятны немногим. В этой главе говорится о том, что мы знаем и чего не знаем об этих раздражающих своей неприступностью, но все же фундаментальных числах. Начинается она с установления некоторых базовых понятий: в частности, концепции разложения на простые множители – как представить заданное число в виде произведения простых чисел. Даже этот знакомый процесс заводит нас на глубину сразу же, как только мы начинаем задавать вопросы о по-настоящему эффективных методах поиска простых множителей конкретного числа. Как ни удивительно, определить, является ли данное число простым, относительно несложно, но если число составное, то отыскать его простые множители часто намного труднее.

Разобравшись в основах, перейдем к самой известной из нерешенных задач, связанных с простыми числами, – к проблеме Гольдбаха, которой уже 250 лет. В последнее время в работе над ней достигнут колоссальный прогресс, но полностью она пока не решена. А несколько других задач представят нам примеры того, что еще предстоит сделать в этой важной, но трудно поддающейся исследованию области математики.

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

Древние греки были знакомы с некоторыми базовыми свойствами простых чисел и знали, как их доказать. Простые числа и сомножители – основная тема Книги VII евклидовых «Начал», классического труда, посвященного геометрии. В этой книге имеется, в частности, геометрическое представление арифметических действий – деления и умножения. Греки предпочитали работать не с числами как таковыми, а с длинами линий (отрезков), но их результаты несложно переформулировать на языке чисел. Так, Предложение 16 Книги VII доказывает, что при перемножении двух чисел результат не зависит от того, в каком порядке берутся эти числа. Иными словами, ab = ba, фундаментальный закон алгебры.

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

135 = 33 × 5; 630 = 2 × 32 × 5 × 7.

Затем берем все простые числа, которые присутствуют в обоих разложениях, в наибольшей общей степени; получаем 32 × 5. Перемножаем, получаем 45. Это и есть наибольший общий делитель. Из этой процедуры создается впечатление, что без разложения на простые множители невозможно найти наибольший общий делитель. На самом деле с точки зрения логики все наоборот. Предложение 2 Книги VII «Начал» представляет метод поиска наибольшего общего делителя двух натуральных чисел без разложения их на простые множители. Метод состоит в последовательном вычитании меньшего числа из большего, а затем остатка из меньшего числа и т. д. до тех пор, пока есть остаток. Для тех же чисел 135 и 630 – это достаточно типичный случай для небольших чисел – процесс выглядит так. Вычитаем 135 из 630 столько раз, сколько сможем:

630 − 135 = 495;

495 − 135 = 360;

360 − 135 = 225;

225 − 135 = 90.

Поскольку 90 < 135, переходим к той же процедуре с участием чисел 90 и 135:

135 − 90 = 45.

Поскольку 45 < 90, продолжаем то же с числами 45 и 90:

90 − 45 = 45;

45 − 45 = 0.

Таким образом, наибольший общий делитель чисел 135 и 630 равен 45.

Эта процедура работает потому, что на каждой стадии происходит замена первоначальной пары чисел более простой парой (одно из чисел уменьшается), которая тем не менее имеет тот же наибольший общий делитель. В конце концов, одно из чисел делится на второе нацело, без остатка, и процесс поиска на этом завершается. В наше время подробное описание вычислительного метода, при помощи которого можно гарантированно найти ответ той или иной задачи, называют алгоритмом. Поэтому и процедура из «Начал» Евклида известна сегодня как евклидов алгоритм. Логически эта процедура первична по отношению к процедуре разложения на простые множители. В самом деле, Евклид использует ее для доказательства основных свойств простых делителей. В современных университетских курсах математики алгоритм Евклида используется с той же целью.

Описанная процедура целиком опирается на евклидово Предложение 30 и была бы невозможна без него. В современных терминах речь в нем идет о том, что если произведение двух чисел – то, что мы получаем при их перемножении – делится на некое простое число, то на это же число должен делиться один из сомножителей. Предложение 32 заключается в том, что любое число либо само является простым, либо имеет простой делитель. Объединив оба утверждения, несложно сделать вывод, что любое число есть результат перемножения простых множителей и что их набор единственный, если не брать во внимание порядок записи. К примеру,

60 = 2 × 2 × 3 × 5 = 2 × 3 × 2 × 5 = 5 × 3 × 2 × 2

и т. д., но единственный реальный способ получить 60 состоит в том, чтобы взять множители из первого разложения и переставить их местами. Не существует, к примеру, разложения, в котором 60 = 7 × что-нибудь. Существование какого-нибудь разложения следует из Предложения 32. Если число простое – стоп. Если нет, находим простой делитель, делим на него, получая меньшее число, и повторяем процедуру. Уникальность набора делителей следует из Предложения 30. Так, если бы разложение 60 = 7 × что-нибудь существовало, то одно из чисел 2, 3 и 5 должно было бы тоже делиться на 7, но этого не происходит.

Здесь я должен прояснить один небольшой, но важный момент: исключительный статус числа 1. Согласно приведенному выше определению, оно простое: если мы попытаемся разбить его на множители, максимум, что мы получим, будет 1 = 1 × 1, где нет меньших чисел. Однако позже, с развитием теории, такая интерпретация вызывает проблемы, поэтому в последние век-два математики добавили в определение простого числа дополнительное ограничение. Число 1 настолько отличается от всех остальных чисел, что его следует рассматривать как исключение, – это не простое число, но и не составное. Это третья разновидность числа – единица. Одна из причин, по которым мы называем 1 особым случаем, а не относим ее к настоящим простым числам, заключается в том, что если мы согласимся с простотой единицы, то единственность набора множителей нарушится. Вообще-то 1 × 1 = 1 – уже нарушение, а уж 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 = 1 ни в какие ворота не лезет. Можно было бы изменить определение единственности и сказать «единственный, без учета дополнительных единичных множителей», но это был бы всего лишь другой способ признать, что 1 – число особое.

Много позже, в Предложении 20 Книги IX, Евклид доказывает еще один ключевой факт: «Простых чисел существует больше, чем их насчитывается в любом множестве простых чисел». Иными словами, множество простых чисел бесконечно. Это чудесная теорема и изящное доказательство, но ее появление вызвало множество проблем. Если простые числа уходят в бесконечность, но, судя по всему, расположены без всякой системы, то как можно сказать, на что они похожи?

Мы вынуждены обратиться к этому вопросу потому, что не можем оставить в стороне простые числа – очень существенную деталь математического ландшафта. Особенно часто они встречаются (и особенно полезны) в теории чисел – разделе математики, изучающем свойства целых чисел. Звучит, может быть, достаточно элементарно, но на самом деле теория чисел – один из самых глубоких и сложных разделов математики. Позже мы увидим тому множество свидетельств. В 1801 г. Гаусс, ведущий специалист того времени по теории чисел (а также, по мнению некоторых ученых, один из ведущих математиков всех времен, а может быть, и величайший из них), написал продвинутый учебник по этой теории – «Арифметические исследования» (Disquisitiones Arithmeticae). В нем среди множества сложных тем Гаусс указал, что не следует терять из виду два весьма фундаментальных вопроса: «Известно, что задача отличения простых чисел от составных и разложения последних на простые множители является одной из важнейших и полезнейших в арифметике».

В школе, как правило, учат ровно одному способу поиска простых делителей числа. Заключается он в том, чтобы пробовать по очереди все потенциальные делители, пока не найдется такой, на который число разделится нацело. Если вы не нашли ни одного делителя к тому моменту, как добрались до корня квадратного из первоначального числа – точнее, до наибольшего целого числа, меньшего или равного этому корню, – то число это простое. В противном случае вы найдете множитель, разделите на него и продолжите с новым числом с того же места. Эффективнее всего пробовать только простые делители, но для этого необходим список простых чисел. Поиск останавливается на корне квадратном из числа, потому что наименьший делитель любого составного числа не превосходит корень квадратный из этого числа. Однако для больших чисел эта процедура безнадежно неэффективна. К примеру, если взять число

1 080 813 321 843 836 712 253,

то на простые множители оно раскладывается следующим образом:

13 929 010 429 × 77 594 408 257,

и, чтобы добраться до меньшего из двух множителей, вам придется опробовать каждое из первых 624 401 249 простых чисел. Конечно, при помощи компьютера это несложно сделать, но если взять для начала число из 100 цифр, которое – так уж случилось – раскладывается на два множителя по 50 цифр в каждом, то систематический перебор последовательных простых чисел продлится до конца Вселенной и вряд ли успеет дать результат.

Нет, вообще-то современные компьютеры, как правило, умеют раскладывать числа из 100 цифр на простые множители. Моему компу требуется меньше секунды, чтобы найти простые множители числа 10⁹⁹ + 1 (выглядит это число как 1000 … 001 с 98 нулями). Это число – результат перемножения 13 простых чисел (одно из них повторяется дважды), наименьшее из которых – 7, а наибольшее – 141 122 524 877 886 182 282 233 539 317 796 144 938 305 111 168 717.

Однако если я попрошу компьютер разложить на множители число 10¹⁹⁹ + 1, в котором 200 цифр, то жужжать он будет долго, но результата так и не выдаст. Хотя, конечно, даже разложение числа из 100 цифр производит сильное впечатление. В чем тут секрет? В более эффективном по сравнению с последовательным перебором потенциальных простых делителей алгоритме поиска.

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

Прапрадедушкой всех современных тестов на простоту может считаться теорема Ферма (чтобы не путать со знаменитой Великой теоремой, о которой речь пойдет в главе 7, ее иногда называют Малой теоремой Ферма). Эта теорема основана на модулярной арифметике, которую иногда называют еще «часовой арифметикой», поскольку числа в ней спирально накладываются друг на друга, как время на циферблате часов. Выберем число – для 12-часовых аналоговых часов это число 12 – и назовем его модулем. Теперь в любых арифметических вычислениях с неотрицательными целыми числами мы договоримся заменять любое число, кратное 12, нулем. К примеру, 5 × 5 = 25, но 24 – это дважды 12, поэтому вычтем из результата 24. Получим 5 × 5 = 1 по модулю 12. Модулярная арифметика очень красива, поскольку почти все обычные арифметические законы в ней тоже работают. Основная разница заключается в том, что мы не всегда можем разделить одно число на другое, даже если это не нуль. Модулярная арифметика полезна также тем, что обеспечивает удобный и аккуратный способ разбираться с вопросами делимости: какие числа делятся на те или иные модули без остатка и чему равен остаток, если это не так. Модулярную арифметику предложил Гаусс в «Арифметических исследованиях», и сегодня она широко используется не только в математике, но и в информатике, физике, инженерном деле.

Малая теорема Ферма утверждает, что если взять простой модуль p и любое число a, не кратное p, то степень (p − 1) числа a будет равна 1 по модулю p. Пусть, к примеру, p = 17 и a = 3. Тогда теорема предсказывает, что остаток от деления 3¹⁶ на 17 будет равен 1. Проверим:

3¹⁶ = 43 046 721 = 2 532 160 × 17 + 1.

Ни один человек, находящийся в своем уме, не захочет проводить подобные расчеты для, скажем, 100-значных простых чисел. К счастью, существует хитрый и быстрый способ сделать это. Смысл в том, что ответ не равен единице, если модуль, с которого мы начали, является составным числом. Так что теорема Ферма – надежная основа для эффективного теста, который обеспечивает необходимое условие простоты числа.