Евклид
Евклид описал простые числа в книге VII «Начал» и доказал три их ключевых свойства. В современном изложении это звучит так.
• Любое число можно представить как производное простых чисел.
• Это выражение будет уникальным, за исключением порядка, в котором появляются простые числа.
• Простых чисел бесконечно много.
Однако то, что Евклид на самом деле утверждал, и то, что он доказал, – не совсем одно и то же. Предложение 31 из книги VII утверждает, что всякое составное число измеряется каким-то первым (простым) числом, т. е. его можно точно разделить на это простое число. Например, 30 – составное, и оно точно делится на несколько простых чисел, среди которых есть 5: действительно, 30 = 6 × 5. Повторяя этот процесс поиска делителя в виде простого числа или множителя, мы можем разложить любое составное число на произведение простых. Так, начав с 30 = 6 × 5, мы находим, что 6 также является составным (2 × 3). Теперь 30 = 2 × 3 × 5, причем все три множителя простые. Это была факторизация числа 30. Если бы мы начали с 30 = 10 × 3, нам пришлось бы вместо этого разложить 10, т. е. 10 = 2 × 5, т. е. 30 = 2 × 5 × 3. Получаем те же три простых числа, но перемноженные в другом порядке, – что, конечно, не влияет на результат.
Может показаться очевидным, что, каким бы образом мы ни раскладывали число на простые, мы всегда получим одинаковый результат, за исключением их порядка, но доказать это не так просто. Похожие утверждения для некоторых систем чисел, связанных математическими соотношениями, на поверку оказываются ложными, хотя для обычных целых чисел они и верны. Разложение на простые множители уникально. Евклид доказал ключевой факт, необходимый для утверждения об уникальности, в «Началах». Предложение 30, книга VII: если простое число делит произведение из двух чисел, то оно должно делить по крайней мере одно из них. Уникальность факторизации – прямое следствие предложения 30.
ПОЧЕМУ УНИКАЛЬНЫ И НЕ ТАК ОЧЕВИДНЫ ПРОСТЫЕ МНОЖИТЕЛИ
Коль скоро мы признаем простые числа атомами теории чисел, вроде бы логично предположить, что при делении чисел на простые должны всегда получаться одинаковые атомы. В конце концов, атомы – неделимые частицы. Если вы можете поделить число двумя разными способами, не будет ли это расщеплением атома? И вот здесь аналогия с химией немного неточная.
Чтобы понять, что уникальность факторизации не очевидна, мы можем взять неполный набор чисел:
1 5 9 13 17 21 25 29
и т. д. Здесь выбраны числа, которые на единицу больше чисел, кратных 4. Произведения этих чисел также обладают схожими свойствами, т. е. мы можем построить такие числа, умножая меньшие числа подобного типа. Назовем квазипростыми любые числа в этом ряду, не являющиеся произведениями двух меньших в исходном ряду. Например, 9 будет квазипростым: меньше его только 1 и 5, а их произведение не равно 9. (То, что 9 = 3 × 3, остается в силе, но в исходном ряду у нас не было 3.) Очевидно – и верно, – что каждое составное число в ряду является произведением квазипростых. Однако, хотя эти квазипростые числа оказываются атомами для данного ряда, выходит нечто весьма странное. Число 693 (693 = 692 + 1, где 692 = 173 × 4, кратно 4) можно разбить двумя разными способами: 693 = 9 × 77 = 21 × 33, и все четыре множителя: 9, 21, 33 и 77 – квазипростые. А значит, уникальность факторизации не работает для этого типа чисел.
Предложение 20, книга IX, утверждает: «Простых чисел существует больше всякого предложенного количества простых чисел». В современном изложении это значит, что множество простых бесконечно. В доказательство можно привести пример: представьте, что существует только три простых числа: a, b и c. Перемножьте их и прибавьте единицу, вот так: abc + 1. Это число должно делиться на какое-то простое, но оно не может быть одним из этих трех первоначальных, поскольку они нацело делят abc, но ни одно из них не сможет также разделить abc + 1, ведь тогда им придется делить еще и разницу, которая равна 1. Получается, что мы обнаружили еще одно простое число, а это противоречит предположению о существовании только трех простых чисел a, b, c.
Хотя в доказательстве Евклида использовано всего три числа, та же идея работает и для более длинного списка. Перемножьте все простые числа в нем, добавьте единицу, затем возьмите несколько простых множителей и проверьте результат: вы всегда сгенерируете новое число, которого нет в списке. То есть невозможно составить полный законченный перечень простых чисел.
НАИБОЛЬШЕЕ ИЗВЕСТНОЕ ПРОСТОЕ ЧИСЛО
Наибольшего простого числа не существует, но в сентябре 2006 г. было найдено наибольшее известное простое число, равное 232 582 657 – 1, в котором есть 9 808 358 десятичных цифр. Числа вида 2p – 1, где p – простое число, называются числами Мерсенна, по имени ученого, в своем труде «Физико-математические размышления» (1644 г.) показавшего, что эти числа являются простыми для р = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257 и составными для всех остальных целых чисел, меньших 257.
Сейчас существуют специальные высокоскоростные методы проверки таких чисел, и мы знаем о пяти ошибках Мерсенна. Его числа получаются составными, если р = 67 и 257, и есть три пропущенных им простых числа с р = 61, 89, 107. На сегодня известно 49 чисел Мерсенна. Поиски новых могут считаться хорошей проверкой новых компьютеров, но не имеют практического значения.
