Начнем с того, что есть 2 экспоненциальные формулы, огромной исторической важности. Обе изучались математиками XVII и XVIII веков, в особенности Ферма и Эйлером. Вот эти формулы:
M(n)=2n-1 и F(n)=22^n+1,
где n - натуральное. Числа из перфой формулы называются числами Мерсенна, а из второй - числами Ферма.
В данном документе мы рассмотрим только числа Мерсенна.
Вопрос о том при каких значениях n числа Мерсена просты, восходит к математикам античной Греции. В пифагорейском мистицизме число называлось совершенным, если оно равняется полусумме своих положительных дделителей. Например, делители числа 6 - это 1,2,3, и 6. Складывая их, получаем:
1+2+3+4+6=12=2*6
Следовательно, 6 - совершенное число. Конечно, никакое простое число не будет совершенным. Действительно, делитель простого числа p - это 1 и p, и 1+p<2p, поскольку p>1.
Эвклид знал, что число 2n-1(2n-1) совершенно, если 2n-1 простое. Нетрудно показать, что все четные совершенные числа имеют такой виз, но доказан этот факт был только Эйлером в восемнадцатов веке. Формула Эвклида сводит задачу о поиске совершенных чисел к нахождению простых чисел Мерсенна.
Задача о нахождении совершенных чисел, имеющая своим истоком туманный мистицизм пифагорейцев,может показаться крайне странной некоторым живущим в начале двадцать первого века. Однако, факт остается фактом: несмотря на то, что проблема стоит около 2500 лет, у нее еще нет удовлетворительного решения. Например, неизвестно, обязано ли совершенное число быть четным, хотя к настоящему времени не найдено не одного нечетного. Конечно, возраст, этой проблеммы бросает трудно преодолимый вызов всем, кто любит числа. Более того, ее сложность может означать, что она относится к глубочайшим свойствам целых чисел. Это делает ее даже еще более важной с точки зрения математиков.
Марен Мерсенн был священником и математиком-любителем семнадцатого века. Числа вида 2n-1 обязаны своим именем утверждению Мерсенна о том, что они просты, в случае
n=2, 3, 5, 7, 13, 17, 19, 67, 127 и 257,
и являются составными для всех остальных 44 положительных простых n, меньших 257.
Первое важное замечение: Мерсен рассматривал значения 2n-1 только при простых n. Действительно, если n-составное, то такое же и M(n). Предположим, что n=rs, 1<r и s<n, тогда
M(n)=2n-1=2rs-1=(2r-1)(2r(s-1)+2r(s-2)+...+2r+1).
Следовательно, если r делит n, то M(r) делит M(n). Второй важный момент заключается в том, что обратное неверно. Иначе говоря, если n - простое, то M(n) не обязано быть простым. Мы видим из списка Мерсенна, что M(11) должно быть составным. Это легко проверить:
M(11)=2047=23*89.
Как часто бывало в то время, Мерсенн не привел доказательства своего утверждения, что дало повод для сомнений в его истинности и оставило широкое поле деятельности для математиков. В поисках простых чисел Мерсенна принял участие и Эйлер. В 1732 году он нашел два "новых простых" числа Мерсенна: M(41) и M(47), отсутствовавших в списке Мерсенна. Поэтому выяснилось, что в этом случае Эйлер был неправ. Первую ошибку в списке Мерсенна нашли Первуээн (Pervusin) и Зилхоф (Seelhov) в 1886. Они обнаружили, что число M(61) простое, хотя его и нет в списке. Другие ошибки были нацдены в последующие годы. Сейчас известно, что кроме M(61), в списке пропущены простые числа M(89) и M(107), и присутствуют составные числа M(67) и M(257).
При доказательстве простоты чисел Мерсенна, Ферма использовал метод разложения на множители. В наше время используется гораздо более эффективный тест Люку-Лемера. С помощью этого теста в 1998 году было показано, что число Мерсенна M(3 021 377) просто. Оно состоит из 1 819 050 знаков. В настоящее время, по моим сведениям, известно 44 простых числа Мерсенна. Число знаков в самом большом из них немного не дотянуло до 10 000 000. Почему именно такой барьер? Все очень просто. Тот кто найдет число Мерсенна с количеством цифр более десяти миллионов, получит премию в $100000 ! Хотите попробовать свои силы? Дерзайте!