Простые числа
Любой, кому доводилось перемножать целые числа, замечал их фундаментальные отличия.
Многие числа можно разделить на меньшие части, из которых искомое получается путем их перемножения. Например, 10 можно получить умножением 2 на 5, а 12 равно 3 × 4. Но некоторые числа так разделить невозможно. Мы не можем выразить 11 как произведение двух меньших целых чисел, то же относится к 2, 3, 5, 7 и многим другим.
Составные числа – те, которые можно выразить как произведение двух меньших. Простые числа – те, которые нельзя так выразить. Согласно этому определению, 1 должно считаться простым числом, но в силу важных причин его решено выделить в отдельный класс и обозначать как единицу. Итак, первые простые числа выглядят так:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41
По этому списку видно, что для простых чисел нет очевидного шаблона (за исключением того, что все, кроме первого, нечетные). Кажется, они появляются беспорядочно, и нет способа предсказать, каким будет следующее в списке. Но даже тогда несомненно, что это число всё же можно определить – одно за другим проверяя все последующие, пока снова не найдете простое.
Несмотря или, скорее, благодаря своему беспорядочному распределению они жизненно важны в математике. Они являются основными строительными блоками для всех прочих чисел, в том смысле, что большие числа получаются умножением меньших.
Химия утверждает, что любая молекула, какой бы сложной она ни была, состоит из атомов – неделимых частиц материи. А математика говорит нам, что любое число, каким бы большим оно ни было, состоит из простых – неделимых. Простые числа – это атомы теории чисел.
Это свойство простых чисел очень полезно, потому что в математике многие вопросы могут быть решены для всех целых чисел, если их решить для простых чисел, а простые числа имеют такие особые свойства, что иногда облегчают процесс. Эта дуальность простых чисел – простота, но непредсказуемость – всегда была предметом любопытства ученых.
Евклид
Евклид описал простые числа в книге 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 десятичных цифр
[5]. Числа вида 2p – 1, где p – простое число, называются числами Мерсенна, по имени ученого, в своем труде «Физико-математические размышления» (1644 г.) показавшего, что эти числа являются простыми для р = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257 и составными для всех остальных целых чисел, меньших 257.
