Четыре простых числа подряд наводят на мысль, что и пятое будет простым. p = 2, 3, 5, 7 дают 3, 7, 31, 127 — все простые, и возникает соблазн поверить, что 2ᵖ − 1 простое всякий раз, когда p простое. Это неверно: калькулятор вычисляет 2¹¹ − 1 как 2047, а 23 × 89 — то же самое 2047. Одиннадцать — первый простой показатель, который терпит неудачу, поэтому простые Мерсенна — это поиск, а не формула.
Неудача не случайна, и именно это делает её проверяемой. Если простое q делит число 2ᵖ − 1 при нечётном простом p, то порядок 2 по модулю q равен p, значит p делит q − 1; а поскольку q нечётно, то и 2p делит q − 1. Итак, каждый множитель 2047 обязан быть сравним с 1 по модулю 22, и 23 и 89 — как раз те два, которые в произведении снова к этому приводят. Такое сужение — причина, по которой числа Мерсенна вообще поддаются атаке: оно отсеивает почти всех кандидатов ещё до того, как начнётся какая-либо арифметика.
Ответ
2047
Как его читать
2¹¹ − 1 на калькуляторе, причём 23 × 89 даёт то же целое число. Оба точны: 2047 лежит далеко ниже точки 2⁵³, в которой экран перестаёт считать шагами по единице.
Источник
Mersenne numbers 2ᵖ − 1, named after Marin Mersenne, whose list in Cogitata Physico-Mathematica (1644) was later proved wrong: 2⁶⁷ − 1 is composite, as Édouard Lucas showed in 1876
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.