Số nguyên tố Mersenne

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Số nguyên tố Mersenne là một số Mersenne (số có dạng lũy thừa của 2 trừ 1: 2n − 1, một số định nghĩa yêu cầu lũy thừa (n) phải là số nguyên tố) và là một số nguyên tố: ví dụ 31 là số nguyên tố Mersenne vì 31 = 25 − 1, và 31 là số nguyên tố.

Điều kiện cần để số Mn nguyên tố là n là số nguyên tố, 24 -1 = 15 là hợp số vì 4 không là nguyên tố, nhưng ngược lại không đúng: ví dụ số Mersenne 2047 = 211 − 1 không là nguyên tố vì nó chia hết cho 89 và 23, mặc dù số 11 là số nguyên tố.

Hiện nay, các số nguyên tố lớn nhất được tìm thấy thường là số nguyên tố Mersenne.

Các số nguyên tố Mersenne có quan hệ chặt chẽ với các số hoàn thiện, nghĩa là các số bằng tổng các ước chân chính của nó. Trong lịch sử, việc nghiên cứu các số nguyên tố Mersenne đã từng bị thay đổi do các liên quan này; vào thế kỷ 4 TCN, Euclid phát biểu rằng nếu M là số nguyên tố Mersenne thì M(M+1)/2 là số hoàn thiện. Vào thế kỷ 18, Leonhard Euler chứng minh rằng tất cả các số hoàn thiện chẵn đều có dạng này. Không một số hoàn thiện lẻ nào được biết, và người ta nghi ngờ rằng chúng không tồn tại.

Tìm các số nguyên tố Mersenne[sửa | sửa mã nguồn]

Đẳng thức

2^{ab}-1=(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a}\right)

cho biết rằng Mn có thể là số nguyên tố chỉ nếu chính n là số nguyên tố, điều đó làm giản lược bớt việc tìm các số nguyên tố Mersenne. Mệnh đề đảo, nói rằng Mn là số nguyên tố nếu n là số nguyên tố là sai. Số nhỏ nhất cho ví dụ này là 211-1 = 23×89, là hợp số.

Đã có các thuật toán nhanh để tìm số nguyên tố Mersenne, do đó hiện nay đã biết các số nguyên tố Mersenne rất lớn.

Bốn số nguyên tố Mersenne đầu tiên M_2=3, M_3=7, M_5=31M_7=127 đã được biết từ cổ xưa. Số thứ năm, M_{13}=8191, được tìm thấy vào trước năm 1461; hai số tiếp theo (M_{17}M_{19}) tìm thấy bởi Cataldi vào năm 1588, đồng thời ông còn dự đoán cho các số mũ 23 (bị Fermat bác bỏ), 29 (bị Fermat bác bỏ), 37(bị Euler bác bỏ). Sau hơn một thế kỷ M_{31} được kiểm tra bởi Euler vào năm 1750 bằng Lý thuyết chỉ số. Số tiếp theo (trong lịch sử, không theo thứ tự số) là M_{127}, do Lucas tìm thấy vào năm 1876, sau đó M_{61} do Pervushin tìm vào năm 1883. Hai số nữa (M_{89}M_{107}) được tìm thấy vào thế kỷ 20, bởi Powers vào năm 1911 và 1914.

Từ thế kỷ 17, các số này được mang tên nhà toán học Pháp Marin Mersenne, người đã chứng minh và dự đoán một loạt các số nguyên tố Mersenne với các số mũ: 2, 3, 5, 7, 13, 17, 31, 67, 127, 257. Danh sách của ông đã mắc một số sai lầm, như bao gồm cả M67 (được Kohler chứng minh là hợp số vào năm 1901, cụ thể: 2^{67} - 1 = 193.707.721 \times 761.838.257.287), M257 (được chứng minh là hợp số vào năm 1952), và bỏ quên M61, M89M107.

Phương pháp tốt nhất để kiểm tra tính nguyên tố của các số Mersenne được dựa vào sự tính toán một dãy tuần hoàn, được phát biểu đầu tiên bởi Lucas năm 1878 và chứng minh bởi Lehmer vào những năm 1930. Hiện nay nó được gọi là kiểm tra Lucas-Lehmer với số Mersenne. Đặc biệt, ta có thể chứng minh rằng (với n>2) M_n=2^n-1 là số nguyên tố nếu và chỉ nếu Mn chia hết cho Sn-2, trong đó S_0=4 và với k>0, S_k=S_{k-1}^2-2.

Đồ thị biểu diễn số các chữ số của số nguyên tố Mersenne lớn nhất đã biết theo từng năm của kỷ nguyên điện tử. Chú ý rằng trục tung độ đã được logarit hóa.

