Путеводитель для влюбленных в математику. Эдвард Шейнерман

много?

      Вернемся к вопросу: сколько всего простых чисел существует? Ответ – на следующей строчке.

      Теорема. Простых чисел бесконечно много.

      Утверждение приписывают Евклиду[20]. Доказательство этой теоремы – математическая жемчужина. Мы не можем доказать ее методом перебора. Очевидно, что время от времени в числовом ряде попадаются простые числа. Вот несколько первых простых чисел:

      2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 и 67.

      Но чем дальше мы идем по последовательности простых чисел, тем обширнее становятся промежутки между ними. Если посмотреть на перечень выше, можно увидеть, что два числа отстоят друг от друга максимум на 6 единиц (например, 53 и 59). Но простые числа 89 и 97 отстоят друг от друга на 8 единиц, все целые числа между ними составные. Или вот другой пример: 139 и 149 – их отделяет 10 единиц. Чем дальше мы двигаемся, тем быстрее увеличиваются промежутки между соседними простыми числами. Можно предположить, что в конечном итоге простые числа должны совсем исчезнуть. На самом деле, хотя они и встречаются все реже, их список в числовом ряду не имеет конца. Впрочем, прежде чем говорить об этом уверенно, мы должны привести доказательство.

      Ключевая идея – задаться вопросом: а что, если?..

      А что, если количество простых чисел конечно? Если мы продемонстрируем, что предположение: «Количество простых чисел конечно» – приводит к абсурдному выводу, то будем считать его ложным[21]. Вслед за Шерлоком Холмсом мы найдем истину, отбросив невозможные варианты, и у нас получится, что простых чисел бесконечно много.

      Вот что нам надо будет сделать:

      1. Предположить, что количество простых чисел конечно;

      2. Показать, что это предположение ведет к невозможному выводу;

      3. Сделать умозаключение, что, раз предположение ведет к логическому противоречию, оно ложно;

      4. Вывести из этого, что простых чисел бесконечно много.

      А теперь перейдем к делу. Предположим, что простые числа можно пересчитать, и посмотрим, к чему это приведет.

      Если количество простых чисел конечно, должно существовать наибольшее простое число P – крайнее в ряду простых чисел. В таком случае полный перечень простых чисел будет выглядеть так:

      2, 3, 5, 7, 11, 13, …, P.

      Перемножим все эти числа и приплюсуем единицу. Назовем получившееся гигантское число N:

      N = (2 × 3 × 5 × 7 × 11 × 13 × … × P) + 1.

      Число N – простое[22]? Наше предположение заставляет нас ответить: нет, потому что N больше P, последнего простого числа. Значит, N – составное число, и его можно разложить на множители. Здесь мы попадаем в западню.

      Мы знаем, что у N есть простые делители. Может ли таким делителем быть 2? Мы утверждаем: нет. Посмотрите на формулу для вычисления N и обратите внимание, что число в скобках четное, потому что среди множителей присутствует 2:

      N = ( × 3 × 5 × 7 × 11 × 13 × … × P) + 1.

      Таким образом, N на единицу больше некоторого гигантского четного числа. Другими словами, N – нечетное, следовательно, оно не делится на 2.

      Ну и ладно. Мы же знаем, что у N есть простой

20

Евклид – автор геометрического трактата «Начала», вершины античной математики. Его научная деятельность протекала в Александрии на рубеже IV и III веков до н. э. – Прим. пер.

21

Подобным образом преступника ловят на лжи. «Вы утверждаете, что были дома в ту ночь, мистер Нулик?» – «Да». – «Чем вы занимались?» – «Телевизор смотрел». – «А вы в курсе, что в тот вечер отключали электричество?» – «Э…» Очевидно, что мистер Нулик в столь поздний час не смотрел телевизор!

22

Представим себе, что последнее простое число равно 13. Тогда N = (2 × 3 × 5 × 7 × 11 × 13) + 1 = 30 031.