ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC LƯƠNG THỊ BĂNG MỘT SỐ VẤN ĐỀ VỀ LÝ THUYẾT SỐ NGUYÊN TỐ CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP MÃ SỐ: 60.46.40 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 - 2010 Số hóa Trung tâm Học liệu - Đại học Thái Ngun http://www.lrc-tnu.edu.vn Cơng trình hồn thành TRƯỜNG ĐẠI HỌC KHOA HỌC - ĐẠI HỌC THÁI NGUYÊN Người hướng dẫn khoa học:GS.TSKH HÀ HUY KHOÁI Phản biện 1: Phản biện 2: Luận văn bảo vệ trước hội đồng chấm luận văn họp tại: TRƯỜNG ĐẠI HỌC KHOA HỌC - ĐẠI HỌC THÁI NGUYÊN Ngày tháng năm 2010 Có thể tìm hiểu THƯ VIỆN ĐẠI HỌC THÁI NGUYÊN Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lời cảm ơn Luận văn hồn thành hướng dẫn tận tình nghiêm khắc GS.TSKH Hà Huy Khối Tơi xin bày tỏ lịng kính trọng biết ơn sâu sắc tới Thầy gia đình Tơi xin chân thành cảm ơn Ban giám hiệu trường Đại học Khoa học, Phòng đào tạo nghiên cứu khoa học quan tâm giúp đỡ, tạo điều kiện thuận lợi cho học tập tốt Tôi xin chân thành cảm ơn Sở Giáo dục Đào tạo Tỉnh Bắc Kạn, Trường Trung học phổ thơng Ngân Sơn, đặc biệt tổ Tốn Tin giúp đỡ tinh thần vật chất suốt trình học tập Thái Nguyên, ngày 19 tháng năm 2010 Tác giả i Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mở đầu Trong số học số nguyên tố đóng vai trị quan trọng Từ xưa nhà tốn học nhiều thời gian để nghiên cứu số nguyên tố nay, nhiều điều bí ẩn số nguyên tố chưa biết Ngày nhờ vào tiến KHKT, nhờ vào máy tính điện tử, người ta tìm nhiều số nguyên tố lớn (có hàng chục triệu chữ số) Bên cạnh định lí số nguyên tố lôi ý nhà tốn học, người ta ln cố gắng tìm chứng minh Chứng minh tính vơ hạn số nguyên tố sử dụng lí thuyết khác số học, lí thuyết chuỗi, tô pô, nhiều công cụ khác Luận văn gồm hai chương Chương 1, chúng tơi trình bày chứng minh khác định lí Euclid Cũng chương này, chúng tơi trình bày số tốn tồn tiếng lí thuyết số ngun tố Chương 2, chúng tơi trình bày lịch sử tìm số số nguyên tố lớn ứng dụng, mà trọng tâm chương nghiên cứu lịch sử tìm số nguyên tố Mersenne từ trước số nguyên tố lớn tìm thường số nguyên tố Mersenne Nhận thức lí thuyết số nguyên tố tảng số học, học số nguyên tố từ sớm, từ bậc học phổ thông sở, tài liệu viết số nguyên tố Bản luận văn cung cấp thêm tài liệu lịch sử nghiên cứu lí thuyết số nguyên tố trình tìm số nguyên tố lớn Chúng hy vọng luận văn đáp ứng phần lịng u thích nghiên cứu số nguyên tố bạn đồng nghiệp, em học sinh Sau thời gian nghiên cứu luận văn hồn thành Tuy nhiên ii Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn khơng tránh khỏi nhiều sai sót Kính mong góp ý quý thầy cô, bạn đồng nghiệp Chúng xin chân thành cảm ơn! Thái Nguyên, ngày 19 tháng năm 2010 Tác giả iii Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục Lời cảm ơn i Mở đầu ii Mục lục Chương Định lí Euclid số nguyên tố 1.1 Định lí: Tập hợp số ngun tố vơ hạn 1.2 Những chứng minh khác định lí Euclid 1.2.1 Chứng minh (Euclid, kỉ III trước công nguyên) 1.2.2 Chứng minh (Kummer) 1.2.3 Chứng minh (Silvestre) 1.2.4 Chứng minh (Goldbach) 1.2.5 Chứng minh 1.2.6 Chứng minh 1.2.7 Chứng minh (Kholsinskii 1994) 10 1.2.8 Chứng minh 11 1.2.9 Chứng minh 12 1.2.10 Chứng minh 10 13 1.2.11 Chứng minh 11 14 1.2.12 Chứng minh 12 14 1.2.13 Chứng minh 13 16 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.2.14 Chứng minh 14 16 1.2.15 Chứng minh 15 17 1.2.16 Chứng minh 16 (Euler) 17 1.2.17 Chứng minh 17 18 1.2.18 Chứng minh 18 18 1.2.19 Chứng minh 19 (chứng minh sử dụng tô pô, Furstenberg,1955) 19 Chương Số nguyên tố lớn ứng dụng 20 2.1 Tại cần phải tìm số nguyên tố lớn? 20 2.1.1 Hệ mã mũ 21 2.1.2 Các hệ mật mã khóa công khai 23 2.2 Số nguyên tố Mersenne 26 2.2.1 Số hoàn hảo số nguyên tố Mersenne 26 2.2.2 Lịch sử tìm số nguyên tố Mersenne 30 2.2.3 Danh sách số nguyên tố Mersenne biết 31 2.3 Một số số nguyên tố lớn biết đến 32 2.3.1 Các số nguyên tố sinh đôi 32 2.3.2 Các số nguyên tố Sophie Germain 32 2.3.3 Các số giai thừa nguyên tố, nguyên tố giai thừa 33 2.4 Lịch sử nghiên cứu số nguyên tố 34 2.4.1 Các chủ đề lịch sử lí thuyết số nguyên tố 34 2.4.2 Một số vấn đề chưa giải 36 Kết luận 38 Tài liệu tham khảo 39 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương Định lí Euclid số nguyên tố Những định lí tồn ln ln lơi ý nhà tốn học, người ta ln ln cố gắng tìm chứng minh định lý toán học cổ điển Chẳng hạn người ta biết 350 chứng minh khác định lí Pytago Những chứng minh khơng thú vị mặt khoa học mà cịn có ý nghĩa mặt lịch sử Hơn nhiều chứng minh cho thấy mối liên quan lĩnh vực kiện khác toán học Ở chúng tơi trình bày 19 chứng minh khác định lí tiếng tốn học, định lí Euclid: 1.1 Định lí: Tập hợp số ngun tố vơ hạn 1.2 Những chứng minh khác định lí Euclid 1.2.1 Chứng minh (Euclid, kỉ III trước công nguyên) Giả sử tập hợp số nguyên tố hữu hạn Gọi p số nguyên tố lớn Xét k tích tất số nguyên tố cộng thêm 1: k = · · · · · ·p + Số k khơng có ước nguyên tố chia cho số nguyên tố tùy ý ta phần dư Trong dễ thấy ước số bé m > số tự nhiên k số nguyên tố, mâu thuẫn chứng minh định lí Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.2.2 Chứng minh (Kummer) Thực chất chứng minh Eculid chỗ, với giả thiết tính hữu hạn tập hợp số nguyên tố, người ta xây dựng số ngun k khơng chia hết cho số nguyên tố Nhà toán học Đức Kummer thay lập luận Euclid dấu định nghĩa k: k = · · · · · p − Trước đến chứng minh khác ta có bổ đề sau: Bổ đề 1.2.1 Nếu tồn dãy vô hạn số nguyên, nguyên tố cặp tập hợp số ngun tố vơ hạn Chứng minh Thật vậy, số nguyên tố cặp khơng có ước ngun tố chung Vì lấy ước nguyên tố số dãy ta nhận tập hợp vô hạn mà phần tử chúng số ngun tố Bây để chứng minh có vơ hạn số nguyên tố ta cần tìm dãy số nguyên tố cặp 1.2.3 Chứng minh (Silvestre) Xét dãy an xác định quan hệ sau: a1 = ak+1 = (ak )2 − ak + 1, k ∈ N Chẳng hạn số số hạng dãy sau: 2, 3, 7, 43 Ta chứng minh quy nạp với n ∈ N ta có đẳng thức sau: an+1 = a1 · a2 · · · ·an−1 · an + Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Với n = hiển nhiên Bây giả sử quan hệ với n tức an+1 = a1 · a2 · · · an−1 · an + Khi đó: an+2 = (an+1 )2 − an+1 + 1, a1 · a2 · · · ·an+1 + = a1 · a2 · · · an [(a1 · a2 · · · an−1 · an ) + 1] + =[(a1 · a2 · · · ·an )2 + a1 · a2 · an ] + =[(an+1 )2 − 2an+1 + + an+1 − + =(an+1 )2 − an+1 + Vậy (1) chứng minh Từ (1) suy phần tử với dãy Silvestre nguyên tố với tất phần tử đứng trước Như ta dãy vô hạn số nguyên tố cặp 1.2.4 Chứng minh (Goldbach) n Giả sử an = 22 + n Ta chứng minh hai số tùy ý dãy 3, 5, 17, , 22 + 1, nguyên tố cặp Giả sử ngược lại an ak n > k khơng ngun tố tức có ước chung d > Ta nhận thấy dãy xét gồm tồn số lẻ, d > Xét đồng thức sau đây: (1 + 2) · (1 + 22 ) · (1 + 22 ) (1 + 22 n−1 n ) = 22 − n Đồng thức chứng tỏ số an − = 22 − chia hết cho ak , chia hết cho d Nhưng = an − (an − 2) chia hết cho d (mâu thuẫn) Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn hai số nguyên tố lớn p q, cỡ chừng 100 chữ số thập phân Điều thực giây nhờ máy tính Khi số nguyên tố p q chọn, số mũ dùng để mã hóa e lấy cho (e, φ(qp)) = Nói chung nên chọn e số nguyên tố tùy ý lớn p q Số e chọn thiết phải thỏa mãn 2e > n = pq Nếu điều kiện khơng thỏa mãn, ta có C = P e < n, để tìm P , ta việc tính bậc e C Khi điều kiện 2e > n thỏa mãn, khối P khác mã hóa cách nâng lên lũy thừa lấy đồng dư theo modulo n Ta cần phải chứng tỏ rằng, việc biết khóa lập mã (cơng khai) (e, n) khơng dẫn đến việc tìm khóa giải mã (d, n) Chú ý rằng, để tìm nghịch đảo d e modulo φ(n), trước tiên phải tìm φ(n) Việc tìm φ(n) khơng dễ so với phân tích n, vì, biết φ(n) n, ta phân tích n = pq Thật vậy, ta có: p + q = n − φ(n) + 1, p−q = (p + q)2 − 4pq = (p + q)2 − 4n Từ cơng thức ta tìm p q Nếu ta chọn số p q khoảng 100 chữ số thập phân, n có khoảng 200 chữ số thập phân Để phân tích số nguyên cỡ lớn thế, với thuật toán nhanh với máy tính đại nhất, ta hàng tỷ năm! Có điều cần lưu ý chọn số p q để tránh rơi vào trường hợp tích pq bị phân tích nhanh nhờ thuật toán đặc biệt: p q cần chọn cho p − q − phải có thừa số nguyên tố lớn, ước chung lớn (p − 1, q − 1) phải nhỏ, q p phải có số chữ số khai triển thập phân khác không nhiều Thực tế triển khai chứng tỏ hệ mã RSA an tồn, có nhược điểm tốc độ mã hóa chậm (bằng phần ngàn hệ đối xứng có cấp độ bảo mật nay), thường 25 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn dùng để mã hóa tin ngắn, giao thức trao đổi chìa khóa hệ mã đối xứng Trên hệ mật mã công khai xuất Từ đến nay, có nhiều hệ mật mã khóa cơng khai đời Tuy vậy, nguyên tắc chung hệ mã sử dụng "thuật toán chiều", tức thuật tốn cho phép tìm đại lượng tương đối nhanh, việc tìm "nghịch đảo" (theo nghĩa đó) địi hỏi thời gian lớn Độc giả quan tâm đến vấn đề tìm đọc tài liệu chun lý thuyết mật mã Vì số nguyên tố lớn có nhiều ứng dụng quan trọng, nên thu hút nhiều quan tâm nhà toán học Nhưng số nguyên tố lớn tìm thường số nguyên tố Mersenne, phần biết câu trả lời 2.2 Số nguyên tố Mersenne 2.2.1 Số hoàn hảo số nguyên tố Mersenne Phần dành để mô tả dạng đặc biệt số ngun tố, có vai trị quan trọng lý thuyết ứng dụng Ta bắt đầu số hàm số học quan trọng Định nghĩa 2.2.1 Hàm τ (n), số ước, có giá trị n số ước dương n Hàm σ(n), tổng ước, có giá trị n tổng ước dương n Nói cách khác, ta có: τ (n) = 1, σ(n) = d\n d d\n Ví dụ Nếu p số ngun tố τ (p) = 2, σ(p) = p + Định lý 2.2.1 τ (n) σ(n) hàm nhân tính Dễ thấy rằng, định lý suy từ bổ đề sau 26 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Bổ đề 2.2.1 Nếu f hàm nhân tính, F (n) = f (d) d\n hàm nhân tính Thật vậy, giả sử m, n số dương nguyên tố Ta có F (mn) = f (d) d\mn Vì (m, n) = 1, ước d mn viết dạng d = d1 d2 d1 , d2 tương ứng ước m, n d1 , d2 nguyên tố Do ta có f (d1 d2 ) F (mn) = d1 \m,d2 \n Vì f hàm nhân tính (d1 , d2 ) = nên F (mn) = f (d1 )f (d2 ) = f (d1 ) d1 \m f (d2 ) = F (m)F (n) d2 \m Định lý chứng minh Sử dụng định lý trên, ta có cơng thức sau cho hàm τ (n) σ(n) Định lý 2.2.2 Giả sử n có phân tích sau thừa số ngun tố n = pa11 pa22 pakk Khi ta có k a pj j+1 − , σ(n) = p − j j=1 k τ (n) = (a1 + 1)(a2 + 1) (ak + 1) = (aj + 1) j=1 Do quan niệm thần bí, người Hy Lạp quan tâm đến số nguyên tổng tất ước dương thật Họ gọi số số hồn hảo 27 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định nghĩa 2.2.2 Số nguyên dương n gọi số hồn hảo τ (n) = 2n Ví dụ Các số 6, 28 số hoàn hảo: τ (6) = + + + + 12, τ (28) = + + + + 14 + 28 = 56 Định lý sau biết từ thời Hy Lạp Định lý 2.2.3 Số nguyên dương chẵn n số hoàn hảo n = 2m−1 (2m − 1), m số nguyên cho m ≥ 2m − số nguyên tố Chứng minh Trước tiên, giả sử rằng, m có dạng Vì σ hàm nhân tính, ta có σ(n) = σ(2m−1 )σ(2m − 1) Từ công thức hàm σ giả thiết 2m − nguyên tố, dễ thấy σ(2m−1 ) = 2m − 1, σ(2m − 1) = 2m , σ(n = 2n) Ngược lại, giả sử n số hoàn hảo chẵn Viết n = 2s t, s, t số nguyên dương, t lẻ, ta được: σ(n) = σ(2s t) = σ(2s )σ(t) = (2s+1 − 1)σ(t) Vì n số hồn hảo nên σ(n) = 2n = 2s+1 t Như vậy, 2s+1 | σ(t), giả sử σ(t) = 2s+1 q Ta có đẳng thức (2s+1 − 1)2s+1 q = 2s+1 t, tức q\t q = t Mặt khác ta có t + q = (2s+1 − 1)q + q = 2s+1 q = σ(t) Ta chứng tỏ rằng, q = Thật vậy, ngược lại, t có ước khác 1, t, q, mâu thuẫn đẳng thức vừa chứng minh Vậy σ(t) = t + 1, có nghĩa t số nguyên tố Định lý chứng minh Như để tìm số hồn hảo, ta cần tìm số ngun tố có dạng 2m − Định nghĩa 2.2.3 Giả sử m số nguyên dương, Mm = 2m − gọi số Mersenne thứ m Nếu p số nguyên tố, Mp nguyên tố, Mp gọi số nguyên tố Mersenne 28 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ví dụ M2 , M3 , M5 , M7 số nguyên tố Mersenne, M1 hợp số Có nhiều định lý khác dùng để xác định số nguyên tố Mersenne Chẳng hạn nhờ định lý sau đây, ta só thể kiểm tra nhanh chóng dựa vào dạng ước nguyên tố số Mersenne Định lý 2.2.4 Nếu p số nguyên tố lẻ, ước nguyên tố số Mersenne Mp có dạng 2kp + 1, k số nguyên dương Chứng minh Giả sử q ước nguyên tố Mq Theo định lý Fermat bé, q | (2q−1 ) Theo hệ (Nếu a b số nguyên dương, ước chug lớn 2a − 2b − 2( a, b) − 1), (2p − 1, 2q − 1) = 2(p,q−1) − Ước chung lớn 1, bội q Do đó, (p, q − 1) = p, p số nguyên tố Ta có q = mp + 1, q lẻ nên m = 2k, định lý chứng minh Sau vài ví dụ cho thấy ứng dụng định lý Ví dụ Để xét xem M13 = 213 − = 8191 có phải số ngun tố hay khơng, ta cần xem phép chia cho số nguyên tố không vượt √ 8191 ≈ 90 Mặt khác, theo định lý trên, ước nguyên tố phải có dạng 26k + Như cần thử với hai số 53 79: ta thấy M13 số nguyên tố Ví dụ Xét M23 = 8388607 Ta cần xét phép chia cho số nguyên tố dạng 46k + Số 47 ước nó: M23 hợp số Có nhiều thuật toán đặc biệt để kiểm tra nguyên tố số Mersenne Nhờ đó, người ta phát số nguyên tố lớn Mỗi lần có số nguyên tố Mersenne, ta lại số hoàn hảo Số nguyên tố Mersenne tìm gần số M43.112.609 , gồm 12.978.189 chữ số Giả thuyết sau chưa chứng minh GIẢ THUYẾT Tồn vô hạn số nguyên tố Mersenne Người ta biết rằng, khoảng từ đến 10200 khơng có số hoàn hảo lẻ Tuy nhiên câu hỏi sau chưa trả lời 29 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Câu hỏi.Tồn hay khơng số hồn hảo lẻ? 2.2.2 Lịch sử tìm số nguyên tố Mersenne Như biết, số nguyên tố Mersenne có quan hệ chặt chẽ với số hoàn hảo Trong lịch sử, việc nghiên cứu số số nguyên tố Mersenne bị thay đổi liên quan này: vào kỷ 4T CN , Euclid phát biểu rằng, M số nguyên tố Mersenne M · (M + 1)/2 số hoàn hảo Vào kỷ 18, Leonhard Euler chứng minh tất số hoàn hảo chẵn có dạng Khơng số hồn hảo lẻ biết người ta nghi ngờ chúng không tồn Bốn số nguyên tố Mersenne đàu tiên M2 = 3, M3 = 7, M5 = 31 M7 = 127 biết từ cổ xưa Số thứ năm M13 = 8191 tìm thấy vào trước năm 1461; hai số M17 M19 tìm thấy Cataldi vào năm 1588 Sau kỷ M31 kiểm tra Euler vào năm 1750 Số M127 , Lucas tìm thấy vào năm 1876 , sau M61 Pervushin tìm thấy vào năm 1883 Hai số M89 M207 tìm thấy vào kỷ 20, Powers vào năm 1911 1914 Từ kỷ 17 số mang tên nhà toán học Pháp Marin Mersenne, người chứng minh loạt số nguyên tố Mersenne với số mũ lên đến 257 Danh sách ông mắc số sai lầm, bao gồm M67 , M257 , bỏ quên M61 , M89 M107 Phương pháp tốt để kiểm tra tính nguyên tố số Mersenne dựa vào tính tốn dãy tuần hồn, phát biểu Lucas năm 1878 chứng minh Lehmer vào năm 1930 Hiện gọi kiểm tra Lucas-Lehmer với số nguyên tố Mersenne Đặc biệt, ta chứng minh (với n > 2) Mn = 2n − số nguyên tố Mn chia hết cho Sn − S0 = với k > 0, Sk = Sk−1 − Việc tìm số nguyên tố Mersenne thực cách mạng máy tính điện tử số Thành cơng tư tưởng thuộc số nguyên tố 30 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mersenne M52 , nhờ nỗ lực khéo léo vào lúc 10h 00.P.M ngày 30.1.1952 sử dụng máy tính tự động Western U.S National Bureau of Standards (SWAC) Institute for Numerical Analysis thuộc Đại học California LosAngeles, điều khiển trực tiếp Lehmer, sử dụng chương trình viết chạy GS RM Robinson Nó số ngun tố Mersenne tìm thấy sau 38 năm; số M607 tìm thấy máy tính sau gần hai chạy máy Ba số M1279 , M2203 , M2281 tìm thấy với chương trình sau nhiều tháng M4253 số nguyên tố Mersenne siêu lớn, 1000 chữ số thập phân (titanic), M44497 số nguyên tố có 10.000 chữ số thập phân (gigantic) Đến tháng năm 2008, biết 46 số nguyên tố Mersenne; số lớn biết số có dạng 243112609 − Cũng nhiều số nguyên tố Mersenne trước đó, tìm nhờ dự án máy tính phân tán Internet, biết với tên gọi: Tìm kiếm số nguyên tố Mersenne khổng lồ Internet(Great Internet Mersenne Prime Search GIMPS) 2.2.3 STT 10 Danh sách số nguyên tố Mersenne biết Số nguyên tố 26972593 − 213466917 − 220996011 − 224036583 − 225964951 − 230402457 − 232582657 − 237156667 − 242643801 − 243112609 − Chữ số 2098960 4053946 6320430 7235733 7816230 9152052 9808358 11185272 12837064 12978189 Ai G4 G5 G6 G7 G8 G9 G9 G12 G12 G10 Khi 1999 2001 2003 2004 2005 2005 2006 2008 2009 2008 Bình luận Mersenne 38 Mersenne 39 Mersenne 40? Mersenne 41? Mersenne 42? Mersenne 43?? Mersenne 44?? Mersenne 45?? Mersenne 46?? Mersenne 47?? 31 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2.3 Một số số nguyên tố lớn biết đến 2.3.1 Các số nguyên tố sinh đôi Số nguyên tố sinh đôi số nguyên tố có dạng p p + chúng khác đơn vị Ngày 28.9.2002 Daniel Papp phát số ngun tố sinh đơi có 51090 chữ số ( 33218925.2169690 ± 1,) Danh sách số số nguyên tố sinh đôi biết: STT 10 Số nguyên tố 16869987339975.2171960 − 16869987339975.2171960 + 100314512544015.2171960 − 100314512544015.2171960 + 194772106074315.21719601 −1 194772106074315.21719601 +1 2003663613.2195000 − 2003663613.2195000 + 65516468355.2333333 − 65516468355.2333333 + 2.3.2 Chữ số 51779 51779 51780 51780 51780 51780 58711 58711 100355 100355 Ai x24 x24 x24 x24 x24 x24 L202 L202 L923 L923 Khi 2005 2005 2006 2006 2007 2007 2007 2007 2009 2009 Bình luận Twin(p) Twin(p+2) Twin(p) Twin(p+2) Twin(p) Twin(p+2) Twin(p) Twin(p+2) Twin(p) Twin(p+2) Các số nguyên tố Sophie Germain Một số nguyên tố Sophie Germain nguyên tố lẻ p mà 2p + số nguyên tố Ngày 18.1.2003, David Underbakko phát nguyên tố Sophie Germain có 34547 chữ số (2540041185.2114729 − 1) Danh sách số nguyên tố Sophie Germain tìm thấy 32 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn STT Số nguyên tố 18912879.298395 − 112886032245.2108000 − 1124044292325.2107999 − 2540041185.2114729 − 7068555.2121301 − 33759183.2123458 − 137211941292195.2171960 − 48047305725.2171960 − 607095.2176311 − 620366307356565.2253824 − 1 10 2.3.3 Chữ số Ai 29628 32523 32523 34547 36523 37173 51780 51910 53081 76424 p94 L99 L99 g294 L100 L527 x24 L99 L983 x24 Khi 2002 2006 2006 2003 2005 2009 2006 2007 2009 2009 Bình luận SophieGermain(p) SophieGermain(p) SophieGermain(p) SophieGermain(p) SophieGermain(p) SophieGermain(p) SophieGermain(p) SophieGermain(p) SophieGermain(p) SophieGermain(p) Các số giai thừa nguyên tố, nguyên tố giai thừa Số có dạng n! ± gọi giai thừa nguyên tố Danh sách số giai thừa nguyên tố biết STT 10 Số nguyên tố 974! − 1477! + 1963! − 3507! − 3610! − 6380! + 6917! − 21480! − 26951! + 34790! − Chữ số 2490 4042 5614 10912 11277 21507 23560 83727 107707 142891 Ai CD D CD C C gl gl p65 p65 p85 Khi 1992 1984 1992 1992 1993 1998 1998 2001 2002 2002 Bình luận Factorial Factorial Factorial Factorial Factorial Factorial Factorial Factorial Factorial Factorial Số nguyên tố giai thừa số nguyên tố có dạng 2.3.5.p + Danh sách số nguyên tố giai thừa biết: 33 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn STT 10 2.4 Số nguyên tố 13033 − 13649 + 15877 − 18523 + 23801 + 24029 + 42209 + 15877 + 366439 + 392113 + Chữ số 5610 5862 6845 8002 10273 10387 18241 63142 158936 169966 Ai CD D CD D C C p8 p21 p16 p16 Khi 1992 1987 1992 1989 1993 1993 1999 2000 2001 2001 Bình luận Primorial Primorial Primorial Primorial Primorial Primorial Primorial Primorial Primorial Primorial Lịch sử nghiên cứu số nguyên tố 2.4.1 Các chủ đề lịch sử lí thuyết số nguyên tố Số nguyên tố tính chất lần nghiên cứu rộng rãi nhà toán học Hy Lạp cổ đại Các nhà toán học trường học Pythagoras (500T CN đến 300T CN ) quan tâm đến tính chất số nguyên tố Họ quan tâm đến số hoàn hảo Cho đến thời gian xuất "Nguyên lý" Euclid (khoảng 300T CN ), số kết quan trọng số nguyên tố chứng minh Trong sách Ngun lý IX chứng minh có vơ hạn số nguyên tố Đây chứng biết từ sớm sử dụng phương pháp phản chứng Euclid cung cấp chứng minh định lí số học: tất số ngun viết tích số nguyên tố Euclid cho thấy 2n − số nguyên tố 2n−1 (2n − 1) số hoàn hảo Euler ( năm 1747) tất số hồn hảo có dạng Trong khoảng 200T CN , Eratosthenes (Hy Lạp) nghĩ thuật tốn để tính số ngun tố, gọi sàng Eratosthenes 34 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Sau có thời gian dài lịch sử khơng có tiến triển thêm số ngun tố Những phát minh quan trọng thực Fermat vào đầu kỷ 17 Ông chứng minh suy đoán Albert Giard số nguyên tố có dạng 4n − viết theo cách dạng tổng bình phương Ơng nghĩ phương pháp để tìm thừa số số lớn, khai triển số 2027651281 = 44021 · 44061 Ông chứng minh điều mà ngày biết đến định lí Fermat bé (để phân biệt với định lí cuối ơng) Định lí Fermat bé sở cho nhiều kết khác lí thuyết số sở cho phương pháp kiểm tra cho dù số mà cịn sử dụng máy tính điện tử ngày Fermat thường trao đổi với nhà toán học đương thời khác, đặc biệt Marin Mersenne Trong thư gửi Mersenne, ông đoán số 2n + nguyên tố n lũy thừa Ông xác minh điều với n = 1, 2, 4, 16, ông biết n không chia hết cho 2, kết không Số dạng nói gọi số Fermat không nhắc đến 100 năm sau đó, Euler trường hợp 232 + = 4294967297 chia hết cho 641, khơng phải số ngun tố: Các số có dạng 2n −1 thu hút ý dễ thấy n không số nguyên tố, số phải hợp số Những số gọi số Mersenne Mn Mersenne nghiên cứu chúng Euler người có ảnh hưởng lớn đến lí thuyết số nói chung số nguyên tố nói riêng Ơng mở rộng định lí Fermat bé đưa phi hàm Euler Φ(n) Như đề cập ơng phân tích số Fermat thứ năm 232 + 1, ơng phát 35 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn biểu (nhưng chứng minh) điều mà ngày gọi luật thuận nghịch bình phương Ơng người nhận lí thuyết số nghiên cứu cách sử dụng công cụ giải tích, xây dựng nên lí thuyết số giải tích Thoạt nhìn, số nguyên tố dường phân phối số nguyên cách lộn xộn Ví dụ số 100 số đứng liền trước 10000000 có chín số ngun tố, 100 số sau có hai số nguyên tố Legendre Gauss tính tốn đến mật độ số ngun tố Gauss nói với người bạn rằng, ơng có 15 phút rảnh rỗi ơng dành tính số ngun tố Đến cuối đời, ơng ước tính ơng tính tất số nguyên tố lên đến khoảng 3000000 Cả Legendre Gauss kết luận rằng, n đủ lớn, mật độ số nguyên tố nhỏ n 1/log(n) Legendre cho ước tính cho (n) số nguyên tố ≤ n (n) = n/(log(n) − 1, 08366) Mệnh đề nói mật độ số nguyên tố 1/log(n) gọi định lí số nguyên tố Người ta cố gắng để chứng minh điều suốt kỉ 19, đạt tiến đáng ý Chebyshev Riemann Kết cuối chứng minh (sử dụng phương pháp mạnh mẽ giải tích phức) Hadamard Dela Vallee Poussin vào năm 1896 Vẫn nhiều câu hỏi mở (một số số có niên đại hàng trăm năm) liên quan đến số nguyên tố 2.4.2 Một số vấn đề chưa giải Có vơ hạn số ngun tố sinh đơi? Phỏng đốn Goldbach (phát biểu thư Goldbach gửi Euler vào năm 1742) số nguyên lớn viết tổng hai số nguyên tố? Có vơ hạn số ngun tố dạng n2 + ? 36 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Luôn có số nguyên tố n2 (n + 1)2 ? Có vơ hạn số ngun tố Fermat? Có nhiều vơ hạn ba số ngun tố liên tiếp cấp số cộng? n2 − n + 41 số nguyên tố với ≤ n ≤ 40 Có vơ hạn số ngun tố có dạng này? Có vơ hạn số ngun tố có dạng n + ? (ở n tích tất số nguyên tố ≤ n) 10 Có vơ hạn số ngun tố có dạng n − 1? 11 Có vơ hạn số ngun tố có dạng n! + 1? 12 Có vơ hạn số ngun tố có dạng n! − 1? 13 Nếu p số ngun tố 2p −1 ln ln khơng có ước phương khác (squarefree?) 14 Các dãy Fibonacci chứa số lượng vô hạn số nguyên tố? 37 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Kết luận Luận văn nhằm trình bày số điều thú vị số nguyên tố: 1/ 19 chứng minh khác Định lý Euclid vô hạn tập hợp số nguyên tố Những chứng minh sử dụng nhiều công cụ khác nhau, kể tô pô để xét tập hợp số nguyên tố 2/ Một số ứng dụng số nguyên tố việc xây dựng hệ mật mã đại 3/ Sơ lược lịch sử nghiên cứu số nguyên tố, đặc biệt lịch sử tìm số nguyên tố lớn 38 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Tài liệu tham khảo [1] Hà Huy Khoái - Phạm Huy Điển - Số học thuật toán - Nxb Khoa học , Hà Nội, năm 1996 [2] Nguyễn Văn Mậu - Một số vấn đề toán học chọn lọc, NXB Giáo dục, tháng 10, 2008 [3] Nguyễn Thành Quang - Luận án tiến sĩ toán học - Trường Đại học sư phạm vinh 1998 [4] Andrew Granville anh Thomas J Tucker, It’s As Easy As abc, Vol 49 Number 10, Notices of the AMS, November 2002 [5] Alin Bostan and Philippe Dumas, Bodu09 Wronskians and Linear indenpendence, Algorithms Project, Inria Rocquencourt, France [6] Frits Beukers, The genneralized Fermat equation, January 20, 2006 [7] Henri Cohen, Number Theory, Vol 2, Analytic and mondern tool, Springer, 2007 [8] Mason, Equations over function fields, Oxford Unierssity Press, 1990 39 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ... bày số tốn tồn tiếng lí thuyết số nguyên tố Chương 2, chúng tơi trình bày lịch sử tìm số số nguyên tố lớn ứng dụng, mà trọng tâm chương nghiên cứu lịch sử tìm số nguyên tố Mersenne từ trước số nguyên. .. trước số nguyên tố lớn tìm thường số nguyên tố Mersenne Nhận thức lí thuyết số nguyên tố tảng số học, học số nguyên tố từ sớm, từ bậc học phổ thơng sở, tài liệu viết số nguyên tố Bản luận văn... 2.3 Một số số nguyên tố lớn biết đến 32 2.3.1 Các số nguyên tố sinh đôi 32 2.3.2 Các số nguyên tố Sophie Germain 32 2.3.3 Các số giai thừa nguyên tố, nguyên