Số nguyên tố lớn nhất được biết, theo kỷ lục công bố tháng 10 năm 2024, là 2¹³⁶²⁷⁹⁸⁴¹ − 1, một số có 41.024.320 chữ số. Nó là một số nguyên tố Mersenne, dạng 2ᵖ − 1, và được Luke Durant tìm ra trong dự án tính toán phân tán GIMPS. Số nguyên tố thì có vô hạn, nên kỷ lục này chỉ là con số lớn nhất mà con người đã kiểm chứng được.
Có số nguyên tố lớn nhất không
Không. Từ khoảng năm 300 trước Công nguyên, Euclid đã chứng minh có vô số số nguyên tố. Vì thế "số nguyên tố lớn nhất" luôn phải hiểu là "lớn nhất mà người ta đã biết chắc là nguyên tố". Kỷ lục này bị phá đều đặn, mỗi lần lại dài thêm vài triệu chữ số, và là một trong những ví dụ đẹp nhất về một con số khổng lồ có thật, được viết ra trọn vẹn từng chữ số.
So với số Graham hay googolplex, số nguyên tố kỷ lục nhỏ đến không đáng kể. Nhưng nó có một điều mà những số kia không có: người ta lưu được toàn bộ chữ số của nó vào một tệp chừng 40 megabyte, và đã kiểm chứng tính nguyên tố của nó bằng nhiều máy tính độc lập.
Vì sao kỷ lục gần như luôn là số Mersenne
Số Mersenne là số có dạng 2ᵖ − 1, đặt theo tên tu sĩ người Pháp Marin Mersenne, người lập danh sách các số dạng này vào năm 1644. Muốn 2ᵖ − 1 là nguyên tố thì p bắt buộc phải là số nguyên tố, nhưng điều ngược lại không đúng:
| p | 2ᵖ − 1 | Nguyên tố? |
|---|---|---|
| 2 | 3 | có |
| 3 | 7 | có |
| 5 | 31 | có |
| 7 | 127 | có |
| 11 | 2.047 = 23 × 89 | không |
| 13 | 8.191 | có |
Số Mersenne được ưu ái vì có một phép thử cực nhanh dành riêng cho chúng: phép thử Lucas–Lehmer, do Édouard Lucas đưa ra năm 1878 và Derrick Lehmer hoàn thiện năm 1930. Cách làm: bắt đầu với s = 4, lặp phép "bình phương rồi trừ 2" tổng cộng p − 2 lần, mỗi lần lấy số dư khi chia cho 2ᵖ − 1. Nếu cuối cùng được 0 thì số đó là nguyên tố.
Bạn có thể thử tay với p = 5, tức số 31: s = 4, rồi 4² − 2 = 14, rồi 14² − 2 = 194, chia 31 dư 8, rồi 8² − 2 = 62, chia 31 dư 0. Được 0 sau ba bước, vậy 31 là nguyên tố. Với số có hàng chục triệu chữ số, mỗi bước bình phương là một phép nhân khổng lồ, được làm bằng thuật toán nhân nhanh dựa trên biến đổi Fourier, nhưng nguyên tắc y hệt.
Lịch sử kỷ lục: từ 6 chữ số tới 41 triệu chữ số
| Năm | Số | Số chữ số | Ai, bằng gì |
|---|---|---|---|
| 1588 | 2¹⁹ − 1 = 524.287 | 6 | Pietro Cataldi, tính tay |
| 1772 | 2³¹ − 1 = 2.147.483.647 | 10 | Leonhard Euler, tính tay |
| 1876 | 2¹²⁷ − 1 | 39 | Édouard Lucas, kỷ lục tính tay lớn nhất cho số Mersenne |
| 1952 | 2⁵²¹ − 1 | 157 | Raphael Robinson, máy tính SWAC |
| 1978 | 2²¹⁷⁰¹ − 1 | 6.533 | Laura Nickel và Curt Noll, hai học sinh trung học, máy CDC |
| 1996 | 2¹³⁹⁸²⁶⁹ − 1 | 420.921 | Joel Armengaud, kỷ lục đầu tiên của GIMPS |
| 2008 | 2⁴³¹¹²⁶⁰⁹ − 1 | 12.978.189 | Edson Smith, máy ở Đại học UCLA |
| 2018 | 2⁸²⁵⁸⁹⁹³³ − 1 | 24.862.048 | Patrick Laroche, GIMPS |
| 2024 | 2¹³⁶²⁷⁹⁸⁴¹ − 1 | 41.024.320 | Luke Durant, GIMPS, dùng bộ xử lý đồ hoạ thuê trên đám mây |
Một chi tiết vui: số 2.147.483.647 mà Euler chứng minh là nguyên tố năm 1772 về sau trở thành con số giới hạn nổi tiếng trong máy tính, giá trị lớn nhất của một số nguyên có dấu 32 bit. Còn kỷ lục 2024 đáng chú ý vì là lần đầu sau 28 năm kỷ lục không do máy tính cá nhân chạy bộ xử lý trung tâm tìm ra, mà nhờ hàng nghìn bộ xử lý đồ hoạ thuê ở nhiều trung tâm dữ liệu.
Tự tính số chữ số của một số Mersenne
Không cần viết số ra mới biết nó dài bao nhiêu. Số chữ số của 2ᵖ là phần nguyên của p × log₁₀2 cộng 1, với log₁₀2 ≈ 0,30103. Trừ đi 1 không làm thay đổi số chữ số (vì 2ᵖ không bao giờ là luỹ thừa của 10).
- p = 127: 127 × 0,30103 ≈ 38,2, cộng 1 được 39 chữ số. Khớp bảng.
- p = 136.279.841: 136.279.841 × 0,30103 ≈ 41.024.319,3, cộng 1 được 41.024.320 chữ số.
In 41 triệu chữ số ra giấy, mỗi trang 3.000 chữ số, cần khoảng 13.700 trang, tức chừng ba chục cuốn sách dày. Đọc to mỗi giây một chữ số, không nghỉ, mất khoảng một năm bốn tháng.
Mẹo nhẩm 2¹⁰ = 1.024 ≈ 10³ cũng cho kết quả gần đúng: cứ mười bậc của 2 là ba chữ số. 136 triệu chia 10 nhân 3 được khoảng 41 triệu chữ số.
GIMPS: hàng nghìn máy tính cùng săn một con số
GIMPS (Great Internet Mersenne Prime Search) được George Woltman lập năm 1996. Bất kỳ ai cũng có thể tải phần mềm miễn phí, để máy tính chạy phép thử khi rảnh, và nhận về một số mũ p để kiểm tra. Từ 1996 tới 2024, toàn bộ 18 kỷ lục số nguyên tố Mersenne đều đến từ dự án này.
Cách dự án làm việc là một bài học hay về kiểm chứng. Khi một máy báo kết quả "có thể là nguyên tố", con số được kiểm lại bằng phần mềm khác, trên phần cứng khác, do người khác chạy. Chỉ khi mọi lần kiểm cho cùng kết quả, kỷ lục mới được công bố. Ngày nay dự án còn dùng phép thử xác suất kèm "chứng chỉ" cho phép kiểm lại kết quả nhanh mà không phải chạy lại từ đầu.
Tính tới kỷ lục 2024, người ta biết 52 số nguyên tố Mersenne. Chưa ai chứng minh được có vô hạn số như thế hay không, dù phần lớn các nhà toán học tin là có.
Số nguyên tố lớn dùng để làm gì
Nói thẳng: những số kỷ lục có hàng chục triệu chữ số không trực tiếp dùng vào việc gì trong đời sống. Mã hoá trên mạng, như khi bạn đăng nhập ngân hàng, dùng số nguyên tố cỡ vài trăm chữ số, nhỏ hơn rất nhiều và được sinh ngẫu nhiên, không phải số Mersenne.
Giá trị của cuộc săn nằm ở chỗ khác. Nó thúc đẩy thuật toán nhân số lớn, được dùng lại trong nhiều ngành. Nó là bài kiểm tra phần cứng khắc nghiệt: phần mềm của GIMPS từng phát hiện lỗi trong bộ xử lý máy tính. Và nó nối với một trong những kết quả cổ nhất của số học: mỗi số nguyên tố Mersenne 2ᵖ − 1 sinh ra một số hoàn hảo 2ᵖ⁻¹ × (2ᵖ − 1), tức số bằng tổng các ước của nó. Ví dụ p = 3 cho 4 × 7 = 28 = 1 + 2 + 4 + 7 + 14. Euclid biết chiều thuận, Euler chứng minh mọi số hoàn hảo chẵn đều có dạng này.
Góc nhìn hôm nay: tự tham gia và tự kiểm
Ai có máy tính đều có thể tham gia GIMPS, và về lý thuyết bất kỳ máy nào cũng có thể là máy tìm ra kỷ lục tiếp theo. Với người chỉ muốn chơi với con số, một ngôn ngữ như Python xử lý được số nguyên lớn tuỳ ý: gõ 2**127 - 1 là thấy ngay số 39 chữ số mà Lucas từng mất nhiều năm kiểm tay.
Thử viết phép thử Lucas–Lehmer trong vài dòng lệnh rồi kiểm các p từ 2 tới 100. Bạn sẽ tìm lại đúng mười số nguyên tố Mersenne đầu tiên, ứng với p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89. Đó là cách hay để thấy bằng tay mình một quy luật mà các nhà toán học mất ba thế kỷ mới xác lập.
Câu hỏi thường gặp
Số nguyên tố lớn nhất hiện nay là số nào?
Theo kỷ lục công bố tháng 10 năm 2024, đó là 2¹³⁶²⁷⁹⁸⁴¹ − 1, có 41.024.320 chữ số, do Luke Durant tìm ra trong dự án GIMPS. Vì có vô số số nguyên tố, đây chỉ là số lớn nhất đã được kiểm chứng, và kỷ lục có thể bị phá bất cứ lúc nào.
Số nguyên tố Mersenne là gì?
Là số nguyên tố có dạng 2ᵖ − 1, ví dụ 3, 7, 31, 127. Để 2ᵖ − 1 là nguyên tố thì p phải là nguyên tố, nhưng không phải p nguyên tố nào cũng cho số Mersenne nguyên tố, ví dụ 2¹¹ − 1 = 2.047 = 23 × 89.
Có bao nhiêu số nguyên tố Mersenne?
Tính tới kỷ lục năm 2024, người ta biết 52 số nguyên tố Mersenne. Chưa ai chứng minh được chúng có vô hạn hay không, dù đa số các nhà toán học tin là có.
Vì sao số nguyên tố lớn nhất luôn là số Mersenne?
Vì có phép thử Lucas–Lehmer kiểm tra tính nguyên tố của 2ᵖ − 1 nhanh hơn rất nhiều so với các phép thử cho số bất kỳ. Nhờ vậy, máy tính kiểm được những số Mersenne dài hàng chục triệu chữ số mà với số dạng khác thì chưa làm nổi.
Số nguyên tố lớn có dùng để mã hoá không?
Mã hoá thông dụng dùng số nguyên tố cỡ vài trăm chữ số, được sinh ngẫu nhiên, không dùng số kỷ lục hay số Mersenne. Các số kỷ lục có giá trị chủ yếu cho toán học, thuật toán và kiểm tra phần cứng.
