Liczba pierwsza Mersenne’a

Pierwsza liczba Mersenne’a to liczba pierwsza, którą można zapisać w postaci 2n-12^{n}-12n-1. Na przykład 313131 jest liczbą pierwszą Mersenne’a, którą można zapisać jako 25-12^{5}-125-1. Pierwsze kilka liczb pierwszych Mersenne’a to 3,7,31,127,81913, 7, 31, 127, 81913,7,31,127,8191. Na czerwiec 2018 roku znanych jest 50 prymusów Mersenne’a, choć mamy nadzieję, że w przyszłości się to zmieni. Ciekawostką dotyczącą prymusów Mersenne’a jest to, że są to najłatwiejsze liczby naturalne do udowodnienia, że są prymusami, więc tworzą największą kategorię na liście znanych liczb pierwszych.

Poszukiwania i ciekawość prymusów Mersenne’a wzięły się z badania liczb doskonałych. Liczba doskonała to liczba, która może być zapisana jako suma jej dodatnich dzielników właściwych. Na przykład, 666 jest liczbą doskonałą, ponieważ można ją zapisać jako 6=1+2+36=1+2+36=1+2+3, i w rzeczywistości jest to najmniejsza liczba doskonała. Następną liczbą doskonałą jest 28=1+2+4+7+1428=1+2+4+7+1428=1+2+4+7+14.

Można wykazać, że jeśli dodatnia liczba całkowita aaa może być zapisana w postaci 2n-1(2n-1)2^{n-1}(2^{n}-1)2n-1(2n-1), tak że 2n-12^{n}-12n-1 jest liczbą pierwszą, to aaa musi być parzystą liczbą doskonałą. Widzieliśmy, że jeśli 2n-12^{n}-12n-1 jest liczbą pierwszą, to jest liczbą pierwszą Mersenne’a, co tworzy jeden do jednego związek między liczbami pierwszymi Mersenne’a i liczbami parzystymi doskonałymi. To znaczy, że każdej liczbie pierwszej Mersenne’a odpowiada dokładnie jedna parzysta liczba doskonała! (Do tej pory nie znaleziono żadnej nieparzystej liczby doskonałej.)

Wykaż, że jeśli 2n-12^{n}-12n-1 jest pierwsze, to nnn musi być również pierwsze.

Podajemy ppp i qqq jako dodatnie liczby całkowite większe od jeden takie, że n=p⋅qn=p⋅q. Wówczas korzystając z tożsamości faktoryzacji,

2pq-1=(2p-1)⋅(1+2p+22p+23p+⋯+2p(q-1)).{ 2 }^{ pq }-1= lewa strona( { 2 }^{ p }-1 \prawda) \prawda( 1+{ 2 }^{ p }+{ 2 }^{ 2p }+{ 2 }^{ 3p }+{ 2 }^{ p(q-1) } \prawda). 2pq−1=(2p−1)⋅(1+2p+22p+23p+⋯+2p(q−1)).

Jeśli więc nnn jest złożone i WLOG 1<p<q1<p<q1<p<q, wtedy mamy człon 2n-12^{n}-12n-1 jako złożony, ponieważ jest on podzielny przez człon 2p-12^{p}-12p-1. □_kwadrat□

Dowód ten mówi nam, że jeśli 2n-12^{n}-12n-1 jest pierwsze, to nnn jest również pierwsze. Ale to nie gwarantuje, że jeśli nnn jest pierwsze, to 2n-12^{n}-12n-1 jest pierwsze, ponieważ nie uwzględniliśmy drugiego członu w powyższym równaniu. Typowym tego przykładem jest 11:11:11: mimo że jest to liczba pierwsza, 211-1=20472^{11}-1=2047211-1=2047 nie jest liczbą pierwszą.