Cztery liczby pierwsze z rzędu budzą podejrzenie wobec piątej. p = 2, 3, 5, 7 dają 3, 7, 31, 127, wszystkie pierwsze, więc kusząco myśleć, że 2ᵖ − 1 jest pierwsze, ilekroć p jest pierwsze. Nie jest: stół roboczy liczy 2¹¹ − 1 jako 2047, a 23 × 89 to te same 2047. Jedenaście to pierwszy wykładnik pierwszy, który zawodzi — i dlatego liczby pierwsze Mersenne'a są poszukiwaniem, a nie wzorem.
Zawodzenie nie jest przypadkowe i właśnie to czyni je testowalnym. Jeśli liczba pierwsza q dzieli 2ᵖ − 1 przy nieparzystym pierwszym p, to 2 ma rząd p modulo q, więc p dzieli q − 1; ponieważ q jest nieparzyste, także 2p dzieli q − 1. Każdy czynnik 2047 musi więc przystawać do 1 mod 22, a 23 i 89 to te dwa, które mnożą się z powrotem do niego. To zawężenie jest powodem, dla którego liczby Mersenne'a w ogóle da się atakować: usuwa prawie każdego kandydata, zanim zacznie się jakakolwiek arytmetyka.
Odpowiedź
2047
Jak to czytać
2¹¹ − 1 na stole roboczym, z 23 × 89 dającym identyczną liczbę całkowitą. Obie są dokładne: 2047 leży daleko poniżej punktu 2⁵³, w którym ekran przestaje liczyć co jeden.
Źródło
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
Rozwiąż w kalkulatorze
Te linki otwierają właściwy kalkulator z już wpisanymi liczbami tego zadania. Powyższa linia to to, co powinien pokazać ekran — sprawdź sam.