Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.
Задача для чисел Мерсенна - поиск в ряду этих чисел простых.
Мерсенн рассматривал значения функции 2p - 1 только при простых p. Действительно, если p - составное, то такое же и М(p). Предположим, что p=r? s, 1 < r и s < p, тогда
М(p) = 2p -1 = 2rs - 1 = (2r - l)(2r(s-1) + 2r(s-2) + . . . + 2r +1).
Следовательно, если r делит p, то и М(r) делит М(p).
В то же время, если p - простое, то М(p) не обязательно является простым. Например, для простого числа p = 11 число Мерсенна М(p)=211−1=2047=23×89 получается составным.
Определен следующий ряд (начало ряда) простых чисел Мерсенна
(табл. 1.7):
|
| № | p | Цифр в M(p) |
При доказательстве простоты чисел Мерсенна, Ферма использовал
метод разложения на множители. Более эффективен тест Люка-Лемера.