Ketika empat prima muncul berturut-turut, orang tergoda mengira yang kelima juga prima. p = 2, 3, 5, 7 memberi 3, 7, 31, 127 — semuanya prima, dan Anda ingin percaya bahwa setiap kali p prima, 2ᵖ − 1 juga prima. Salah. Kalkulator menghitung 2¹¹ − 1 sebagai 2047 dan 23 × 89 juga 2047 yang sama. Sebelas adalah eksponen prima pertama yang gagal, jadi bilangan prima Mersenne adalah pencarian, bukan rumus.
Kegagalan itu bukan kebetulan, dan justru itulah yang membuatnya dapat diverifikasi. Untuk prima ganjil p, jika prima q membagi 2ᵖ − 1 maka orde 2 modulo q adalah p, sehingga p membagi q − 1. Karena q ganjil, 2p juga membagi q − 1. Jadi setiap faktor 2047 harus kongruen dengan 1 modulo 22, dan 23 serta 89 adalah keduanya yang hasil kalinya kembali membawa ke sana. Penyempitan seperti inilah yang membuat bilangan Mersenne bisa diserang. Ia menyaring hampir semua kandidat sebelum aritmetika apa pun dimulai.
Jawaban
2047
Cara membacanya
2¹¹ − 1 pada kalkulator, dan 23 × 89 juga memberi bilangan bulat yang sama. Keduanya tepat. 2047 jauh di bawah 2⁵³, titik tempat layar berhenti menghitung satu per satu.
Sumber
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
Kerjakan di kalkulator
Tautan ini membuka kalkulator yang tepat dengan angka soal ini sudah diketik. Baris di atas adalah yang seharusnya ditampilkan layar — periksa sendiri.