Việc tìm các số nguyên tố Mersenne thực sự được cách mạng bởi các máy tính điện tử số. Thành công đầu tiên của tư tưởng này thuộc về số nguyên tố Mersenne, M521, nhờ nỗ lực khéo léo vào lúc 10:00 P.M. ngày 30-1, 1952 khi sử dụng máy tính tự động Western U.S. National Bureau of Standards (SWAC) tại Institute for Numerical Analysis thuộc Đại học California tại Los Angeles, dưới sự điều khiển trực tiếp của Lehmer, sử dụng chương trình viết và chạy bởi GS R.M. Robinson. Nó là số nguyên tố Mersenne đầu tiên tìm thấy sau 38 năm; số tiếp theo, M607, đã được tìm thấy do computer này sau gần hai giờ chạy máy. Ba số tiếp theo  — M1279, M2203, M2281 — đã được tìm thấy với cùng chương trình trên sau nhiều tháng nữa. M4253 là số nguyên tố Mersenne đầu tiên là số nguyên tố siêu lớn (trên 1000 chữ số thập phân-titanic), và M44497 là số nguyên tố đẩu tiên có trên 10.000 chữ số thập phân (gigantic).

Đến tháng 9 năm 2008, chỉ mới biết 46 số nguyên tố Mersenne; số lớn nhất đã biết là số (243 112 609 − 1). Cũng như nhiều số nguyên tố Mersenne trước đó, nó được tìm ra nhờ dự án tính toán phân tán trên Internet, được biết với tên gọi Tìm kiếm số nguyên tố Mersenne khổng lồ trên Internet (Great Internet Mersenne Prime Search - GIMPS).

Các định lý về số nguyên tố Mersenne[sửa | sửa mã nguồn]

c^n-d^n=(c-d)\sum_{k=0}^{n-1} c^kd^{n-1-k},

hay

(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a}\right)=2^{ab}-1

nhờ đặt c=2^a, d=1, và n=b

chứng minh

(a-b)\sum_{k=0}^{n-1}a^kb^{n-1-k}
=\sum_{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum_{k=0}^{n-1}a^kb^{n-k}
=a^n+\sum_{k=1}^{n-1}a^kb^{n-k}-\sum_{k=1}^{n-1}a^kb^{n-k}-b^n
=a^n-b^n
  • Nếu 2^n-1 là số nguyên tố, thì n là số nguyên tố.

Chứng minh

Do

(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a}\right)=2^{ab}-1

Nếu n không là nguyên tố, hoặc n=ab trong đó 1 < a, b < n. Do đó, 2^a-1 là ước của 2^n-1, hoặc 2^n-1 không là nguyên tố.

  • Với mọi số nguyên tố p lẻ, ước nguyên tố của Mp luôn có dạng 2kp + 1 \equiv \pm 1 \pmod{8}.

Chứng minh

Gọi q là ước nguyên tố của 2p - 1 ta có:

2^p \equiv 1 \pmod{q}.

Theo định lý nhỏ Fermat ta có:

2^{q-1} \equiv 1 \pmod{q}.

Từ đó ta có q là ước chung của 2p - 1 và 2q - 1 - 1, hay là \gcd (2^p - 1,2^{q - 1} - 1) > 1(*).

Xét bổ đề sau: Nếu a và b là hai số nguyên dương phân biệt thì \gcd (2^a - 1,2^b - 1) = 2^{\gcd (a,b)} - 1.

Thật vậy giả sử \gcd (a,b) = d, suy ra a = k1d và b = k2d.

Suy ra:

2^a - 1 = 2^{k_1d} - 1 = \left (2^d - 1 \right) \times A
2^b - 1 = 2^{k_2d} - 1 = \left (2^d - 1 \right) \times B

Tức là bổ đề đã cho là đúng.

Từ bổ đề suy ra: \gcd (2^p - 1,2^{q - 1} - 1) = 2^{\gcd (p,q - 1)} - 1.

Giả sử \gcd (p,q - 1) = 1 thì suy ra được \gcd (2^p - 1,2^{q - 1} - 1) = 1, mâu thuẫn với (*). Do đó ta phải có \gcd (p,q - 1) > 1. Do p là số nguyên tố nên \gcd (p,q - 1) = p hay q - 1 = bp.

Do q là ước của Mp lẻ nên q lẻ, suy ra b = 2k hay q = 2kp + 1.

Do 2p ≡ 1 (mod q) nên 2p + 1 ≡ 2 (mod q), suy ra 2^{\frac {p + 1}{2}} là căn bậc hai của 2 theo modulo q, tức nó là nghiệm của:

x^2 \equiv 2 \pmod{q}.

Theo luật tương hỗ bậc hai:

q \equiv \pm 1 \pmod{8}.

Danh sách các số nguyên tố Mersenne đã biết[sửa | sửa mã nguồn]

(dãy A000668 trong OEIS):

