Магия математики. Как найти x и зачем это нужно

В интервале от 1 до 100 насчитывается 25 простых чисел, от 101 до 200 – 21, от 201 до 300 – 16. И тенденция эта сохраняется: чем дальше мы продвигается, тем реже встречаются простые величины (без всякой, впрочем, системы: в промежутке от 301 до 400 их снова 16, а в промежутке от 401 до 500 – 17) – а от 1 000 000 до 1 000 100 мы их найдем всего лишь 6. Объяснение этому вполне очевидно: чем больше число, тем больше потенциальных делителей у него будет.

Давайте попробуем доказать, что есть такие сотни чисел, в которых простых чисел не будет вовсе (и не только сотни – тысячи, миллионы, сколько угодно). Для этого будет достаточно подобрать 99 последовательно идущих друг за другом составных чисел:

100! + 2, 100! + 3, 100! + 4…., 100! + 100

Так как 100! = 100 × 99 × 98 ×… × 3 × 2 × 1, его можно разделить на все числа от 2 до 100. Возьмем теперь 100! + 53. Так как 53 – делитель 100! оно должно являться делителем и 100! + 53. Та же логика подсказывает, что при 2 ≤ k ≤ 100 100! + k должно быть кратным k, а следовательно, составным.

Отступление

Обратите внимание, что мы пропустили 100! + 1. Впрочем, ничто не мешает нам взять и его. На этот счет существует очень интересная теорема – теорема Вильсона, которая утверждает, что число n является простым тогда и только тогда, когда (n – 1)! + 1 делится на n без остатка. Применим ее к нескольким малым величинам: 1! + 1 = 2, что кратно 2; 2! + 1 = 3, что кратно 3; 3! + 1 = 7, что не кратно 4; 4! + 1 = 25, что кратно 5; 5! + 1 = 121, что не кратно 6; 6! + 1 = 721, что кратно 7; и т. д. Следовательно, поскольку число 101 – простое, согласно теореме Вильсона, 100! + 1 является кратным 101 и потому составным. Значит, промежуток от 100! до 100! + 100 содержит в себе непрерывную последовательность, состоящую из 101 составного числа.

Итак, чем больше числа, тем меньше среди них попадается простых. Вполне логично было бы предположить, что рано или поздно они перестают попадаться вовсе. Но только не в этом случае, как больше 2000 лет назад предупредил нас Евклид. Дерзнем не поверить великому греку на слово и докажем это сами.

Теорема: Количество простых чисел бесконечно.

Доказательство: Предположим обратное – что количество простых чисел конечно. Значит, существует некое наибольшее простое число. Обозначим его литерой P. Возьмем число P! + 1. Так как P! делится на все числа в промежутке от 2 до P, ни одно из них нельзя разделить на P! + 1 без остатка. Следовательно, простой множитель P! + 1 будет больше P, что противоречит нашему условию, что P есть наибольшее простое число.◻

И хотя мы никогда не найдем наибольшее простое число, математики и специалисты по вычислительной технике не оставляют попыток зайти в этих поисках все дальше и дальше в бесконечность числового ряда. Самым большим известным науке простым числом на настоящий момент является число, состоящее из 17 425 170 цифр. Чтобы его записать, потребуется примерно сотня томов – каждый объемом не меньше книги, которую вы сейчас держите в руках. Но можно уместить и в одну строку –

2^{57 885 161} – 1

А все благодаря существованию удивительно действенных методов, которые позволяют легко определить, являются ли числа вида 2n – 1 или 2n + 1 простыми.