А все благодаря существованию удивительно действенных методов, которые позволяют легко определить, являются ли числа вида 2n – 1 или 2n + 1 простыми.
Отступление
Великий Пьер де Ферма доказал, что если p – это нечетное простое число, то число 2p–1 – 1 должно быть кратно p. Проверим это на примере нескольких первых нечетных простых чисел. Для 3, 5, 7 и 11 мы видим, что 2² – 1 = 3, что кратно 3; 24 – 1 = 15, что кратно 5; 26 – 1 = 63, что кратно 7; 210 – 1 = 1023, что кратно 11. Что касается составных чисел, совершенно ясно, что при четном значении n 2n–1 – 1 будет нечетным, а потому кратным n быть никак не может. Составные же нечетные, вроде 9, 15 или 21, дают нам 28 – 1 = 255, что не кратно 9; 214 – 1 = 16 383, что не кратно 15; 220 – 1 = 1 048 575, что не кратно 21 (да хотя бы и 3).
Следствием теоремы Ферма является то, что, если при наибольшем значении числа N 2N–1 – 1 не кратно N, мы можем со стопроцентной уверенностью утверждать, что N не может быть простым, при этом нам даже необязательно знать его множители! Тем не менее это не совсем так: существуют такие составные числа, которые ведут себя абсолютно как простые (и по этой причине называются псевдопростыми). Самый простой пример – 341 = 11 × 31: 2340 – 1 вполне себе кратно 341. И хотя встречаются такие числа крайне редко, их количество все же бесконечно, а для их определения придуманы специальные методы.
Простые числа активно используются в повседневной жизни – в частности, в вычислительной технике при создании алгоритмов кодирования (на них, например, построена система шифрования с открытым ключом, которая используется при совершении финансовых операций онлайн). В большинстве своем они построены на методах быстрого определения того, является ли то или иное число простым. Жаль только, что нет настолько же эффективных способов быстрого разложения на множители по-настоящему огромных чисел. Так, если я перемножу два случайных тысячезначных числа и скажу вам двухтысячезначный ответ, вы никогда в жизни не сможете найти составляющие его простые величины – ни сами, ни с помощью компьютера (конечно, если этот компьютер не квантовый – а такие собирать пока еще попросту не научились). Зато представляете, насколько надежны коды (вроде алгоритма RSA[17]), в основе которых лежит эта неспособность?
Интерес человечества к простым числам стар, как само человечество. Древние греки называли число, равное сумме его делителей (естественно, за исключением самого этого числа), совершенным. Среди них, например, число 6, сумма делителей которого – 1, 2 и 3 – равна 6. Или 28, получающееся из сложения 1, 2, 4, 7 и 14. Дальше следуют 496 и 8128. Интересно, складываются они в какую-нибудь закономерность? Попробуем разложить их на множители:
Видите закономерность? Первое число – это степень основания 2. Второе – на единицу меньше, чем удвоенная степень основания 2; и при этом оно простое (поэтому здесь и нет 8 × 15 или, скажем, 32 × 63: ведь 15 и 63 простыми числами не являются). Закономерность эту можно сформулировать в виде теоремы.
Теорема: Если число 2n – 1 является простым, число 2n–1 × (2n – 1) будет совершенным.
