С точки зрения арифметики большинство чисел отличается, так сказать, «хорошим поведением». Четные числа всегда чередуются с нечетными, каждое третье число всегда кратно трем, квадраты чисел подчиняются определенному закону. Поэтому мы можем составить длинный ряд чисел, которые ведут себя так, как им положено, независимо от длины этого ряда и величины самих чисел. Но простые числа похожи на неуправляемую толпу. Они появляются там, где им захочется, без предварительного предупреждения, на первый взгляд, совершенно хаотично, без какой-либо закономерности. А самое главное — их нельзя проигнорировать: простые числа необходимы для арифметики и для математики в целом.
Простые числа — не такая уж сложная тема, на изучение которой потребовалось бы много лет; фактически ее проходят еще в школе. Чтобы понять, что такое простое число, нужно лишь уметь считать и владеть четырьмя основными арифметическими действиями. Тем не менее, простые числа были и продолжают оставаться одной из самых удивительных проблем в истории науки. Тот, кто хочет заниматься математикой, но не владеет теорией простых чисел, ничего не сможет добиться, так как они присутствуют везде — иногда затаившись, как в засаде, готовые появиться когда их меньше всего ожидаешь. С неизбежностью появления простых чисел невозможно не считаться.
Простые числа важны не только в математике. Многие даже не догадываются о том, что они играют важную роль в нашей повседневной жизни, например, в банковских операциях или в обеспечении защиты персональных компьютеров и конфиденциальности разговоров по мобильному телефону. Они являются краеугольным камнем компьютерной безопасности.
В метафорическом смысле простые числа — как вредоносный вирус: если он захватывает ум математика, его очень трудно искоренить. Евклид, Ферма, Эйлер, Гаусс, Риман, Рамануджан и многие другие известные математики стали его жертвой.
Хотя некоторым и удалось более-менее излечиться, все они страдали навязчивой идеей найти «волшебную формулу», которая определяет, какое простое число будет следовать за определенным натуральным числом. Однако никому еще не удалось открыть это правило.
Простые числа на протяжении всей истории математики порождали множество гипотез. В каком-то смысле можно сказать, что история простых чисел является историей неудач, но прекрасных неудач, которые со временем привели к возникновению новых теорий, свежих воззрений и передовых рубежей. В смысле развития математики простые числа являются источником чрезмерного богатства: как это ни парадоксально звучит, даже хорошо, что эта теория до конца не изучена. И все говорит о том, что такая ситуация будет сохраняться в течение долгого времени.
При подготовке этой книги мы старались поддерживать «высокий» уровень разъяснения: объем математических знаний, необходимых для понимания материала, может быть небольшим. Кавычки указывают на то, что эти понятия относительны, тем более для рассматриваемых здесь тем. Во всяком случае, эта книга является кратким путеводителем по миру простых чисел и будет полезна каждому читателю, который знает, что такое числа, и умеет оперировать ими.
С другой стороны, для читателей, имеющих более глубокие знания математики, мы постарались включить информацию о конкретных исторических процессах, необходимых для понимания тонкостей, которые великие математики применяли в решении проблем, связанных с простыми числами.
Как будет ясно из первой главы, понятие простых чисел и задачи, связанные с ними, можно легко объяснить, но решения этих задач в большинстве своем относятся к сложнейшим областям профессиональной математики.
Глава 1
На заре арифметики
Как и у всего остального, у простых чисел тоже есть происхождение: свое начало они берут в системах счета. Простые числа появились одновременно с натуральными, но очень быстро выделились в виде особого набора специальных чисел.
Нет ничего более натурального, чем натуральные числа.
«Бог создал первые десять чисел, остальное — дело рук человека». Эти слова сказаны немецким математиком Леопольдом Кронекером (1823–1891) про натуральные числа, которые мы используем при счете: 1, 2, 3, 4, 5 и т. д. Кронекер имел в виду, что могучее здание математики построено на самой простой, элементарной арифметике. Если не углубляться в религию, то утверждение о том, что Бог дал нам первые десять чисел, означает, что эти числа всегда были частью природы.
Без особой натяжки можно предположить, что необходимость в счете появилась, когда человечество перешло от охоты и собирательства к земледелию и животноводству. При этом урожай и скот перестали быть продуктами немедленного потребления, а превратились в товары, которые нужно считать, регистрировать и продавать.
Это создало потребность в конкретных способах счета. Представим себе пастуха, который выгоняет стадо на пастбище. Он должен быть уверен, что в загон вернется то же количество животных, которое он выпускал. Без системы счета самым естественным решением будет взять горсть гальки и класть один камень в сумку каждый раз, как из загона выходит одна овца. Затем, по возвращении, он должен вынимать один камень для каждой входящей в загон овцы, чтобы таким образом убедиться в том, что все овцы целы. Это, конечно, примитивная система подсчета. Кстати, слово подсчет (
