Phân tích các số dạng 10n + 1 ra thừa số nguyên tố

Chia sẻ: Huyết Thiên Thần | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

18
lượt xem 3
download

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

Bài báo "Phân tích các số dạng 10n + 1 ra thừa số nguyên tố" trình bày cách sử dụng Geogebra như một công cụ thí nghiệm trong phân tích số 10n + 1 ra thừa số nguyên tố, và trả lời về cơ bản câu hỏi nêu trên. Mời các bạn cùng tham khảo chi tiết mội dung bài viết!

Chủ đề:

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

Lưu

Nội dung Text: Phân tích các số dạng 10n + 1 ra thừa số nguyên tố

Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 PHÂN TÍCH CÁC SỐ DẠNG 10n + 1 RA THỪA SỐ NGUYÊN TỐ Nguyễn Thị Hồng Hạnh∗, Đỗ An Khánh†, Bùi Thị Hằng Mơ‡, Tạ Duy Phượng§ Tóm tắt nội dung Sử dụng Geogebra, bài viết trả lời về cơ bản câu hỏi của Giáo sư Lại Đức Thịnh nêu trong [4] về phân tích số dạng 10n + 1 ra thừa số nguyên tố. 1. Dẫn nhập Trong tạp chí Toán học và Tuổi trẻ số 29 (tháng 2-1967, trang 15, [4]), Giáo sư Lại Đức Thịnh đã viết như sau: “Bài toán: Các số nguyên tố có dạng 1000 . . . 0001 gồm bao nhiêu chữ số 0 là một bài toán chưa giải được". Theo tìm hiểu của chúng tôi, hơn 50 năm qua chưa có phản hồi nào về bài toán này, có lẽ cũng vì không ai đủ sức (bằng tay) để phân tích các số dạng 100..001 với n số 0 ra thừa số nguyên tố. Bài báo này trình bày cách sử dụng Geogebra như một công cụ thí nghiệm trong phân tích số 10n + 1 ra thừa số nguyên tố, và trả lời về cơ bản câu hỏi nêu trên. 2. Giới thiệu về Geogebra Geogebra là một phần mềm toán học có thể làm mọi tính toán toán học và vẽ hình trong chương trình toán phổ thông và đại học. Hơn nữa, Geogebra được cài đặt phần mềm chuyển đổi tiếng Anh sang tiếng Việt, do đó Geogebra là một công cụ tiện dùng và hữu ích trong dạy và học, đặc biệt trong dạy và học theo chương trình và sách giáo khoa mới. Bạn đọc có thể tìm hiểu cài đặt và sử dụng Geogebra theo [1] và tìm hiểu một số ứng dụng của Geogebra trong [2], [3]. ∗ THPT Quang Trung, Đống Đa, Hà Nội † THPT Trần Đại Nghĩa, Thanh Oai, Hà Nội ‡ Học viên Cao học, ĐH Khoa học, ĐH Thái Nguyên § Cộng tác viên Viện Toán học 1
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 3. Sử dụng Geogebra trong phân tích số nguyên tố ra thừa số Một số chỉ chia hết cho 1 và chính nó được gọi là số nguyên tố. Với những số lớn, thuật toán Euclid và các thuật toán hiện đại phân tích một số ra thừa số nguyên tố ở thời điểm hiện tại chưa thể cho kết quả trong thời gian thực. Vì vậy, việc phân tích một số ra thừa số nguyên tố vẫn còn là bài toán rất khó, ngay cả với những hệ thống máy tính song song cỡ lớn và các phần mềm chuyên dụng. Mặt khác, với phần mềm thương mại Maple hoặc phần mềm free (miễn phí trên mạng) Geogebra, có thể phân tích được số tự nhiên với dưới 35 chữ số tương đối nhanh (chỉ trong vài giây). Điều này giúp các thày cô giáo có thể hướng dẫn học sinh Trung học Phổ thông, thậm chí học sinh Trung học Cơ sở, tập dượt nghiên cứu với đề tài Phân tích một số ra thừa số nguyên tố. Sau khi cài đặt, để phân tích một số ra thừa số nguyên tố nhờ Geogebra, ta mở Geogebra, chọnCAS (Computer Algebra System-hệ tính toán đại số). Sau đó chỉ cần khai báo duy nhất một lệnh ifactor () với số cần phân tích được khai báo trong ngoặc, thí dụ, số dạng 10n + 1, máy sẽ lập tức cho ra ngay kết quả như trong Bảng 1. Bảng 1 Phân tích các số dạng 100 . . . 001 với n = 2, . . . , 50 chữ số 0 ra thừa số nguyên tố. 2
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 3
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Quan sát Bảng 1, ta rút ra quy luật sau: Khẳng định 1 Các số dạng Nn := 100 . . . 001 với n = 2k chữ số 0 chia hết cho 11. Nhận xét 0.1. Với k = 0 thì 11 là số nguyên tố. Chứng minh 1 Làm phép nhân trực tiếp ta được 1 00 . . 00} 1 = 9090 . . . 9091 × 11 | .{z 2k với k − 1 cặp số 90. Chứng minh 2 Ta có 1 00 . . 00} 1 = 102k+1 + 1 | .{z 2k = (10 + 1) 102k − 102k−1 + 102k−2 − . . . . + 1 = 11. 102k − 102k−1 + 102k−2 − . . . . + 1 . 4
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Như vậy, câu hỏi của Giáo sư Lại Đức Thịnh đã được trả lời một nửa. Có thể thấy rõ hơn trong Phụ lục 1 dưới đây. Phụ lục 1 1001 = 103 +1 = 11 × 91; 100001 = 105 +1 = 11 × 9091; 10000001 = 107 +1 = 11 × 909091; 100000000 = 109 +1 = 11 × 90909091; 100000000001 = 1011 +1 = 11 × 9090909091; 10000000000001 = 1013 +1 = 11 × 909090909091; 1015 +1 = 11 × 90909090909091; 1017 +1 = 11 × 9090909090909091; 1019 +1 = 11 × 909090909090909091; 1021 +1 = 11 × 90909090909090909091; 1023 +1 = 11 × 9090909090909090909091; 1025 +1 = 11 × 909090909090909090909091; 1027 +1 = 11 × 90909090909090909090909091; 1029 +1 = 11 × 9090909090909090909090909091; 1031 +1 = 11 × 909090909090909090909090909091; 1033 +1 = 11 × 90909090909090909090909090909091; 1035 +1 = 11 × 9090909090909090909090909090909091; 1039 +1 = 11 × ×90909090909090909090909090909090909091;; 1045 + 1 = 11 × ×90909090909090909090909090909090909090909091; 1049 +1 = 11 × ×909090909090909090909090909090909090909090909091. Áp dụng Mặc dù với n đủ lớn, thí dụ, với n = 36, 40, 42, 46, 50, Geogebra không thể phân tích được các số đó ra thừa số (Geogebra cho dấu ?, xem Bảng 1). Nhưng ta vẫn khẳng định được nó chia hết cho 11. Ta có thể kiểm tra điều này nhờ Geogebra bằng phép chia (sử dụng lệnh chia: /) như sau. Vậy chỉ còn chưa biết các số dạng N2k+1 có là số nguyên tố hay không. Quan sát Bảng 1 ta đi đến Khẳng định 2 Các số dạng Nn := 100 . . . 001 với n = 4k + 1 chữ số 0 chia hết cho 101. Nhận xét 2 Với k = 0 thì 101 là số nguyên tố. Chứng minh 1 Phép nhân trực tiếp cho 5
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 1 00 . . 00} 1 = 99009900 . . . 99009901 × 101 | .{z 4k +1 với k − 1 bộ bốn 9900 và một bộ 9901 ở cuối. Chứng minh 2 Ta có 1 00 . . 00} 1 = 104k+2 + 1 | .{z 4k +1 = (102 + 1) 104k − 104k−2 + 104k−4 + · · · − 102 + 1 = 101 × 99009900 . . . 99009901. Các số lẻ n = 2k + 1 chỉ có thể là n = 4k1 + 1 hoặc n = 4k2 + 3. Ta đã thấy rằng, nếu n = 4k1 + 1 thì Nn chia hết cho 101. Vậy câu hỏi của Giáo sư Lại Đức Thịnh đã được trả lời thêm một phần tư (tổng cộng đã bằng 1/2 + 1/4 = 3/4). Chỉ còn các số dạng n = 4k + 3. Có thể thấy rõ hơn trong Phụ lục 2 dưới đây. Phụ lục 2 106 +1 = 101 × 9901; 1010 +1 = 101 × 99009901; 1014 +1 = 101 × 990099009901; 1018 +1 = 101 × 9900990099009901; 1022 +1 = 101 × 99009900990099009901; 1026 + 1 = 101 × 990099009900990099009901; 1030 + 1 = 101 × 9900990099009900990099009901; 1034 + 1 = 101 × 99009900990099009900990099009901; 1042 + 1 = 101 × 9900990099009900990099009900990099009901; 1050 + 1 = 101 × 990099009900990099009900990099009900990099009901. Áp dụng Mặc dù Geogebra không phân tích được N37 , N45 ra thừa số (xem Bảng 1), nhưng n = 37 = 4 × 9 + 1 và n = 45 = 4 × 11 + 1 nên ta khẳng định N37 , N45 chia hết cho 101. Ta có Quan sát tiếp Bảng 1, ta thấy nếu n = 8k + 3 thì Nn chia hết cho 10001 = 73 × 137. Ta có Khẳng định 3 Các số dạng Nn := 100 . . . 001 với n = 8k + 3 chữ số 0 chia hết cho 10001. Nhận xét 3 Với k = 0 thì 10001 = 73 × 137 là hợp số. Chứng minh 1 Phép nhân trực tiếp cho 6
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 1 00 . . 00} 1 = 9999000099990000 . . . 9999000099990001 × 10001. | .{z 8k +3 Chứng minh 2 Ta có 1 00 . . 00} 1 = 108k+4 + 1 = | .{z 8k+3 = 104 + 1 108k − 108k−4 + 108k−8 − · · · − 104 + 1 = 10001 × 9999000099990000 . . . 9999000099990001. Các số lẻ n = 4k + 3 chỉ có thể là n = 8k1 + 3, (khi n = 2k1 ) hoặc n = 8k1 + 7 (khi n = 2k1 + 1) Vậy chỉ còn trường hợp n = 8k1 + 7 là chưa có câu trả lời, hay câu hỏi của Giáo sư Lại Đức Thịnh đã được trả lời thêm một phần tám (tổng cộng bằng 1/2 + 1/4 + 1/8 = 7/8). Có thể thấy rõ hơn trong Phụ lục 3 dưới đây. Phụ lục 3 1012 + 1 = 10001 × 99990001; 1020 + 1 = 10001 × 9999000099990001; 1028 + 1 = 10001 × 999900009999000099990001; 1036 + 1 = 10001 × ×99990000999900009999000099990001; 1044 + 1 = 10001 × ×9999000099990000999900009999000099990001. Quan sát tiếp Bảng 1, ta thấy nếu n = 16k + 7 thì Nn chia hết cho 100000001 = 17 × 5882353. Ta có Khẳng định 4 Các số dạng Nn := 100 . . . 001 với n = 16k + 7 chữ số 0 chia hết cho 100000001. Nhận xét 4 Với k = 0 thì 100000001 = 17 × 5882353 là hợp số. Chứng minh 1 Phép nhân trực tiếp cho 1 00 . . 00} 1 = 100000001 × 9999999900000000 . . . 9999999900000001 | .{z 16k +7 với k − 1 bộ 16 số 9999999900000000 và một bộ số 9999999900000001. Chứng minh 2 Ta có 1 00 . . 00} 1 = 1016k+8 + 1 = | .{z 16k +7 = 108 + 1 1016k − 1016k−8 + · · · − 108 + 1 = 100000001 × 9999999900000000 . . . 9999999900000001 Có thể thấy rõ hơn trong Phụ lục 4 dưới đây. Phụ lục 4 1024 + 1 = 100000001 × 9999999900000001; 1040 + 1 = 100000001 × 99999999000000009999999900000001. Vì n = 8k + 7 chỉ có thể là n = 16k + 7 (khi k = 2k1 ) hoặc n = 16k1 + 15 (khi k = 2k1 + 1 ) nên chỉ còn các số với n = 16k1 + 15 là chưa biết có phải là số nguyên tố hay không. Tổng quát hóa từ bốn khẳng định trên, ta đi đến 7
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Định lí 1 Các số Nn , n = 2 p k + 2 p−1 − 1 chia hết cho 10n + 1 với 2 p−1 − 1 số 0, với p = 1, 2, . . . Chứng minh 1 Nhân trực tiếp ta được 1 00 | .{z . . 0} 1 × 9| .{z . . 00} 1 = 1 0| .{z . . 9} 0| .{z . . 0} . . . 9| .{z . . 9} 0| .{z . . 0} 9| .{z . . 9} 0| .{z . . 0} 1. 2 p k + 2 p −1 − 1 2 p −1 − 1 p −1 2 p −1 2 p −1 2 p −1 2 p −1 2 p −1 − 1 |2 {z } k −1 Chứng minh 2 Ta có p p −1 1 00 . . 00} 1 = 102 k+2 + 1 | .{z 2 p k + 2 p −1 − 1 p p −1 p p −1 p p −1 p p −1 = (102 + 1) × 102 k − 102 k−2 + 102 k−2.2 − 102 k−2 ···+1 = 1 00 . . . 0} 1 × 9| .{z | {z . . 9} 0| .{z . . 0} . . . 9| .{z . . 0} 9| .{z . . 9} 0| .{z . . 9} 0| .{z . . 0} 1. 2 p −1 p −1 2 p −1 2 p −1 2 p −1 2 p −1 2 p −1 − 1 |2 {z } k −1 Từ Định lí 1, cho p = 1, 2, 3, 4 ta có các Khẳng định 1, 2, 3, 4. Như vậy, ta đã khẳng định được rằng, hầu hết các số dạng 100 . . . 001 là hợp số. Cứ mỗi lần cho p thay đổi,p = 1, 2, . . . , ta lại chứng minh được một nửa số còn lại là hợp số và chỉ còn một nửa số còn lại là chưa kiểm tra được. Nhưng 1 1 1 1 1 1 2 + 4 + 8 + · · · = 2 1 + 2 + 4 + . . . = 1. Điều này cho ta dự đoán, ta đã vét cạn tất cả các số tự nhiên. Để khẳng định điều này, ta phải chứng minh Mệnh đề sau. Mệnh đề 0.1. Mọi số tự nhiên lẻ n đều có dạng n = 2 p k + 2 p−1 − 1. (1) Chứng minh. Giả sử n chạy trên khoảng 2 , 2 q q + 1 , tức là 2 ≤ n = 2k − 1 < 2q+1 , với q q = 0, 1, 2, . . . Biểu diễn n = 2k − 1 số trong hệ đếm cơ số 2 ta được n = 2q + a1 2q−1 + . . . . + a p 2 p + a p−1 2 p−1 − 1, trong đó ai = 0 hoặc ai = 1 và a p−1 = 1 là hệ số cuối cùng khác 0 trong biểu diễn cơ số 2 của n. Ta có n = 2q + a 1 2q −1 + . . . . + a p 2 p + 2 p −1 − 1 = 2 p −1 (2q − p +1 + a 1 2q − p + · · · + a p 2 p − q +1 ) + 2 p −1 − 1 = 2 p−1 k + 2 p−1 − 1. Cho q lần lượt chạy trên tập các số tự nhiên, q = 0, 1, 2, . . . thì n chạy trên toàn bộ tập các số tự nhiên và có biểu diễn dưới dạng (1). Mệnh đề 1 được chứng minh. Nhận xét rằng nếu n = 2k thì n có dạng trên với p = 1. Như vậy, chỉ còn câu hỏi: Các số dạng 10n + 1 với 2m − 1 số 0 có là số nguyên tố không? Bằng con đường ngắn gọn hơn, Đỗ An Khánh cũng đã chứng minh khẳng định này như sau. Mệnh đề 0.2. Nếu n 6= 2m − 1 thì mọi số dạng 10n + 1 với n − 1 số 0 là hợp số. . . 0} 1 = 10n + 1. Chứng minh. Ta có 1 0| .{z n −1 8
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Khả năng 1 Nếu n là lẻ (n = 2k + 1, k 6= 0 ) thì 0..0 1 = 102k+1 + 1 = (10 + 1) 102k − 102k−1 + 102k−2 . . . . − 10 + 1 1 |{z} 2k nên 1 0| .{z . . 0} 1 chia hết cho 11, do đó là hợp số. 2k Khả năng 2 Nếu n là chẵn ( n = 2k, k 6= 0) thì n = 2m q = pq, trong đó q là một số lẻ. Khi ấy ta có . . 0} 1 = 10n + 1 = 10 pq + 1 = (10 p )q + 1 = (10 p + 1) (10 p )q−1 − (10 p )q−2 + (10 p )q−3 − · · · + 1 . 1 0| .{z n −1 . . 0} 1 = 102k + 1 chia hết cho 10 p + 1 Vậy nếu n = 2k = 2m q = pq với q 6= 1 là số lẻ thì 1 0| .{z 2k −1 . . 0} 1 = 102k + 1 là hợp số. và do đó 1 0| .{z 2k −1 . . 0} 1 (khi n = 2m , hay q = 1) có là hợp số hay không. Ta có Vậy chỉ còn chưa biết 1 0| .{z 2m −1 . . 0} 1 nếu có ước khác nó thì các ước đó chỉ có thể có dạng 2m+1 k + 1. Mệnh đề 0.3. Số 1 0| .{z 2m −1 Chứng minh. Xem [7]. Thí dụ Với m = 2 : 2 10001 = 73 × 137 hay 102 + 1 = 23 .9 + 1 × 23 .17 + 1 ; Với m = 3 : 100000001 = 17 × 5882353 hay 3 102 +1 = 24 + 1 × 24 .36747 + 1 ; Với m = 4 : 10000000000000001 = 353 × 449 × 641 × 1409 × 69857 hay 4 102 +1 = 25 .11 + 1 × 25 .14 + 1 × 25 .20 + 1 × 25 .44 + 1 × 25 .2183 + 1 ; Với m = 5 : 100000000000000000000000000000001 = 19841 × 976193 × 6187457 × 834427406578561 hay 5 102 + 1 = 26 .310 + 1 × 26 .15253 + 1 × 26 .96679 + 1 × 26 .13037928227790 + 1 . m 0..0 1 = 102 + 1 là hợp số. Tuy nhiên, ta vẫn chưa thể khẳng định tất cả các số dạng 1 |{z} 2m − 1 m Geogebra không thể phân tích tiếp được các số dạng 1 |{z} 0..0 1 = 102 + 1 ra thừa số nguyên 2m −1 tố, nhưng nó có thể khẳng định các số này là hợp số với m = 6, 7, . . . , 12. Sử dụng lệnh Isprime (có phải là số nguyên tố không, Geogebra sẽ trả lời: false (sai, nghĩa là số cần kiểm tra là hợp số): 9
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Tuy nhiên, với m = 13, Geogebra trả lời: Tính toán quá lâu nên bỏ, nghĩa là Geogebra không tính toán và trả lời được đây là số nguyên tố hay không. Vĩ thanh 1 Bài toán phân tích số dạng 100 . . . 001 ra thừa số nguyên tố liên quan đến bài toán sau đây: Tìm số nguyên tố p có tổng các chữ số của nó là một số nguyên tố q mà tổng các chữ số của q là 2. Lời giải. Vì q là số nguyên tố q mà tổng các chữ số của q là 2 nên q = 2, tức là p chỉ có thể có dạng 100 . . . 001. Thí dụ: 11, 101. Dẫn đến bài toán: Có bao nhiêu số nguyên tố dạng 10n + 1? - hiện nay có lẽ chưa có câu trả lời (xem [4]). Vĩ thanh 2 Để tìm câu trả lời cho câu hỏi của Giáo sư Lại Đức Thịnh, thực ra chỉ cần chứng minh Mệnh đề 2. Tuy nhiên, chúng tôi muốn trình bày con đường đi đến lời giải của chúng tôi, cũng khá vất vả và công phu, và phải dùng đến công cụ thí nghiệm là Geogebra. Một câu hỏi tuy nhỏ, phát biểu đơn giản, nhưng tồn tại 50 năm (và bây giờ cũng vẫn chưa giải quyết trọn vẹn). Tất nhiên, không loại trừ khả năng đã có chứng minh hoặc phản ví m 0..0 1 = 102 + 1 là số nguyên tố. dụ (mà chúng tôi chưa biết) là có số dạng 1 |{z} 2m −1 Cuối cùng, chúng tôi nêu một ví dụ chứng tỏ khả năng giải quyết vấn đề của Geogebra trong Phân tích số tự nhiên ra thừa số nguyên tố. Ví dụ Phân tích số 3 × 5 × 7 × 11 × 13 × 17 × 19 − 2; 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 − 2 và 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 × 29 − 2 ra thừa số nguyên tố. Sử dụng Geogebra với lệnh ifactor () ta được 10
Hội thảo Khoa học, Sầm Sơn 28-28/09/2019 Ví dụ này liên quan đến giả thuyết: Các số dạng An = p1 p2 . . . pn − 2 (hiệu của tích các số nguyên tố liên tiếp và 2), trong đó là số nguyên tố lẻ thứ k là số nguyên tố với mọi n. Trong [5], được in lại trong [6], Giáo sư Lại Đức Thịnh viết: Bằng cách thử, ta thấy rằng các số A3 , A4 , A5 , A6 , A7 đều là số nguyên tố. Có lẽ thử với một vài giá trị nữa của n ta sẽ tìm được một hợp số. Tuy nhiên muốn kiểm tra A8 cần làm 300 phép chia và kiểm tra A9 cần 1300 phép chia, tức là mất vài buổi làm tính. Dùng Geogebra, như trên ta thấy A8 , A9 là số nguyên tố, nhưng A10 là hợp số. Hơn nữa, với Geogebra, chỉ mất vài phút để kiểm tra: trong 21 số đầu thì A3 , A4 , A5 , A6 , A7 , A8 , A9 , A11 , A13 , A16 , A20 là các số nguyên tố, các còn lại là hợp số. Tài liệu [1] Bùi Việt Hà, Hướng dẫn sử dụng nhanh Geogebra, School@net. [2] Nguyễn Thị Hồng Hạnh, Đỗ An Khánh, Bùi Thị Hằng Mơ, Tạ Duy Phượng, Geogebra-Một công cụ thí nghiệm trong phân tích đa thức ra thừa số, Kỷ yếu Hội thảo Seminar toán Olympic (Nguyễn Văn Mậu chủ biên), Trường Trung học Cơ sở Cầu Giấy, 02/05/2019. Xem thêm: Big School: https://stream.bigschool.vn/static/Bigschoolvn/document/2019/05/8Geogebra24- 4-2019.pdf. [3] Nguyễn Thị Hồng Hạnh, Bùi Thị Hằng Mơ, Tạ Duy Phượng, Sử dụng phần mềm Geogebra trong tìm hiểu môt số giả thuyết về số nguyên tố, Kỷ yếu Hội thảo Các chuyên đề toán học cập nhật chương trình và sách giáo khoa mới (Nguyễn Văn Mậu, Trần Quốc Tuấn chủ biên), Lạng Sơn 02-03/03/2019. [4] Lại Đức Thịnh, Giải đáp thắc mắc, Tạp chí Toán học và Tuổi trẻ, Số 29 (tháng 2-1967). [5] Lại Đức Thịnh, Nói chuyện về số nguyên tố, Tạp chí Toán học và Tuổi trẻ, số 7-1966. [6] Tuyển tập 30 năm tạp chí Toán học và Tuổi trẻ, Nhà xuất bản Giáo dục, 1997, trang 343. [7] Tạp chí Toán học và Tuổi trẻ, số 120, tháng 4-1981, bài 2/116). 11