Йэн Стюарт - Укрощение бесконечности. История математики от первых чисел до теории хаоса [litres]

Это свойство простых чисел очень полезно, потому что в математике многие вопросы могут быть решены для всех целых чисел, если их решить для простых чисел, а простые числа имеют такие особые свойства, что иногда облегчают процесс. Эта дуальность простых чисел – простота, но непредсказуемость – всегда была предметом любопытства ученых.

Евклид описал простые числа в книге 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 .