Любому, кто захочет написать список всех простых чисел, придется писать его вечно, потому что их количество бесконечно. Почему же мы уверены, что никогда не дойдем до последнего простого числа, что за ним в списке будет следующее? Одно из величайших достижений человеческого разума состоит как раз в том, что с помощью небольшой последовательности логических шагов мы можем осознать бесконечность.

Первым, кто доказал нескончаемость простых чисел, был греческий математик Евклид, живший в Александрии. Он был учеником Платона, и время его деятельности также пришлось на III в. до н. э., хотя, по-видимому, он был на 50 лет старше библиотекаря Эратосфена.

Для того чтобы доказать бесконечность количества простых чисел, Евклид задался вопросом: может ли, напротив, множество простых чисел быть конечным? Конечный список простых чисел означал бы, что любое другое число может быть получено перемножением элементов этого конечного списка. Предположим, к примеру, что список простых чисел включает лишь три числа: 2, 3 и 5. Может ли любое число быть получено путем перемножения различных комбинаций 2, 3 и 5? Евклид придумал способ построения числа, которое не может быть получено таким путем. Он начал с перемножения списка простых чисел, что приводит к 30. Затем – и в этом была гениальная догадка – он добавил 1 к этому числу и получил 31. Ни одно из списка простых чисел, ни 2, ни 3, ни 5, не является его делителем. Всегда получается остаток 1.

Евклид знал, что все числа могут быть построены перемножением простых чисел – так что же можно сказать о 31? Так как оно не делится на 2, 3 или 5, должны быть другие простые числа, вне имеющегося списка, которые участвуют в построении 31. В действительности число 31 само является простым, так что Евклид создал «новое» простое число. Вы скажете, что в имеющийся список простых чисел нужно лишь добавить это «новое» число. Но, сколь бы ни был велик список, Евклид мог бы снова повторить свой прием – перемножить числа из списка и добавить 1. Каждый раз он получал бы число, которое при делении на любое число из списка давало бы остаток 1, значит, это новое число должно делиться на простые числа вне имеющегося списка. Таким образом Евклид доказал, что любой конечный список не может включать все простые числа. Следовательно, количество простых чисел должно быть бесконечным.

Хотя Евклид сумел показать, что простые числа никогда не заканчиваются, его доказательство не говорило, как найти простые числа. Можно было бы подумать, что, действуя в соответствии с указанной процедурой, мы будем генерировать новые простые числа. Ведь мы перемножили 2, 3 и 5, добавили 1 и получили новое простое число 31. Однако такая процедура срабатывает не всегда. Например, возьмите следующий список простых чисел: 2, 3, 5, 7, 11 и 13. Перемножив их, мы получим 30 030, а добавив 1, придем к 30 031. Простые числа с 2 до 13 не являются делителями последнего числа, всякий раз при делении получается остаток 1. Тем не менее 30 031 не является простым числом, у него есть простые делители 59 и 509, которые не включены в наш список. В действительности математики до сих пор не знают, будет ли повторение процедуры перемножения конечного количества простых чисел и добавления 1 давать бесконечно много новых простых чисел.