Công cụ Kiểm tra Số nguyên tố Mersenne

Giới thiệu về Công cụ Kiểm tra Số nguyên tố Mersenne

Chào mừng bạn đến với Công cụ Kiểm tra Số nguyên tố Mersenne, một công cụ tương tác kiểm tra xem \(2^p - 1\) có phải là số nguyên tố Mersenne hay không cho bất kỳ số mũ \(p\) nào lên đến 5000. Công cụ này chạy kiểm tra tính nguyên tố Lucas-Lehmer nổi tiếng, hiển thị dấu vết lặp lại hoạt hình của hệ thức truy hồi \(S_i = S_{i-1}^2 - 2 \pmod{M_p}\), trực quan hóa mẫu bit nhị phân (một dấu hiệu đặc trưng của mọi số Mersenne) và — khi kết quả là số nguyên tố — sẽ ghép đôi nó với số hoàn hảo chẵn tương ứng thông qua định lý Euclid-Euler.

Số nguyên tố Mersenne là gì?

Một số Mersenne là một số có dạng \(M_p = 2^p - 1\). Khi bản thân \(M_p\) là số nguyên tố, nó được gọi là một số nguyên tố Mersenne. Tên gọi này nhằm vinh danh Marin Mersenne (1588-1648), một tu sĩ người Pháp, người đã lập danh mục các trường hợp ban đầu và phỏng đoán những số mũ nào lên đến 257 tạo ra số nguyên tố — một danh sách sau đó được chứng minh là sai một phần, nhưng đã mở ra ba thế kỷ nghiên cứu.

Một vài số nguyên tố Mersenne đầu tiên, theo thứ tự:

• \(M_2 = 3\)
• \(M_3 = 7\)
• \(M_5 = 31\)
• \(M_7 = 127\)
• \(M_{13} = 8{,}191\)
• \(M_{17} = 131{,}071\)
• \(M_{19} = 524{,}287\)
• \(M_{31} = 2{,}147{,}483{,}647\) (được tìm thấy bởi Euler vào năm 1772 — số nguyên tố lớn nhất được biết đến trong suốt 104 năm)

Tính đến năm 2024, chính xác 52 số nguyên tố Mersenne đã được biết đến. Kỷ lục hiện tại là \(M_{136{,}279{,}841}\), được phát hiện vào tháng 10 năm 2024 bởi dự án điện toán phân tán GIMPS — một con số có 41.024.320 chữ số thập phân.

Kiểm tra Lucas-Lehmer

Lý do các số nguyên tố Mersenne thống trị các bảng kỷ lục là nhờ một bài kiểm tra tính nguyên tố chuyên biệt, cực kỳ nhanh do Édouard Lucas phát hiện (1878) và được Derrick Lehmer đơn giản hóa (1930):

Bài kiểm tra chỉ yêu cầu \(p-2\) phép bình phương modulo — xấp xỉ \(O(p^3)\) thao tác bit với phép nhân thông thường, hoặc \(O(p^2 \log p \log\log p)\) với FFT. Hãy so sánh điều này với các bài kiểm tra tính nguyên tố đa năng trên các số có kích thước như \(M_p\) (hàng triệu chữ số), điều mà hoàn toàn không khả thi. Lối tắt Lucas-Lehmer chính là thứ giúp việc tìm kiếm số nguyên tố Mersenne trở nên khả thi.

Tại sao p phải là số nguyên tố?

Nếu \(p = a \cdot b\) với \(a, b > 1\), một hằng đẳng thức cổ điển cho thấy \(2^a - 1\) chia hết cho \(2^{ab} - 1\):

Vì vậy, nếu số mũ là hợp số, \(M_p\) tự động là hợp số. Điều ngược lại là sai: \(p\) là số nguyên tố không đảm bảo \(M_p\) là số nguyên tố. Ví dụ, \(p = 11\) là số nguyên tố nhưng \(M_{11} = 2047 = 23 \times 89\).

Số nguyên tố Mersenne và Số hoàn hảo (Euclid-Euler)

Euclid đã quan sát thấy vào khoảng năm 300 trước Công nguyên rằng nếu \(2^p - 1\) là số nguyên tố, thì \(2^{p-1}(2^p - 1)\) là một số hoàn hảo — một con số bằng tổng các ước thực sự của nó. Sau đó, Euler đã chứng minh điều ngược lại: mọi số hoàn hảo chẵn đều phát sinh theo cách này.

Vì vậy, việc tìm thấy một số nguyên tố Mersenne mới ngay lập tức tạo ra một số hoàn hảo mới. Bốn số hoàn hảo chẵn đầu tiên là 6, 28, 496 và 8128 — đã được biết đến từ thời cổ đại. Việc liệu có tồn tại bất kỳ số hoàn hảo lẻ nào hay không vẫn là một bài toán chưa có lời giải sau hơn 2.300 năm.

