Số nguyên tố Mersenne

Bách khoa toàn thư mở Wikipedia

Trong toán học, một số Mersenne là một số dạng

M_n = 2ⁿ − 1.

Một số nguyên tố Mersenne là một số Mersenne và là số nguyên tố. Điều kiện cần để M_n là số nguyên tố là n là số nguyên tố, nhưng ngược lại không đúng.

Chẳng hạn, 31 = 2⁵ − 1, và 5 là số nguyên tố , do đó 31 là số Mersenne ; và 31 cúng là nguyên tố Mersenne vì chính nó là nguyên tố. Nhưng số Mersenne 2047 = 2¹¹ − 1 không là nguyên tố ví nó chia hết cho 89 và 23. Và 2⁴ -1 = 15 là hợp số vì 4 không là nguyên tố.

Hiện nay, các số nguyên tố lớn nhất được biết 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ệcnghiê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ỷ 8, Leonhard Euler chứng minh rằng tất cả các số hoàn thiệnchẵ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.

Mục lục

1 Tìm các số nguyên tố Mersenne
2 Các định lý về số nguyên tố Mersenne
3 Danh sách các số nguyên tố Mersenne đã biết
4 Xem thêm
5 Liên kết

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

Đẳ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 M_n 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 M_n 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à is 2¹¹-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 = 31$ và $M 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$ và $M 19$ ) tìm thấy bởi Cataldi vào năm 1588. Sau hơn một thế kỷ $M 31$ được kiểm tra bởiEuler vào năm 1750. 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$ và $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 một loạt các số nguyên tố Mersenne với số mũ lên tối 257. Danh sách của ông là mắc một số sai lầm, như bao gồm cả M₆₇, M₂₅₇, và bỏ quên M₆₁, M₈₉ và M₁₀₇.

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ố nguyên tố 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 M_n chia hết cho S_n-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úu ý rằng trục tung đã được logarithm 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 , M₅₂₁, 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 University of California, 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 Prof. 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, M₆₀₇, đã được tìm thấy do computer này sau gần hai giờ chạy máy. Ba số tiếp theo more — M₁₂₇₉, M₂₂₀₃, M₂₂₈₁ — đã được tìm thấy với cùng chương trình trên sau nhiều tháng nữa. M₄₂₅₃ 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à M₄₄₄₉₇ là số nguyên tố đẩu tiên có trên 10.000 chữ số thập phân (gigantic).

Đến tháng 9-2006, chỉ mới biết 44 số nguyên tố Mersenne; số lớn nhất đã biết là số (2^32,582,657 − 1). Cũng như nhiều số nguyên tố Mersenne trước đó, nó được tìm ra nhờ dự án distributed computing trên Internet, được biết với tên gọi Great Internet Mersenne Prime Search (GIMPS).

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

Nếu n là số nguyên dương, theo định lý nhị thức ta có thể viết:

$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

$(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 = a b$ 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ố.

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

(sequence A000668 in OEIS):

#	n	M_n	Digits in M_n	Ngày tìm được	Người tìm
1	2	3	1	ancient	ancient
2	3	7	1	ancient	ancient
3	5	31	2	ancient	ancient
4	7	127	3	ancient	ancient
5	13	8191	4	1456	anonymous
6	17	131071	6	1588	Cataldi
7	19	524287	6	1588	Cataldi
8	31	2147483647	10	1750	Euler
9	61	2305843009213693951	19	1883	Pervushin
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	January 30 1952	Robinson
14	607	531137992…031728127	183	January 30 1952	Robinson
15	1,279	104079321…168729087	386	June 25 1952	Robinson
16	2,203	147597991…697771007	664	October 7 1952	Robinson
17	2,281	446087557…132836351	687	October 9 1952	Robinson
18	3,217	259117086…909315071	969	September 8 1957	Riesel
19	4,253	190797007…350484991	1,281	November 3 1961	Hurwitz
20	4,423	285542542…608580607	1,332	November 3 1961	Hurwitz
21	9,689	478220278…225754111	2,917	May 11 1963	Gillies
22	9,941	346088282…789463551	2,993	May 16 1963	Gillies
23	11,213	281411201…696392191	3,376	June 2 1963	Gillies
24	19,937	431542479…968041471	6,002	March 4 1971	Tuckerman
25	21,701	448679166…511882751	6,533	October 30 1978	Noll & Nickel
26	23,209	402874115…779264511	6,987	February 9 1979	Noll
27	44,497	854509824…011228671	13,395	April 8 1979	Nelson & Slowinski
28	86,243	536927995…433438207	25,962	September 25 1982	Slowinski
29	110,503	521928313…465515007	33,265	January 28 1988	Colquitt & Welsh
30	132,049	512740276…730061311	39,751	September 20 1983	Slowinski
31	216,091	746093103…815528447	65,050	September 6 1985	Slowinski
32	756,839	174135906…544677887	227,832	February 19 1992	Slowinski & Gage on Harwell Lab Cray-2 [1]
33	859,433	129498125…500142591	258,716	January 10 1994	Slowinski & Gage
34	1,257,787	412245773…089366527	378,632	September 3 1996	Slowinski & Gage [2]
35	1,398,269	814717564…451315711	420,921	November 13 1996	GIMPS / Joel Armengaud [3]
36	2,976,221	623340076…729201151	895,932	August 24 1997	GIMPS / Gordon Spence [4]
37	3,021,377	127411683…024694271	909,526	January 27 1998	GIMPS / Roland Clarkson [5]
38	6,972,593	437075744…924193791	2,098,960	June 1 1999	GIMPS / Nayan Hajratwala [6]
39	13,466,917	924947738…256259071	4,053,946	November 14 2001	GIMPS / Michael Cameron [7]
40^*	20,996,011	125976895…855682047	6,320,430	November 17 2003	GIMPS / Michael Shafer [8]
41^*	24,036,583	299410429…733969407	7,235,733	May 15 2004	GIMPS / Josh Findley [9]
42^*	25,964,951	122164630…577077247	7,816,230	February 18 2005	GIMPS / Martin Nowak [10]
43^*	30,402,457	315416475…652943871	9,152,052	December 15 2005	GIMPS / Curtis Cooper & Steven Boone [11]
44^*	32,582,657	124575026…053967871	9,808,358	September 4 2006	GIMPS / Curtis Cooper & Steven Boone [12]