# n Mn Số chữ số trong Mn Ngày tìm được Người tìm Phương pháp sử dụng
1 2 3 1 cổ đại Hy Lạp cổ đại
2 3 7 1 cổ đại Hy Lạp cổ đại
3 5 31 2 cổ đại Hy Lạp cổ đại
4 7 127 3 cổ đại Hy Lạp cổ đại
5 13 8191 4 1456 Khuyết danh
6 17 131071 6 1588 Cataldi
7 19 524287 6 1588 Cataldi
8 31 2147483647 10 1750 Euler
9 61 2305843009213693951 19 1883 Pervushin Chuỗi Lucas
10 89 618970019…449562111 27 1911 Powers
11 107 162259276…010288127 33 1914 Powers
12 127 170141183…884105727 39 1876 Lucas
13 521 686479766…115057151 157 30 tháng 1 năm 1952 Robinson
14 607 531137992…031728127 183 30 tháng 1 năm 1952 Robinson
15 1 279 104079321…168729087 386 25 tháng 6 năm 1952 Robinson
16 2 203 147597991…697771007 664 7 tháng 10 năm 1952 Robinson
17 2 281 446087557…132836351 687 9 tháng 10 năm 1952 Robinson
18 3 217 259117086…909315071 969 8 tháng 9 năm 1957 Riesel
19 4 253 190797007…350484991 1 281 3 tháng 11 năm 1961 Hurwitz
20 4 423 285542542…608580607 1 332 3 tháng 11 năm 1961 Hurwitz
21 9 689 478220278…225754111 2 917 11 tháng 5 năm 1963 Gillies
22 9 941 346088282…789463551 2 993 16 tháng 5 năm 1963 Gillies
23 11 213 281411201…696392191 3 376 2 tháng 6 năm 1963 Gillies
24 19 937 431542479…968041471 6 002 4 tháng 3 năm 1971 Tuckerman
25 21 701 448679166…511882751 6 533 30 tháng 10 năm 1978 Noll & Nickel
26 23 209 402874115…779264511 6 987 9 tháng 2 năm 1979 Noll
27 44 497 854509824…011228671 13 395 8 tháng 4 năm 1979 Nelson & Slowinski
28 86 243 536927995…433438207 25 962 25 tháng 9 năm 1982 Slowinski
29 110 503 521928313…465515007 33 265 28 tháng 1 năm 1988 Colquitt & Welsh
30 132 049 512740276…730061311 39 751 20 tháng 9 năm 1983 Slowinski
31 216 091 746093103…815528447 65 050 6 tháng 9 năm 1985 Slowinski
32 756 839 174135906…544677887 227 832 19 tháng 2 năm 1992 Slowinski & Gage trên Cray-2 tại Phòng thí nghiệm Harwell [1]
33 859 433 129498125…500142591 258 716 10 tháng 1 năm 1994 Slowinski & Gage
34 1 257 787 412245773…089366527 378 632 3 tháng 9 năm 1996 Slowinski & Gage [2]
35 1 398 269 814717564…451315711 420 921 13 tháng 11 năm 1996 GIMPS / Joel Armengaud [3]
36 2 976 221 623340076…729201151 895 932 24 tháng 8 năm 1997 GIMPS / Gordon Spence [1]
37 3 021 377 127411683…024694271 909 526 27 tháng 1 năm 1998 GIMPS / Roland Clarkson [2]
38 6 972 593 437075744…924193791 2 098 960 1 tháng 6 năm 1999 GIMPS / Nayan Hajratwala [3]
39 13 466 917 924947738…256259071 4 053 946 14 tháng 11 năm 2001 GIMPS / Michael Cameron [4]
40 20 996 011 125976895…855682047 6 320 430 17 tháng 11 năm 2003 GIMPS / Michael Shafer [5]
41* 24 036 583 299410429…733969407 7 235 733 15 tháng 5 năm 2004 GIMPS / Josh Findley [6]
42* 25 964 951 122164630…577077247 7 816 230 18 tháng 2 năm 2005 GIMPS / Martin Nowak [7]
43* 30 402 457 315416475…652943871 9 152 052 15 tháng 12 năm 2005 GIMPS / Curtis Cooper & Steven Boone [8]
44* 32 582 657 124575026…053967871 9 808 358 4 tháng 9 năm 2006 GIMPS / Curtis Cooper & Steven Boone [9]
45* 37 156 667 202254406…308220927 11 185 272 6 tháng 9 năm 2008 GIMPS / Hans-Michael Elvenich
46* 42 643 801 169873516…562314751 12 837 064 12 tháng 4 năm 2009 GIMPS / Odd M. Strindmo
47* 43 112 609 316470269…697152511 12 978 189 23 tháng 8 năm 2008 GIMPS / Edson Smith
48* 57,885,161 581887266…724285951 17,425,170 2013 January 25 GIMPS / Curtis Cooper[4] LLT / Prime95 on 3 GHz Core 2 Duo PC[5]
Số liệu tính đến tháng 2 năm 2013.
  • Chưa khẳng định được có số nguyên tố Mersenne nào nằm giữa số thứ 40 (M20 996 011) và 48 (M57 885 161) trong bảng mà chưa được phát hiện hay không, do đó thứ tự các số đó là tạm thời. Một ví dụ là số thứ 29 được phát hiện ra sau số thứ 30 và 31, số thứ 46 cũng được công bố trước số 45 chỉ có 2 tuần.
  • Để hình dung độ lớn của số nguyên tố lớn nhất được tìm thấy (số thứ 48), cần có 4 647 trang giấy A4 để biểu diễn số đó với các chữ số trong hệ cơ số 10, 75 chữ số một dòng và 50 dòng một trang. Nếu dùng giấy định lượng 70g/, sẽ cần hơn 10 kg giấy (2.324 tờ) để in thành tập dày khoảng 20 cm.

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]