Mẫu bit nhị phân

Mỗi số Mersenne có một biểu diễn nhị phân cực kỳ gọn gàng: \(2^p\) trong hệ nhị phân là \(1\) theo sau bởi \(p\) số 0, vì vậy \(2^p - 1\) chính xác là \(p\) bit 1 liên tiếp:

Đây là lý do tại sao công cụ trực quan hóa mỗi bit dưới dạng một ô riêng biệt — mẫu bit là dấu hiệu trực quan của một số Mersenne, không phụ thuộc vào việc số đó có phải là số nguyên tố hay không.

Cách sử dụng máy tính này

1. Nhập một số mũ \(p\): bất kỳ số nguyên dương nào từ 1 đến 5.000.
2. Nhấp Kiểm tra: công cụ trước tiên kiểm tra xem \(p\) có phải là số nguyên tố hay không; nếu không, nó sẽ giải thích tại sao \(M_p\) phải là hợp số.
3. Đối với p nguyên tố: hệ thức truy hồi Lucas-Lehmer chạy \(p - 2\) lần lặp modulo \(M_p\).
4. Khám phá kết quả: biểu ngữ phán quyết, dấu vết lặp lại 6 dòng (với "..." cho các bước giữa bị bỏ qua trên \(p\) lớn), dạng thập phân và nhị phân của \(M_p\), và ghép cặp số hoàn hảo Euclid-Euler khi có thể áp dụng.

Mười hai số nguyên tố Mersenne đầu tiên đã biết

Dự án GIMPS

Great Internet Mersenne Prime Search (GIMPS), được khởi xướng vào năm 1996 bởi George Woltman, là một dự án điện toán phân tán nơi các tình nguyện viên đóng góp thời gian CPU để chạy các bài kiểm tra Lucas-Lehmer trên các số mũ ứng viên. Tính đến năm 2024, mọi số nguyên tố Mersenne kể từ M_35 = M_{1398269} (1996) đều được khám phá bởi GIMPS. Một bài kiểm tra Lucas-Lehmer đơn lẻ ở biên giới hiện đại (các số mũ gần \(10^8\)) mất nhiều tuần tính toán trên GPU.

Sự thật thú vị về số nguyên tố Mersenne

• \(M_{31} = 2{,}147{,}483{,}647\) là số nguyên có dấu 32-bit lớn nhất — \(\texttt{INT\_MAX}\) nổi tiếng trong ngôn ngữ C. Đây không phải là ngẫu nhiên: giá trị này bắt nguồn từ thực tế rằng \(M_{31}\) là số nguyên tố và do đó là một ranh giới "ngay-trước-khi-tràn" tự nhiên.
• Có những khoảng trống không xác định kích thước giữa các số nguyên tố Mersenne liên tiếp. Người ta không biết liệu có vô số số nguyên tố Mersenne hay không — giả thuyết Lenstra-Pomerance-Wagstaff dự đoán là có, tăng trưởng xấp xỉ như \(e^\gamma \log_2 p\).
• Vào năm 2008, Electronic Frontier Foundation đã trao giải thưởng 100.000 USD cho người đầu tiên phát hiện ra số nguyên tố có 10 triệu chữ số. Giải thưởng đã thuộc về đội ngũ GIMPS của UCLA cho số \(M_{43112609}\). Một giải thưởng 150.000 USD vẫn đang chờ đợi số nguyên tố có 100 triệu chữ số đầu tiên.
• \(M_{31}\) xuất hiện trên tờ tiền lưu niệm 100 rúp Nga năm 1811 vinh danh khám phá của Euler — một trong số ít các số nguyên tố từng được in trên tiền tệ.
• Vì mỗi số nguyên tố Mersenne tạo ra một số hoàn hảo, nhân loại hiện có chính xác 52 số hoàn hảo chẵn trong hồ sơ (khớp với 52 số nguyên tố Mersenne đã biết).

Câu hỏi thường gặp

Số nguyên tố Mersenne là gì?

Số nguyên tố Mersenne là số nguyên tố có dạng \(2^p - 1\), trong đó \(p\) cũng là số nguyên tố. Một vài số đầu tiên là 3, 7, 31, 127 và 8.191. Tính đến năm 2024, có 52 số nguyên tố Mersenne đã được biết đến; số nguyên tố lớn nhất (\(M_{136{,}279{,}841}\)) là một số nguyên tố Mersenne với hơn 41 triệu chữ số.

Kiểm tra Lucas-Lehmer hoạt động như thế nào?

