Читать «Число, пришедшее с холода. Когда математика становится приключением» онлайн - страница 54

Марен Мерсенн нашел еще один рецепт. Он вычитал из степеней 2, то есть из чисел

2² = 4, 2³ = 8, 2⁴ = 16, 2⁵ = 32, 2⁶ = 64, 2⁷ = 128,

2⁸ = 256, 2⁹ = 512…

единицу и установил, что только в тех случаях, когда показатель степени является простым числом, результат вычитания из степени единицы является простым числом. Действительно, имеем:

2² — 1 = 3, 2³ — 1 = 7, 2⁵ — 1 = 31, 2⁷ — 1 = 127,

то есть простые числа. Вычитание единицы из представленной составным числом степени числа 2 ни в коем случае не может дать в результате простое число, как это видно из следующих примеров:

2⁴ — 1 = 15 = (2² — 1) × (1 + 2²) = 3 × 5,

2⁶ — 1 = 63 = (2³ — 1) × (1 + 2³) = 7 × 9,

2⁸ — 1 = 255 = (2⁴ — 1) × (1 + 2⁴) = 15 × 17,

2⁹ — 1 = 511 = (2³ — 1) × (1 + 2³ + 2⁶) = 7 × 73.

Мерсенн, однако, сам выяснил, что его рецепт действует не всегда, а точнее, весьма редко. Собственно, даже если показатель степени двойки выражен простым числом, разность между степенью и единицей не обязательно является простым числом. Хотя правило Мерсенна работает для показателей степени 2, 3, 5 и 7, сбой происходит уже при показателе, равном 11, ибо 2¹¹–1 = 2047, то есть произведению 23 и 89.

Тем не менее это не окончательный сбой. Мерсенн доказал, что иногда его формула работает и при показателях степени, больших 11. Действительно, он установил, что числа

2¹³ — 1 = 8191, 2¹⁷ –1 = 131 071 и 2¹⁹ — 1 = 524 287

являются простыми. Мерсенн утверждал, что то же самое верно и для показателей степени 31, 67, 127 и 257, но неверно для простых чисел, находящихся в промежутках между ними. Здесь Мерсенн немного ошибся. Число 2⁶⁷ — 1 не является простым, но зато таковым является число 2⁶¹ — 1, как и числа 2⁸⁹ — 1 и 2¹⁰⁷ — 1, а вот число 2²⁵⁷ — 1 простым не является. Показатели степени меньше 500, при которых разность степени двойки и единицы дает простое число, следующие:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127.

Наибольшая из этих разностей, состоящая из 39 разрядов, а именно

2¹²⁷ — 1 = 170 141 183 460 469 231 731 687 303 715 884 105 727,

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

Однако уже в 1950 г. для вычисления простых чисел по формуле Мерсенна были использованы электронно-вычислительные машины, и было обнаружено свыше тридцати разностей степеней двойки и единицы, представлявших собой огромные простые числа, и среди них одно, состоящее из дюжины миллионов разрядов.