Luận văn Thạc sĩ Toán học: Các ước số của số Mersenne

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:56

Thêm vào BST

Báo xấu

37
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn có hai mục tiêu chính: Giới thiệu một bức tranh toàn cảnh về lịch sử phát triển của số hoàn hảo và số Mersenne, những phát kiến và sai lầm trong quá trình nghiên cứu số Mersenne và số hoàn hảo. Trình bày một số kết quả nghiên cứu hiện đại về các ước số của số Mersenne. Đây là một vấn đề quan trọng, đặc biệt trong việc tìm ra những số nguyên tố lớn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Các ước số của số Mersenne

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM THỊ PHƯỢNG CÁC ƯỚC SỐ CỦA SỐ MERSENNE Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM THỊ PHƯỢNG CÁC ƯỚC SỐ CỦA SỐ MERSENNE Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. HÀ HUY KHOÁI Thái Nguyên - 2017
i Mục lục Danh mục các ký hiệu, các chữ viết tắt iii Mở đầu 1 1 Số hoàn hảo, số Mersenne trong lịch sử 3 1.1 Số hoàn hảo, từ Pythagoras đến Euler . . . . . . . . . . . . 3 1.2 Số Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Một số tính chất đặc biệt của số hoàn hảo chẵn . . . . . . . 18 1.4 Số hoàn hảo lẻ . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Các ước nguyên tố của số Mersenne 25 2.1 Ước lượng cận trên của tổng nghịch đảo các ước nguyên tố của số Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1 Phát biểu kết quả . . . . . . . . . . . . . . . . . . . . 25 2.1.2 Một số bài toán . . . . . . . . . . . . . . . . . . . . . 28 2.1.3 Chứng minh các Định lí 2.1 - 2.3 . . . . . . . . . . . 30 2.1.4 Chứng minh Định lí 2.4 . . . . . . . . . . . . . . . . 36 2.2 Ước lượng cận dưới của tổng nghịch đảo các ước nguyên tố của số Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2.1 Một số kết quả . . . . . . . . . . . . . . . . . . . . . 40 2.2.2 Các bổ đề . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2.3 Chứng minh Định lí 2.5 . . . . . . . . . . . . . . . . 46 Kết luận và kiến nghị 51 Tài liệu tham khảo 52
ii Danh mục các ký hiệu, các chữ viết tắt φ(m) Hàm Euler của m. σ(m) Hàm tổng các ước của m. τ (m) Hàm số các ước của m. Ω(m) Số thừa số nguyên tố của m. ω(m) Tương ứng tính bội hoặc không tính bội của m. log x Logarit tự nhiên của x. [a, b] Bội chung nhỏ nhất của hai số a, b. (a, b) Ước chung lớn nhất của hai số a, b.
1 Mở đầu Các số Mersenne và số hoàn hảo là đề tài xuyên suốt của lý thuyết số, từ thời Hy Lạp cổ đại cho đến ngày hôm nay. Đây là một chủ đề vừa phù hợp với chương trình Toán bậc THPT, lại vừa chứa đựng những nghiên cứu mới. Dưới sự hướng dẫn tận tình của GS.TSKH. Hà Huy Khoái, tác giả chọn đề tài " Các ước số của số Mersenne". Luận văn có hai mục tiêu chính: - Giới thiệu một bức tranh toàn cảnh về lịch sử phát triển của số hoàn hảo và số Mersenne, những phát kiến và sai lầm trong quá trình nghiên cứu số Mersenne và số hoàn hảo. - Trình bày một số kết quả nghiên cứu hiện đại về các ước số của số Mersenne. Đây là một vấn đề quan trọng, đặc biệt trong việc tìm ra những số nguyên tố lớn. Với mục tiêu trên, tác giả tiến hành nghiên cứu hai nội dung chính tương ứng với hai chương: Chương 1. Số hoàn hảo, số Mersenne trong lịch sử 1.1. Số hoàn hảo, từ Pythagoras đến Euler 1.2. Số Mersenne 1.3. Một số tính chất đặc biệt của số hoàn hảo chẵn 1.4. Số hoàn hảo lẻ Chương 2. Các ước nguyên tố của số Mersenne 2.1. Ước lượng cận trên của tổng nghịch đảo các ước nguyên tố của số Mersenne
2 2.2. Ước lượng cận dưới của tổng nghịch đảo các ước nguyên tố của số Mersenne Qua bản luận văn này, tác giả xin gửi lời cảm ơn tới Ban Giám hiệu trường Đại học Khoa học - Đại học Thái Nguyên, Khoa Toán - Tin, cùng các giảng viên đã tham gia giảng dạy và tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu trong suốt thời gian qua. Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới Giáo sư - Tiến sĩ khoa học Hà Huy Khoái - người đã tận tình, chỉ bảo, động viên khích lệ tác giả trong suốt quá trình học tập và thực hiện luận văn. Cuối cùng, tác giả xin cảm ơn gia đình, bạn bè, đồng nghiệp và tất cả mọi người đã quan tâm, động viên và giúp đỡ để tác giả có thể hoàn thành luận văn của mình. Tác giả rất mong nhận được ý kiến đóng góp của quý độc giả để bản luận văn này được hoàn thiện hơn. Tác giả xin chân thành cảm ơn!
3 Chương 1 Số hoàn hảo, số Mersenne trong lịch sử 1.1 Số hoàn hảo, từ Pythagoras đến Euler Định nghĩa đầu tiên về số hoàn hảo dùng khái niệm gọi là "phần chia hết", nguyên gốc là "aliquot parts", vốn có nguồn gốc từ tiếng Latin, trong đó "ali" có nghĩa là "khác" và "quot" nghĩa là "có bao nhiêu". Một "phần chia hết" của một số là một thương thực sự của số đó, nghĩa là thương khác số ban đầu. Ví dụ 1, 2 và 5 là các "phần chia hết" của 10 vì 10 10 10 1= ,2 = ,5 = , 10 5 2 còn 10 không phải là một "phần chia hết" vì 10 không phải là một thương thực sự của 10. Định nghĩa nguyên thủy: Một số được gọi là hoàn hảo nếu nó bằng tổng các "phần chia hết" của nó. Ví dụ. +) Số 6 có các phần chia hết là 1, 2, 3 và 1 + 2 + 3 = 6 nên số 6 là một số hoàn hảo. +) Số 10 có các phần chia hết là 1, 2, 5 và 1 + 2 + 5 = 8 nên số 10 không phải là một số hoàn hảo. Để có một định nghĩa hiện đại, người ta dùng khái niệm sau
4 Định nghĩa 1.1 Hàm tổng các ước là hàm X σ(n) = d, d|n trong đó n là một số nguyên dương và tổng chạy qua tất cả các ước nguyên dương của n (bao gồm cả 1 và chính nó). Nhờ khái niệm này, ta có Định nghĩa 1.2 Một số tự nhiên n được gọi là hoàn hảo nếu σ(n) = 2n. Khi σ(n) < 2n thì n được gọi là thiếu và khi σ(n) > 2n thì n được gọi là thừa. Ví dụ. +) Số 12 có các ước số là 1, 2, 3, 4, 6 và 12. Ta có σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28 > 12. Do đó số 12 là một số thừa. +) Số 10 là số thiếu vì σ(10) = 1 + 2 + 5 + 10 = 18 < 20 . +) Các số 6, 28 là các số hoàn hảo vì σ(6) = 1 + 2 + 3 + 6 = 12, và σ(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56. Một cách tương đương, một số là hoàn hảo khi nó bằng tổng các ước thực sự của nó. Theo tác giả C.M.Taisbak, dường như người Ai Cập cổ đại là những người đầu tiên sử dụng số hoàn hảo trong các tính toán của mình. Aurelius Augustinus (354 – 430) trong quyển "The City of God" nhắc lại rằng Chúa trời thực hiện sự sáng tạo ra thế giới muôn loài trong 6 ngày, bởi vì sự hoàn hảo của công việc được thể hiện ở số 6. Nguồn gốc thứ hai của loài người sinh ra từ số thiếu 8: Kinh thánh nói rằng trong chiếc tàu của Noah có 8 linh hồn từ đó xuất hiện ra toàn bộ loài người, nhưng quá trình sáng tạo này không được hoàn hảo vì 8 là số "thiếu". Nguồn gốc này xem chừng không được coi trọng bằng nguồn gốc thứ nhất bởi lí do đơn giản: 6 là số hoàn hảo! Mặt trăng quay một vòng quanh Trái đất hết 28 ngày cũng bởi lí do 28 là một số hoàn hảo.
5 Theo Pythagoras, sự hoàn hảo của các con số phụ thuộc vào các ước số của nó. Những người theo trường phái Pythagoras luôn luôn tin tưởng vào số 6, họ xem nó là số đẹp nhất, tượng trưng cho sức khỏe và vẻ đẹp của con người. Pythagoras còn cho rằng con số 6 là hoàn hảo không phải là do Chúa đã chọn nó, mà bởi vì sự hoàn hảo là thuộc tính sở hữu của con số đó: "số 6 tự nó đã là hoàn hảo chứ không phải vì Chúa đã tạo ra vạn vật trong 6 ngày, thực ra thì ngược lại mới đúng, Chúa đã tạo ra vạn vật trong 6 ngày bởi vì đó là con số hoàn hảo và nó vẫn cứ hoàn hảo thậm chí nếu như chuyện đó không xảy ra." Trong quyển "Cơ sở" của Euclid, viết khoảng 300 năm trước Công nguyên, mệnh đề 36 trong quyển thứ 9 của bộ "Cơ sở" nói rằng "Bắt đầu từ đơn vị, gấp đôi liên tục rồi lấy tổng cho đến khi kết quả là một số nguyên tố, đem nhân với số cuối cùng trong tổng, ta sẽ nhận được một số hoàn hảo". Sau đây ta thực hiện từng bước theo Euclid. Dãy số mà Euclid nói đến là 1, 2, 4, 8, 16, 32, . . . Lấy tổng các số đầu tiên trong dãy ta có các kết quả 1 + 2 = 3; 1 + 2 + 4 = 7; 1 + 2 + 4 + 8 = 15; 1 + 2 + 4 + 8 + 16 = 31. Ta chọn ví dụ số 31. Đem nhân với số cuối cùng trong tổng ta có 31.16 = 496, là một số hoàn hảo! Euclid cũng đã chứng minh được rằng nếu p = 1 + 2 + 22 + . . . .. + 2n là một số nguyên tố thì 2n p là một số hoàn hảo. Ông chỉ ra rằng 2n p có tất cả các ước thực sự là 1, 2, . . . , 2n , p, 2p, . . . , 2n−1 p và tổng của chúng đúng bằng 2n p. Theo ngôn ngữ hiện đại, mệnh đề của Euclid trở thành
6 Mệnh đề 1.1 Nếu n là số nguyên lớn hơn 1 thỏa mãn 2n − 1 là một số nguyên tố thì 2n−1 (2n − 1) là một số hoàn hảo. Các nhà toán học sau này thường gọi phát hiện này là Định lí Euclid và các số có dạng 2n−1 (2n − 1) (trong đó 2n − 1 là một số nguyên tố) là số Euclid. Nhưng Euclid mới chỉ cho chúng ta một chiều, và do đó một câu hỏi được đặt ra là: liệu còn số hoàn hảo nào khác không nằm trong các số có dạng này không? Đây có thể nói là một trong những vấn đề quan trọng trong lịch sử nghiên cứu số hoàn hảo. Công trình ý nghĩa tiếp theo sau Euclid mà ta phải nhắc đến là của nhà toán học Nicomachus (60-120 sau Công nguyên). Năm 100, Nicomachus viết quyển "Introductio Arithmetica" trong đó ông phân loại các số dựa vào khái niệm số hoàn hảo. Theo đó, có 3 loại: số thừa, số thiếu và số hoàn hảo. Nicomachus đề ra các kết quả liên quan đến số hoàn hảo, đó là 5 khẳng định (hay phán đoán?) sau 1. Số hoàn hảo thứ n có n chữ số. 2. Mọi số hoàn hảo đều chẵn. 3. Số hoàn hảo có chữ số cuối cùng luân phiên giữa 6 và 8. 4. Mọi số hoàn hảo đều có dạng 2n−1 (2n − 1) trong đó n > 1 và 2n − 1 là một số nguyên tố. 5. Có vô hạn số hoàn hảo. Năm khẳng định của Nicomachus chỉ có được từ sự phân tích cách tìm số hoàn hảo của Euclid đã nói ở trên và chỉ với 4 ví dụ về số hoàn hảo thời điểm đó: 6, 28, 496, 8128. Và mặc dù chưa được kiểm chứng nhưng chúng đã được công nhận trong nhiều năm. Đến tận thời kì đầu giai đoạn Phục Hưng ở châu Âu (khoảng năm 1500), các khẳng định của Nicomachus vẫn được xem là đúng. Carolus Bovillus (1470 − 1553) - một nhà thần học và triết học xuất bản một cuốn sách về số hoàn hảo năm 1509, trong đó ông cho rằng mọi số hoàn hảo là số chẵn, nhưng chứng minh của ông chỉ áp dụng được cho các số Euclid.
7 Bovilus khẳng định 2n − 1 là một số nguyên tố nếu n là số lẻ, chẳng hạn với n = 3, 5, 7 ta được các số 7, 31, 127 là các số nguyên tố. Khẳng định này rõ ràng sai vì với n = 9, 11, các số 511, 2047 là hợp số. Ông còn đưa ra danh sách các số hoàn hảo dạng 2n−1 (2n − 1) với n là các số lẻ không vượt quá 39 và lại sai một lần nữa! (có 8 số thuộc vào danh sách này không phải là hoàn hảo). Tuy nhiên, cùng với ông, cũng có các nhà toán học cùng mắc chung sai lầm như vậy còn rất nhiều: De la Roche, Giradus Ruffus,... Năm 1536, Hudalrichus Regius đã làm nên bước đột phá khi xuất bản cuốn "Utriusque Arithmetices", trong đó ông đưa ra phân tích 211 − 1 = 2047 = 23.89. Như vậy, ông là người tìm ra số nguyên tố p đầu tiên để 2p−1 (2p − 1) không phải là một số hoàn hảo. Pierre de Fermat (1601 − 1665) trong thư gửi Mersenne ngày 26 − 12 − 1638 tin tưởng rằng mình có một phương pháp "toàn năng" để giải quyết tất cả các câu hỏi liên quan đến ước thực sự. Fermat viết 2 dãy số liền nhau như sau 1 2 3 4 5 6 7 8 9 10 11 12 13 1 3 7 15 31 63 127 255 511 1023 2047 4095 8191 trong đó dãy ở trên là dãy các số tự nhiên liên tiếp, còn dãy ở dưới là dãy (2n − 1), ứng với các số n ở ngay trên nó. Fermat phát hiện được các tính chất sau: 1. Nếu một số ở dòng trên là hợp số thì số ở dòng dưới tương ứng cũng là hợp số. Chẳng hạn 6 ở dòng trên là hợp số và 63 ở dòng dưới cũng là hợp số. 2. Nếu một số ở dòng trên là nguyên tố thì số ở dòng dưới tương ứng trừ đi 1 phải chia hết cho 2 lần số ở dòng trên. Chẳng hạn 7 là nguyên tố và số ở dòng dưới 127 thỏa mãn 126 chia hết cho 14. 3. Nếu số ở trên là nguyên tố thì số ở dưới tương ứng không chia hết cho số nguyên tố nào khác ngoại trừ các số lớn hơn 1 so với một bội nào
8 đó của 2 lần số trên. Chẳng hạn 11 là nguyên tố và 2047 chỉ có 2 ước nguyên tố là 23 và 89, cả 2 đều có dạng 22k + 1. Bài toán tìm công thức số hoàn hảo chẵn chỉ được giải quyết trọn vẹn và chính xác dưới bàn tay của bộ óc vĩ đại Leonard Euler (1707-1783). Euler chú ý rằng 2n − 1 có thể là hợp số kể cả khi n là số nguyên tố, chẳng hạn 211 − 1 = 23.89. Với n là nguyên tố có dạng 4m − 1 hoặc 8m − 1 thì 2n − 1 có ước là 8m − 1. Ông đã viết: "Tôi tin rằng ngoài các trường hợp kể trên, 2n−1 (2n − 1) sẽ là số hoàn hảo với các giá trị nguyên tố của n không vượt quá 100. Euler sau đó đã tự mình tìm ra lỗi trong phát biểu đầu tiên cho các trường hợp n bằng 41 và 47. Năm 1738, Euler chứng minh được 229 − 1 không nguyên tố, và do đó phủ định phán đoán của Nicomachus. Năm 1747, từ định lí Fermat, Euler chứng minh kết quả: nếu n là một số nguyên tố sao cho 2n − 1 là hợp số thì 2n − 1 không có các ước số khác dạng mn + 1, và lập bảng các ước nguyên tố của 2n − 1 với n ≤ 37. Và đến năm 1749, ông chứng minh được mọi số hoàn hảo chẵn là số Euclid, qua đó đã kiểm chứng phán đoán của Nicomachus, ít nhất là trong trường hợp các số hoàn hảo chẵn. Định lí 1.1 (Euler) Nếu a là một số hoàn hảo chẵn thì a có thể viết dưới dạng a = 2k−1 (2k − 1), trong đó 2k − 1 là một số nguyên tố. Chứng minh. Giả sử a = 2n b là một số hoàn hảo, trong đó b lẻ. Gọi B là tổng các ước của b. Tổng các ước của a bằng 2a vì a là số hoàn hảo, trong khi tổng các ước của 2n b là (2n+1 − 1)B, vì vậy (2n+1 − 1)B = 2a = 2n+1 b, và do đó b = (2n+1 − 1)c với c là số nguyên nào đó (vì 2n+1 − 1 và 2n+1 nguyên tố cùng nhau).
9 Nếu c > 1 thì B ≥ b + 2n+1 − 1 + c + 1 = 2n+1 (c + 1), suy ra B 2n+1 (c + 1) 2n+1 ≥ > n+1 , b b 2 −1 hay B(2n+1 − 1) > 2n+1 b, mâu thuẫn! Vậy c = 1, lúc đó b = 2n+1 − 1 và phải là một số nguyên tố vì tổng các ước của nó là B = 2n+1 . Điều này có nghĩa là a là một số Euclid. Kết quả của Euler đã kết thúc quá trình lâu dài đi tìm công thức số hoàn hảo chẵn, đồng thời chính thức khẳng định mối quan hệ giữa số hoàn hảo và số nguyên tố dạng 2n − 1, gọi là số nguyên tố Mersenne mà ngay sau đây ta tìm hiểu. 1.2 Số Mersenne Như đã nói ở trên, sau các kết quả mang tính đột phá của mình, Hu- dalrichus Regius đã tìm được số hoàn hảo thứ 5 là 212 (213 − 1). Năm 1555, J.Scheybl đưa ra được số hoàn hảo thứ 6 trong bài bình luận về tác phẩm "Cơ sở" của Euclid. Chỉ dẫn của Euclid giúp các nhà toán học định hướng vào việc phát hiện các số nguyên tố dạng 2n − 1. Mặc dù một kết luận chính xác về số hoàn hảo chẵn được Euler đưa ra vào năm 1749 và khái niệm số nguyên tố Mersenne mới chỉ xuất hiện sau này, nhưng các khám phá về các số dạng 2n − 1 đã có từ trước đó rất lâu. Ta có định nghĩa về số Mersenne như sau Định nghĩa 1.3 Giả sử m là một số nguyên dương, khi đó Mm = 2m − 1 được gọi là số Mersenne thứ m. Nếu p là số nguyên tố và Mp cũng nguyên tố, thì Mp được gọi là số nguyên tố Mersenne.
10 Ví dụ. M2 , M3 , M5 , M7 là các số nguyên tố Mersenne. M11 là hợp số. Các số có dạng này được đặt theo tên của Marin Mersenne (1588−1648) - nhà thần học, triết học, toán học, nhạc lý học người Pháp, người được xem là "trung tâm của khoa học Paris những năm đầu thế kỉ 17". Năm 1603, nhà toán học người Ý Cataldi (1548 − 1626) tìm được phân tích nguyên tố của tất cả các số không vượt quá 800, và lập bảng các số nguyên tố đến 750 (có 132 số nguyên tố). Dùng bảng này, Cataldi đã chứng tỏ rằng 217 − 1 = 131071, là một số nguyên tố. Cataldi đã làm mất 132 phép tính. Từ kết quả đó, ông tìm được số hoàn hảo thứ 6 là 216 (217 − 1) = 8589869056. Đến lúc này thì khẳng định của Nicomachus rằng số hoàn hảo luân phiên tận cùng 6 và 8 đã bị bác bỏ, vì số hoàn hảo thứ 5 và 6 đều tận cùng là 6. Cataldi cũng dùng phương pháp tương tự để kiểm tra 219 − 1 = 524287 là một số nguyên tố và vì thế số hoàn hảo thứ 7 được phát hiện 218 (219 − 1) = 137438691328. Mặc dù đạt được các kết quả tuyệt vời như vậy, Cataldi vẫn mắc sai lầm. Ông cho rằng các số mũ ứng với n = 2, 3, 5, 7, 13, 17, 19, 23, 29, 31, 37 trong công thức 2n−1 (2n − 1) sẽ cho ta các số hoàn hảo. Khẳng định này sai với n = 23, 29, 37. Có thể tin rằng, Fermat đã tìm ra một định lí nổi tiếng nhờ nghiên cứu số hoàn hảo. Định lí được phát biểu như sau: "Cho p là một số nguyên tố và a là một số nguyên không chia hết cho p, khi đó ap−1 − 1 chia hết cho p" (Định lý Fermat nhỏ). Sử dụng Định lý Fermat nhỏ của mình, ông đưa ra bác bỏ cho 2 khẳng định trước đó của Cataldi bằng cách chỉ ra 223 − 1 và 237 − 1 là hợp số.
11 Không những chỉ ra nó là hợp số, ông còn chỉ cho Mersenne cách phân tích 237 − 1 = 223.616318177. Năm 1484, nhà toán học Pháp Luca Paciuolo de Borgo San Sepolero sau khi đưa ra được quy tắc Euclid, trong đó phải thử xem 1 + 2 + 4 + . . . + 2n có là số nguyên tố hay không, đã khẳng định số hoàn hảo thứ 14 là 9007199187632128. Ông lí giải như sau: lấy 9007199187632128 chia cho 2, rồi lại lấy thương tiếp tục chia cho 2 và cứ tiếp tục như vậy. Sau 26 phép chia ông nhận được số 134217727. Như vậy, số ban đầu có các ước là 1, 2, 22 , . . . , 226 và 134217727. Để ý rằng 1 + 2 + 22 + ... + 226 + 134217727 = 9007199187632128, và do đó 9007199187632128 phải là một số hoàn hảo. Tuy nhiên, điều này không đúng, đơn giản vì số 134217727, được ông đánh dấu là "không chia được nữa" (ám chỉ nó là một số nguyên tố) lại không phải là một số nguyên tố, nó có ước là 7 (điều này đã được các nhà toán học Bovilus và Cataldi chỉ ra sau đó: 9007199187632128 là một số thừa). E.Lucas cũng đạt được một số kết quả rất hay là: mọi số hoàn hảo chẵn ngoài 6 và 496 tận cùng là 16, 28, 36, 56 hay 76; số hoàn hảo bất kỳ trừ 28 có dạng 7k ± 1 ; số hoàn hảo bất kỳ trừ 6 có số dư 1, 2, 3 hay 8 khi chia cho 13. Các kết quả nói ở trên của Fermat làm Mersenne rất thích thú. Năm 1646, Mersenne xuất bản cuốn "Cogitata physica mathematica" trong đó có nêu Giả thuyết 1.1 (Mersenne, 1646) 2n −1 là nguyên tố (và do đó 2n−1 (2n − 1) là số hoàn hảo) với các giá trị sau của n n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, và là hợp số với 44 giá trị nguyên tố khác của n ≤ 257. Tuy vậy, Mersenne không thể nào kiểm tra được kết quả này mà chỉ thừa nhận, ông viết
12 "Để kiểm tra một số có 15 hay 20 chữ số có nguyên tố hay không chắc phải mất cả đời!" Nhưng đáng kinh ngạc là trong 47 số nguyên tố từ 19 đến 257, phán đoán của Mersenne đúng đến 42 số. Năm 1679, Joh. Wilh. Pauli chỉ ra 211 − 1 chia hết cho 23, 223 − 1 chia hết cho 47, 241 − 1 chia hết cho 83, qua đó đưa ra câu trả lời phủ định cho nhận định của G.W.Leibniz (1646-1716) rằng 2p − 1 là số nguyên tố nếu và chỉ nếu p là số nguyên tố. Cụ thể hơn, Cataldi và Fermat đã chỉ ra Mệnh đề 1.2 Nếu 2n − 1 là nguyên tố thì n phải là một số nguyên tố. Chứng minh. Khẳng định này có thể chứng minh rất đơn giản. Giả sử n = r.s với r, s > 1. Khi đó 2n − 1 = (2r )s − 1 = (2r − 1)((2r )s−1 + . . . + 2r + 1) Điều này có nghĩa 2n − 1 là hợp số. Năm 1732, tức hơn 100 năm sau khi phát hiện số hoàn hảo thứ 7, Leonard Euler chứng minh được 231 − 1 là nguyên tố, do đó tìm ra 230 (231 − 1) = 2305843008139952128, là số hoàn hảo thứ 8. Năm 1738, Euler đã chứng tỏ 229 − 1 = 536870911 = 233.1103.2089. Số hoàn hảo thứ 8 của Euler là số lớn nhất được biết trong vòng 150 năm tính đến thời điểm đó. Đến mức một số nhà toán học như Peter Barlow, đã viết trong quyển "Lý thuyết số" xuất bản năm 1811 về số hoàn hảo 230 (231 − 1), rằng "Nó là số hoàn hảo lớn nhất mà chúng ta từng biết, chắc không còn ai có thể tìm được số nào lớn hơn nó nữa" Đây rút cuộc cũng chỉ là một trong vô số các phán đoán sai liên quan đến số hoàn hảo! Lỗi đầu tiên trong bảng của Mersenne được phát hiện năm 1876 bởi E.Lucas khi ông chứng tỏ được 267 − 1 là một hợp số. Lucas sau đó đã xác
13 minh 2127 − 1 là một số nguyên tố có 39 chữ số. Ông nói rằng mình có một kĩ thuật kiểm tra có hay không khẳng định của Mersenne rằng 2n − 1 là số nguyên tố với n = 53, 67, 127, 257 một cách chính xác. Ông lập bảng các nhân tử nguyên tố của 2n − 1 với n ≤ 40. Ông cũng đưa ra một bảng gồm những số nguyên tố với 12 đến 16 chữ số là nhân tử của 2n − 1 với n = 49, 59, 65, 69, 87 và của 2n + 1 với n = 43, 47, 49, 53, 69, 72, 75, 86, 94, 98, 99, 135 và những giá trị chẵn khác của n > 100. Các ý tưởng và phương pháp của Lucas thực sự mang tính cách tân và nó đã trở thành cơ sở cho việc phát hiện các số nguyên tố Mersenne sau này dựa vào máy tính. Đến năm 1930, Lehmer đã cải tiến phép thử và viết nó dưới dạng đơn giản sau Mệnh đề 1.3 (Phép thử Lucas-Lehmer) Cho p là một số nguyên tố lẻ. Khi đó 2p − 1 là nguyên tố khi và chỉ khi 2p − 1 là ước của S(p − 1) trong đó dãy S(n) xác định bởi  S(n + 1) = S(n)2 − 2 S(1) = 4 Viết dưới dạng một thuật toán như sau: Lucas − Lehmer − T est(p): s := 4; for i from 3 to p do s := s2 − 2 (mod 2p − 1); if s = 0 then 2p − 1 is prime else 2p − 1 is composite Năm 1883, Pervouchine phát hiện 261 −1 là nguyên tố, nghĩa là Mersenne đã thiếu số 61. Đến năm 1911, các số bị thiếu tiếp theo được chỉ ra bởi Powers khi ông chứng minh 289 − 1 là một số nguyên tố, và 2107 − 1 là nguyên tố một năm sau đó.
14 Năm 1922, Kraitchik chứng tỏ được Mersenne đã sai với số nguyên tố cuối cùng trong dãy: 2257 − 1 là một hợp số. Cuối cùng, đến năm 1947 bảng của Mersenne đã được kiểm tra hoàn toàn và kết quả cuối cùng: 2n − 1, n ≤ 257 là nguyên tố với các số sau: n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127. Dựa vào phát hiện của Lucas nói rằng 127 là một số nguyên tố Mersenne và 2127 − 1 cũng là một số như vậy, Catalan đã đưa ra dự đoán Giả thuyết 1.2 (Catalan) Các số an , n ≥ 1 đều là số nguyên tố (và do đó là số nguyên tố Mersenne), trong đó dãy (an )n được cho bởi  an n+1 = 2 − 1 a a = 2 0 Hiển nhiên nếu giả thuyết này đúng thì câu hỏi về việc có tồn tại vô hạn số nguyên tố Mersenne (suy ra tồn tại vô hạn số hoàn hảo) được giải quyết. Dễ thấy a1 = 3, a2 = 7, a3 = 127, đều là số nguyên tố, còn a4 = 2127 − 1 là nguyên tố theo Lucas. Người ta vẫn chưa kiểm tra được a5 , một con số to khủng khiếp, có phải là nguyên tố hay không. Nên biết là số Mersenne lớn nhất vừa tìm ra năm 2017 là 274,207,281 − 1, có 22,338,618 chữ số. Cũng tương tự với dự đoán của Catalan, có thêm một dự đoán nữa như sau Dự đoán 1.1 Nếu n là một số nguyên tố Mersenne thì 2n − 1 cũng là một số nguyên tố Mersenne. 13 17 19 31 −1 −1 −1 −1 Tuy nhiên, bốn số 22 − 1, 22 − 1, 22 − 1 và 22 − 1 đã được kiểm tra là hợp số và do đó dự đoán này bị bác bỏ. Năm 1989, Bateman, Selfridge và Wagstaff đưa ra giả thuyết sau. Giả thuyết 1.3 Cho p là một số tự nhiên lẻ. Nếu hai trong ba điều kiện sau thỏa mãn thì điều kiện còn lại cũng được thỏa mãn:
15 1. p = 2k ± 1 hoặc p = 4k ± 3. 2. 2p − 1 là nguyên tố . 2p + 1 3. là nguyên tố. 3 Tới tháng 9-2008, có 46 số hoàn hảo được phát hiện, trong đó số 288 (289 − 1) là số lớn nhất được phám phá bằng tính toán nhờ giấy bút và số nguyên tố Mersenne thứ 45 được tìm thấy 243112609 − 1, với hơn 10 triệu chữ số. Và chỉ một tháng sau, số nguyên tố Mersenne thứ 46 được tìm thấy là 237156667 − 1, nhỏ hơn số ở trên! George Woltman, một lập trình viên đưa lên một chương trình được tối ưu hóa cực cao phục vụ cho công cuộc tìm kiếm. Đó chính là chương trình GIMPS (Great Internet Mersenne Prime Search), thu hút hàng chục chuyên gia và hàng nghìn người nghiệp dư tham gia tìm kiếm. Số nguyên tố Mersenne lớn nhất hiện nay do ông tìm ra nhờ việc cho chương trình quét qua tất cả các lỗ hổng chưa được kiểm tra trước đó. Năm 2013, số nguyên tố Mersenne đã tìm ra là 257885161 − 1 có 17425170 chữ số. Quỹ Electronic Frontier Foundation (www.eff.org) trao giải thưởng 150.000 USD cho ai tìm được số nguyên tố Mersenne có trên 100 triệu chữ số và 250.000 USD cho số có trên 1 tỉ chữ số và 3000 USD cho bất kỳ số nguyên tố mới nào dưới 100 chữ số. Đến ngày 7 − 1 − 2017, số nguyên tố Mersenne mới nhất được công bố trong lễ kỷ niệm 20 năm ngày thành lập GIMPS. Đó là 274,207,281 − 1, có 22,338,618 chữ số. Bảng sau đây gồm 49 số nguyên tố Mersenne đã được biết đến năm 2017, trong đó ta ký hiệu Mp = 2p − 1 là số nguyên tố Mersenne và Np là số hoàn hảo 2p−1 (2p − 1) ứng với số nguyên tố p.
16 Số thứ tự p Số chữ số của Mp Số chữ số của Np Năm phát hiện Người phát hiện (1) (2) (3) (4) (5) (6) 1 2 1 1 ... ... 2 3 1 2 ... ... 3 5 2 3 ... ... 4 7 3 4 ... ... 5 13 4 8 1456 ... 6 17 6 10 1588 Cataldi 7 19 6 12 1588 Cataldi 8 31 10 19 1772 Euler 9 61 19 37 1883 Pervushin 10 89 27 54 1911 Powers 11 107 33 65 1914 Powers 12 127 39 77 1876 Lucas 13 521 157 314 1952 Robinson 14 607 183 366 1952 Robinson 15 1279 386 770 1952 Robinson 16 2203 664 1327 1952 Robinson 17 2281 687 1373 1952 Robinson 18 3217 969 1937 1957 Riesel 19 4253 1281 2561 1961 Hurwitz 20 4423 1332 2663 1961 Hurwitz 21 9689 2917 5834 1963 Gillies 22 9941 2993 5985 1963 Gillies 23 11213 3376 6751 1963 Gillies 24 19937 6002 12003 1971 Tuckerman Bảng 1.1: Bảng 24 số nguyên tố Mersenne đầu tiên