Đối với số mũ nguyên tố \(p \geq 3\), xác định \(S_0 = 4\) và \(S_i = S_{i-1}^2 - 2 \pmod{M_p}\). Số Mersenne \(M_p = 2^p - 1\) là số nguyên tố nếu và chỉ nếu \(S_{p-2} \equiv 0 \pmod{M_p}\). Kiểm tra chạy trong \(p - 2\) lần lặp, mỗi lần là một phép bình phương modulo đơn lẻ.

Tại sao p phải là số nguyên tố?

Nếu \(p = ab\) với cả hai thừa số đều lớn hơn 1, thì \(2^p - 1\) chia hết cho \(2^a - 1\) (và cho \(2^b - 1\)), vì vậy \(M_p\) là hợp số. Điều ngược lại không đúng: \(p\) là số nguyên tố không có nghĩa là \(M_p\) là số nguyên tố. Ví dụ \(p = 11\) là số nguyên tố nhưng \(M_{11} = 2047 = 23 \times 89\) là hợp số.

Mối liên hệ giữa số nguyên tố Mersenne và số hoàn hảo là gì?

Định lý Euclid-Euler phát biểu rằng mọi số hoàn hảo chẵn đều có dạng \(2^{p-1}(2^p - 1)\) trong đó \(2^p - 1\) là một số nguyên tố Mersenne. Vì vậy, mỗi số nguyên tố Mersenne tạo ra đúng một số hoàn hảo chẵn và mỗi số hoàn hảo chẵn đều bắt nguồn từ một số nguyên tố Mersenne. Việc có tồn tại số hoàn hảo lẻ nào hay không là một trong những bài toán mở lâu đời nhất.

Tại sao \(M_p\) có \(p\) bit 1 liên tiếp trong hệ nhị phân?

Số \(2^p\) trong hệ nhị phân là số 1 theo sau bởi \(p\) số 0. Trừ đi 1 sẽ chuyển tất cả \(p\) số 0 ở cuối thành các số 1. Vì vậy, \(2^p - 1\) trong hệ nhị phân chính xác là \(p\) số một — dấu hiệu trực quan đặc trưng của mọi số Mersenne, dù là số nguyên tố hay hợp số.

Số mũ lớn nhất mà công cụ này có thể kiểm tra là bao nhiêu?

Công cụ này kiểm tra các số mũ lên đến 5.000 để vòng lặp Lucas-Lehmer hoàn thành trong một yêu cầu web bình thường. Đối với các số mũ lớn hơn (bao gồm cả ranh giới GIMPS gần \(10^8\)), cần có phần mềm chuyên dụng như Prime95 vì một lần kiểm tra có thể mất nhiều tuần tính toán trên một GPU hiện đại.

Tài nguyên bổ sung

• Số nguyên tố Mersenne - Wikipedia
• Kiểm tra tính nguyên tố Lucas-Lehmer - Wikipedia
• Số hoàn hảo - Wikipedia
• GIMPS: Great Internet Mersenne Prime Search
• OEIS A000043: Các số mũ của số nguyên tố Mersenne

Phép toán cơ bản:

• Máy tính thừa số chung
• Máy tính Lập phương và Căn bậc ba
• Máy tính căn bậc ba
• Chia Thành Hai Phần
• Máy tính Kiểm tra Chia hết Nổi bật
• Máy tính hệ số
• Máy tính Tìm Số Lớn Nhất và Nhỏ Nhất
• n chữ số đầu tiên của e
• n chữ số đầu tiên của pi
• Máy tính Ước số chung lớn nhất
• Đây có phải là Số Nguyên Tố? Nổi bật
• Máy tính Bội số chung nhỏ nhất (BCNN)
• Máy tính Modulo Nổi bật
• Máy tính nhân
• Máy tính căn bậc n độ chính xác cao
• Máy tính số chữ số
• Máy tính thừa số nguyên tố
• Máy tính Phân tích Thừa số Nguyên tố Nổi bật
• Máy tính thương và số dư Nổi bật
• Sắp xếp số Nổi bật
• Máy tính căn bậc hai Nổi bật
• Máy tính Tổng
• Máy Tính Tỷ Lệ Mới
• Máy Tính Chia Dài Mới
• Máy Tính Nhân Chéo Mới
• Tạo Bảng Cửu Chương Mới
• Máy Tính Nhân Dọc Mới
• Máy tính Cộng và Trừ theo Cột Mới
• Máy tính Thứ tự Phép tính (PEMDAS) Mới
• Trình tạo Biểu đồ Giá trị Hàng Mới
• Công cụ Tìm Quy luật Dãy số Mới
• Kiểm Tra Số Chẵn Hay Số Lẻ Mới
• Máy Tính Giá Trị Tuyệt Đối Mới
• Máy Tính Hàm Trần và Sàn Mới
• Máy Tính Giá Đơn Vị Mới
• Trình Tạo Đếm Nhảy Mới
• Máy Tính Ước Lượng Mới
• Kiểm tra Số Hoàn hảo Mới