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



tải về 123.6 Kb.
Chuyển đổi dữ liệu26.07.2016
Kích123.6 Kb.
#6333

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 để Mn là số 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


Đẳng thức

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à 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 M2 = 3, M3 = 7, M5 = 31 và M7 = 127 đã được biết từ cổ xưa. Số thứ năm, M13 = 8191, được tìm thấy vào trước năm 1461; hai số tiếp theo (M17M19) tìm thấy bởi Cataldi vào năm 1588. Sau hơn một thế kỷ M31 được kiểm tra bởi Euler vào năm 1750. Số tiếp theo (trong lịch sử, không theo thứ tự số) là M127, do Lucas tìm thấy vào năm 1876, sau đó M61 do Pervushin tìm vào năm 1883. Hai số nữa (M89M107) đượ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 đã mắc một số sai lầm, như bao gồm cả M67, M257, 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ố nguyên tố Mersenne. Đặc biệt, ta có thể chứng minh rằng (với n > 2) Mn = 2n − 1 là số nguyên tố nếu và chỉ nếu Mn chia hết cho Sn-2, trong đó S0 = 4 và với k > 0, .





Đồ 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 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, 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


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

,

hay


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



chứng minh





= anbn



  • Nếu 2n − 1 là số nguyên tố, thì n là số nguyên tố.

Chứng minh

Do



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

Danh sách các số nguyên tố Mersenne đã biết


(sequence A000668 in OEIS):

#

n

Mn

Số chữ số trong Mn

Ngày tìm được

Người tìm

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

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 [4]

37

3 021 377

127411683…024694271

909 526

27 tháng 1 năm 1998

GIMPS / Roland Clarkson [5]

38

6 972 593

437075744…924193791

2 098 960

1 tháng 6 năm 1999

GIMPS / Nayan Hajratwala [6]

39

13 466 917

924947738…256259071

4 053 946

14 tháng 11 năm 2001

GIMPS / Michael Cameron [7]

40*

20 996 011

125976895…855682047

6 320 430

17 tháng 11 năm 2003

GIMPS / Michael Shafer [8]

41*

24 036 583

299410429…733969407

7 235 733

15 tháng 5 năm 2004

GIMPS / Josh Findley [9]

42*

25 964 951

122164630…577077247

7 816 230

18 tháng 2 năm 2005

GIMPS / Martin Nowak [10]

43*

30 402 457

315416475…652943871

9 152 052

15 tháng 12 năm 2005

GIMPS / Curtis Cooper & Steven Boone [11]

44*

32 582 657

124575026…053967871

9 808 358

4 tháng 9 năm 2006

GIMPS / Curtis Cooper & Steven Boone [12]

45*

37 156 667

202254406…308220927

11 185 272

6 tháng 9 năm 2008

GIMPS / Hans-Michael Elvenich

46*

43 112 609

316470269…697152511

12 978 189

23 tháng 8 năm 2008

GIMPS / Edson Smith

  • Chưa khẳng định được có số nguyên tố Mersenne nào nằm giữa số thứ 39 (M 13 466 917) và 46 (M43 112 609) 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 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ứ 46), cần có 3 461 trang giấy để 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.

Каталог: resources
resources -> HƯỚng dẫn sử DỤng tài liệU Ôn tập thi thpt quốc gia môN: tiếng anh
resources -> KHỔ giấY, kiểu trình bày và ĐỊnh lề trang văn bảN a Khổ giấy
resources -> THỦ TƯỚng chính phủ CỘng hoà XÃ HỘi chủ nghĩa việt nam
resources -> CỦa chính phủ SỐ 01/2003/NĐ-cp ngàY 09 tháng 01 NĂM 2003
resources -> Nghị ĐỊnh của chính phủ SỐ 205/2004/NĐ-cp ngàY 14 tháng 12 NĂM 2004 quy đỊnh hệ thống thang lưƠNG, BẢng lưƠng và chế ĐỘ phụ CẤp lưƠng trong các công ty nhà NƯỚC
resources -> CHÍnh phủ Cộng hoà xã hội chủ nghĩa Việt Nam Độc lập Tự do Hạnh phúc
resources -> QuyếT ĐỊnh của bộ TÀi chính số 32/2008/QĐ-btc ngàY 29 tháng 05 NĂM 2008 VỀ việc ban hành chế ĐỘ quản lý, TÍnh hao mòN
resources -> Ban tổ chức số 09-hd/btctw đẢng cộng sản việt nam

tải về 123.6 Kb.

Chia sẻ với bạn bè của bạn:




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương