Xem mẫu
- 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
nguon tai.lieu . vn
