Возникновение чисел в результате умножения — процесс несколько более запутанный и сложный, но зато и более интересный. Мы снова будем исходить из единицы как из первого числа. Однако, умножая единицу саму на себя сколь угодно большое число раз, мы не получим ничего, кроме единицы.
Первым настоящим «элементом» чисел — с точки зрения умножения — является число 2. Из него возникает целый ряд чисел: 2 × 2 = 2² = 4, 2 × 2 × 2 = 2³ = 8, 2 × 2 × 2 × 2 = 24 = 16 и т. д. Но получить таким образом все числа невозможно. Наименьшее число, отсутствующее в этом списке, — это 3. Поэтому за еще один «элемент» числового царства была принята и тройка — наряду с двойкой. Такие «элементы», как 2 и 3, в математике называют простыми числами (на латыни они называются также первичными). Действительно, начиная с простых чисел, из них путем умножения получают все остальные числа.
С помощью чисел 2 и 3 в результате умножения получают числа 2 × 2 = 4, 2 × 3 = 6, 2 × 2 × 2 = 8, 3 × 3 = 9, 2 × 2 × 3 = 12 и т. д. Как мы видим, так снова получаются не все числа. В этом списке отсутствуют 5 и 7. Они тоже являются простыми.
Величайшее озарение снизошло на двух греческих ученых — Евклида из Александрии и Эратосфена из Кирены. Оба принадлежали к поколению, родившемуся после Александра Македонского, и оба работали в Александрийской библиотеке.
Евклид выяснил, что из бесконечного списка простых чисел можно получить все числа как произведения простых чисел из списка. Если же произведения составлять из конечного списка простых чисел, то получить все числа путем вычисления таких произведений не удастся никогда. Евклид обосновывал свое утверждение так: он вычисляет произведение всех простых чисел из списка и добавляет к результату единицу. Выполнив эту операцию, он получает число, которое невозможно разделить ни на одно простое число из списка. Следовательно, это число не является результатом произведения простых чисел первоначально заданного конечного списка.
Растолкуем рассуждения Евклида на конкретном примере: допустим, некто утверждает, что все простые числа исчерпываются списком из 2, 3, 5, 7, 11 и 13. Других простых чисел якобы не существует. Тогда, возражает Евклид, число 2 × 3 × 5 × 7 × 11 × 13 + 1, равное 30 031, можно было бы представить как произведение простых чисел из этого конечного списка. Но очевидно, что это неверно. Число 30 031 не делится ни на одно простое число из нашего списка, при любом делителе мы получим остаток, равный единице. Поскольку же число 30 031 не может быть записано как произведение простых чисел из списка 2, 3, 5, 7, 11, 13, постольку простых чисел должно быть больше, чем их есть в списке. Помимо того, заметим, что в список не входят простые числа 59 и 509, а именно их перемножение дает в результате 30 031, то есть 59 × 509 = 30 031.
Эратосфену удалось создать таблицу простых чисел в промежутке между 2 и 100. Вот этот список:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 59, 61, 67, 71, 73, 79, 83, 89, 97.
При взгляде на него возникает впечатление, что в последовательности простых чисел нет никакой закономерности. В их последовательности мы не наблюдаем никакой регулярности. Эратосфен также понимал, как можно усовершенствовать и расширить систематизацию простых чисел, для чего вычислил все простые числа в промежутке между 1 и 1000. Однако аргумент Евклида гласит, что никакой конечный список не может содержать все без исключения простые числа. То есть ни один конечный список простых чисел не является исчерпывающим.
Спорадическое появление простых чисел в ряду следующих друг за другом натуральных чисел вызывает удивление: между следующими друг за другом простыми числами 19 609 и 19 661 мы видим довольно большой промежуток. Напротив, разность между числами 19 697 и 19 699 равна всего лишь двум. Представляется, что не существует простого закона, определяющего порядок следования простых чисел.
В частности, мы пока не знаем, является ли простым число 4 294 967 297…
В поисках простых чисел
Во Франции времен кардинала Ришелье, когда знатные люди и богатые буржуа имели достаточно досуга для бесполезных, на первый взгляд, занятий, некоторые из них по-любительски — в лучшем смысле этого слова — занимались проблемой простых чисел. К числу таких людей принадлежали работавший на монетном дворе чиновник Министерства финансов Бернар Френикль де Бесси, образованный монах ордена «минимов» Марен Мерсенн и адвокат и парламентский советник Пьер де Ферма. Все они главным образом пытались отыскать формулу, согласно которой можно было бы получать простые числа.
Один из обманчивых рецептов, разработанный ими, гласил: для того чтобы получить простое число, надо взять число, сложить его с его квадратом и с числом 41. На первый взгляд такой принцип выглядит многообещающе. Действительно, если взять единицу, прибавить к ней квадрат единицы, то есть 1, а затем 41, то получится 43 — простое число. Если взять 2, то его квадрат равен 4. При сложении обоих чисел с 41 получится простое число 47. Взяв 3, мы получим 53, также простое число. Далее, если взять 4 и 5, то получатся тоже простые числа — 61 и 71 соответственно. Этот ряд не кончается долго. Например, возьмем число 10, возведем его в квадрат, сложим 100 и 10 и прибавим 41. Мы опять получим простое число — 151. Если взять число 36, прибавить 36² = 1296, а затем еще число 41, то получится простое число 1373. По этой формуле числа от 1 до 39 бесперебойно дают простые числа. Но потом система дает сбой. Прибавим к числу 40 его квадрат, 40² = 40 × 40, и в результате получим число, равное произведению 40 × 41. Если же к этому числу прибавить число 41, то получится число 41 × 41 = 41². Это число не может быть простым. (Это просто прекрасно, что для обоснования этого утверждения не надо ничего вычислять. Однако, разумеется, с тем же успехом можно указать на то, что сложение числа 40 с его квадратом 40² = 1600 дает в результате 1640, после увеличения которого на 41 мы получим число 1681. Можно легко удостовериться в том, что 1681 = 41² = 41 × 41, то есть не является простым числом. Но доказательство, позволяющее избежать вычислений, выглядит все-таки более изящно.)
Марен Мерсенн нашел еще один рецепт. Он вычитал из степеней 2, то есть из чисел
2² = 4, 2³ = 8, 24 = 16, 25 = 32, 26 = 64, 27 = 128,
28 = 256, 29 = 512…
единицу и установил, что только в тех случаях, когда показатель степени является простым числом, результат вычитания из степени единицы является простым числом. Действительно, имеем:
2² — 1 = 3, 2³ — 1 = 7, 25 — 1 = 31, 27 — 1 = 127,
