Некоторые свойства простых чисел очевидны. За исключением самого маленького из них, двойки, все они нечетные. Сумма цифр простого числа, за исключением тройки, не может быть кратна трем. Они, за исключением пятерки, не могут заканчиваться на цифру 5. Если же число не подпадает под эти правила — и под несколько других, более тонких, — то невозможно посмотреть на него и сразу сказать, простое это число или нет. Да, существуют формулы для простых чисел, но это в значительной степени обман. Эти формулы не дают никакой полезной новой информации о простых числах; это просто хитрый способ зашифровать определение «простоты» в виде формулы. Простые числа — как люди: каждое из них — личность, и они не подчиняются общим правилам.
За тысячелетия математики сумели постепенно расширить свои знания о простых числах. Время от времени и сегодня решаются новые серьезные проблемы, с ними связанные. Однако многие вопросы по-прежнему остаются нерешенными. Некоторые из них фундаментальны и легко формулируются, другие понятны немногим. В этой главе говорится о том, что мы знаем и чего не знаем об этих раздражающих своей неприступностью, но все же фундаментальных числах. Начинается она с установления некоторых базовых понятий: в частности, концепции разложения на простые множители — как представить заданное число в виде произведения простых чисел. Даже этот знакомый процесс заводит нас на глубину сразу же, как только мы начинаем задавать вопросы о по-настоящему эффективных методах поиска простых множителей конкретного числа. Как ни удивительно, определить, является ли данное число простым, относительно несложно, но если число составное, то отыскать его простые множители часто намного труднее.
Разобравшись в основах, перейдем к самой известной из нерешенных задач, связанных с простыми числами, — к проблеме Гольдбаха, которой уже 250 лет. В последнее время в работе над ней достигнут колоссальный прогресс, но полностью она пока не решена. А несколько других задач представят нам примеры того, что еще предстоит сделать в этой важной, но трудно поддающейся исследованию области математики.
Простые числа и разложение на множители знакомы нам из школьного курса арифметики, однако большинство интересных свойств простых чисел на этом уровне не рассматривают и никаких доказательств не представляют. Тому есть веские причины: доказательства даже самых очевидных, на первый взгляд, свойств удивительно сложны. Вместо этого школьников учат некоторым простым методикам работы с простыми числами, акцентируя внимание на вычислениях, где цифры относительно невелики. В результате наши первые впечатления от встречи с простыми числами, как правило, обманчивы.
Древние греки были знакомы с некоторыми базовыми свойствами простых чисел и знали, как их доказать. Простые числа и сомножители — основная тема Книги VII евклидовых «Начал», классического труда, посвященного геометрии. В этой книге имеется, в частности, геометрическое представление арифметических действий — деления и умножения. Греки предпочитали работать не с числами как таковыми, а с длинами линий (отрезков), но их результаты несложно переформулировать на языке чисел. Так, Предложение 16 Книги VII доказывает, что при перемножении двух чисел результат не зависит от того, в каком порядке берутся эти числа. Иными словами, ab = ba, фундаментальный закон алгебры.
В школьной арифметике простые делители используют для поиска наибольшего общего делителя двух чисел. К примеру, чтобы найти наибольший общий делитель чисел 135 и 630, мы раскладываем их на простые множители:
Затем берем все простые числа, которые присутствуют в обоих разложениях, в наибольшей общей степени; получаем 32 × 5. Перемножаем, получаем 45. Это и есть наибольший общий делитель. Из этой процедуры создается впечатление, что без разложения на простые множители невозможно найти наибольший общий делитель. На самом деле с точки зрения логики все наоборот. Предложение 2 Книги VII «Начал» представляет метод поиска наибольшего общего делителя двух натуральных чисел без разложения их на простые множители. Метод состоит в последовательном вычитании меньшего числа из большего, а затем остатка из меньшего числа и т. д. до тех пор, пока есть остаток. Для тех же чисел 135 и 630 — это достаточно типичный случай для небольших чисел — процесс выглядит так. Вычитаем 135 из 630 столько раз, сколько сможем: