ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NINH VĂN QUÝ
LỊCH SỬ PHÁT TRIỂN 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 - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Công trình được hoàn thành tại
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 sẽ được 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 2011
Có thể tìm hiểu tại
THƯ VIỆN ĐẠI HỌC THÁI NGUYÊN
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn tận tình và nghiêm
khắc của GS.TSKH. Hà Huy Khoái . Tôi xin bày tỏ lòng kính trọng và
biết ơn sâu sắc tới Thầy và 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 và nghiên cứu khoa học đã quan tâm giúp đỡ, tạo mọi
điều kiện thuận lợi cho tôi được học tập tốt.
Tôi xin chân thành cảm ơn Sở Giáo dục và Đào tạo Tỉnh Bắc Giang,
sẽ không tránh khỏi nhiều sai sót. Kính mong sự góp ý của quý thầy cô,
4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
các bạn đồng nghiệp. Chúng tôi xin chân thành cảm ơn!
Thái Nguyên, ngày 20 tháng 5 năm 2011
Tác giả
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Mục lục
Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Chương 1. Các giai đoạn phát triển của lý thuyết số nguyên
tố 8
1.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2. Giai đoạn 1:(Trước công nguyên) . . . . . . . . . . . . . 8
1.2.1. Định lý 1 (Euclid, thế kỉ III trước công nguyên) . 8
1.2.2. Sàng Eratosthenes . . . . . . . . . . . . . . . . . 9
1.3. Giai đoạn 2(Trước thế kỷ 17) . . . . . . . . . . . . . . . 10
1.4. Giai đoạn 3:(Sau thế kỷ 17) . . . . . . . . . . . . . . . . 10
1.4.1. Định lý 2(Fermat bé) . . . . . . . . . . . . . . . . 11
1.4.2. Định lý 3(Wilson) . . . . . . . . . . . . . . . . . . 11
1.4.3. Định lý 4(Định lý cơ bản của số học) . . . . . . . 13
1.4.4. Định lý 5 . . . . . . . . . . . . . . . . . . . . . . 14
1.4.5. Sự phân bố các số nguyên tố: . . . . . . . . . . . 14
1.4.6. Số nguyên tố Mersenne . . . . . . . . . . . . . . . 17
1.4.7. Số nguyên tố Fermat . . . . . . . . . . . . . . . . 20
1.4.8. Một số số nguyên tố lớn được biết đến . . . . . . 21
1.4.9. Một số vấn đề chưa được giải quyết . . . . . . . . 23
1.4.10. Số giả nguyên tố . . . . . . . . . . . . . . . . . . 24
1.2.1. Định lý 1 (Euclid, thế kỉ III trước công nguyên)
Tập hợp các số nguyên tố là vô hạn.
Chứng minh:(Định lý 1)
Giả tập hợp các số nguyên tố là hữu hạn. Gọi p là số nguyên tố lớn
nhất.
8
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Xét k là tích của tất cả các số nguyên tố cộng thêm 1:
k = 2 · 3 ·5 · · ··p + 1
Số k không có ước nguyên tố bởi vì khi chia cho số nguyên tố tùy ý ta
được phần dư bằng 1. Trong khi đó dễ thấy rằng ước số bé nhất m > 1
của số tự nhiên k là số nguyên tố. Mâu thuẫn này chứng minh định lí.
Euclid cũng đưa ra một bằng chứng của Định lý cơ bản của số học là
mỗi số nguyên có thể viết thành tích của các số nguyên tố.
Euclid cũng cho thấy nếu 2
n
−1 là số nguyên tố thì 2
n−1
·(2
n
−1) là
một số hoàn hảo. Nhà toán học Euler(Năm 1747) đã chỉ ra rằng tất cả
các số hoàn hảo đều có dạng trên.
1.2.2. Sàng Eratosthenes
Trong khoảng 200 TCN. Eratosthenes (Hylạp) đã nghĩ ra một thuật
toán để tính các số nguyên tố, được gọi là sàng Eratosthenes:
Trước tiên, ta viết dãy các số tự nhiên từ 1 đến n . Trong dãy đó
gạch đi số 1, vì nó không phải là số nguyên tố. Số nguyên tố đầu tiên
của dãy là 2. Tiếp theo đó ta gạch khỏi dãy tất cả những số chia hết
cho 2. Số đầu tiên không chia hết cho 2 là 3: Đó chính là số nguyên tố.
định lý cuối cùng của Ông).
10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Định lý Fermat bé là một cơ sở cho nhiều kết quả khác trong lý thuyết
số và là cơ sở cho phương pháp kiểm tra nguyên tố, vẫn đang được sử
dụng trên các MTĐT ngày nay.
1.4.1. Định lý 2(Fermat bé)
Nếu p là số nguyên tố và a là số không chia hết cho p thì a
p−1
≡ 1
(mod p)
Chứng minh(Định lý 2)
Xét p − 1 số nguyên a, 2a, , (p − 1)a, các số đó đều không chia hết
cho p, và không có hai số nào đồng dư modulo p. Như vậy, các thặng dư
dương của chúng phải là: 1, 2, , p−1 xếp theo thứ tự nào đó, từ đó ta có:
a.2a (p − 1)a ≡ 1.2 (p − 1) ≡ (p − 1)! (mod p)
Tức là: (p − 1)! ≡ 1 (mod p)
Vì ((p − 1)!, p) = 1, nên ta có : a
p−1
≡ 1 (mod p)
Như vậy để tìm ra các số nguyên tố, người ta thường cố gắng tìm các
đặc trưng của chúng thể hiện qua các đồng dư thức dễ kiểm tra. Ngoài
Định lý Fermat bé đã trình bày ở trên. Ta còn một đồng dư thức khác:
1.4.2. Định lý 3(Wilson)
Số p là số nguyên tố khi và chỉ khi (p − 1)! ≡ −1 (mod p)
Chứng minh(Định lý 3)
Trước tiên, giả sử p là số nguyên tố. Khi p = 2 , ta có:
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
(p − 1)! ≡ 1 ≡ −1 (mod 2)
1.4.3. Định lý 4(Định lý cơ bản của số học)
Mọi số nguyên lớn hơn 1 đều phân tích được một cách duy nhất
thành tích các số nguyên tố, trong đó các thừa số được viết với thứ tự
không giảm.
Chứng minh (Định lý 4)
Giả sử tồn tại những số không viết được thành tích các số nguyên tố.
Gọi n là số bé nhất trong các số đó. Như vậy n phải là hợp số, n = a.b với
a, b < n. Do định nghĩa của n các số a và b phân tích được thành tích các
số nguyên tố, nghĩa là n cũng phân tích được (mâu thuẫn với giả thuyết).
Còn phải chứng minh phân tích là duy nhất. Giả sử có
n = p
1
.p
2
p
s
= q
1
.q
2
q
r
, trong đó p
i
, q
j
là các số nguyên tố.
Giản ước những số nguyên tố bằng nhau có mặt trong hai vế, ta được
đẳng thức:
p
1.4.4. Định lý 5
Mọi hợp số n đều có ước nguyên tố nhỏ hơn
√
n.
Chứng minh(Định lý 5)
Thật vậy vì n là hợp số nên ta có thể viết n = a.b , trong đó a và b
là các số nguyên với 1 < a ≤ b < n. Rõ ràng ta phải có a hoặc b không
vượt quá
√
n. Giả sử đó là a. Ước nguyên tố của a cũng đồng thời là
ước nguyên tố của n.
Định lý trên chính là cơ sở cho thuật toán để tìm ra các số nguyên
tố nhỏ hơn hoặc bằng số n cho trước (Sàng Eratosthenes).
1.4.5. Sự phân bố các số nguyên tố:
Thoạt nhìn, các số nguyên tố dường như được phân phối giữa các số
nguyên một cách khá lộn xộn. Ví dụ trong số 100 số đứng liền trước
10000000 có chín số nguyên tố, trong khi 100 số sau chỉ có hai số nguyên
14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
tố. Legendre và Gauss đã tính toán đến mật độ của các số nguyên tố.
Gauss nói với một người bạn rằng, bất cứ khi nào ông có 15 phút rảnh
rỗi ông sẽ dành nó trong tính số nguyên tố. Đến cuối đời, ông ước tính
rằng ông đã tính tất cả các số nguyên tố lên đến khoảng 3000000. Cả
Legendre và Gauss kết luận rằng, đối với n đủ lớn, mật độ các số nguyên
tố nhỏ hơn n là 1/log(n). Legendre đã cho một ước tính cho π(n) số
nguyên tố ≤ n của π(n) = n/(log(n) − 1, 08366).
Mệnh đề nói rằng mật độ của các số nguyên tố là 1/log(n) được gọi là
định lí số nguyên tố. Người ta đã cố gắng để chứng minh điều này trong
suốt thế kỉ 19, và đạt tiến bộ đáng chú ý bởi Chebyshev và Riemann.
Kết quả cuối cùng đã được chứng minh (sử dụng phương pháp mạnh
78498 72382, 4 1, 085
10
7
664575 620420, 7 1, 071
10
8
5761455 5428681, 0 1, 061
10
9
50847534 48254942, 4 1, 054
10
10
455052512 434294481, 9 1, 048
10
11
4118054133 394813663, 7 1, 043
10
12
37607912018 36191206825, 3 1, 039
10
13
3460665535898 33407267837, 1 1, 036
Năm 2004. Hai nhà toán học Daniel A.Goldston, trường ĐHQG
Sanjosé ở California và Cem Y. Yildirim, trường ĐH Bogazici ở Istanbul,
vừa đạt được những tiến bộ kỳ diệu trong việc tìm hiểu sự phân bố
những số nguyên tố. Nhà toán học Hugl L. Montgomerry, trường ĐH
Michigan ở Ann Harbor đánh giá:"Khám phá mới này là lý thú nhất
trong 30 năm gần đây về vấn đề đó. Tuy vậy các chuyên gia vẫn kiểm
tra tính xác thực của khám phá đó."
Trong dãy n số nguyên liên tiếp k + 1, k + 2, , k + n, với k nhỏ thì
Sự phân bố các số nguyên tố có liên hệ chặt chẽ với một trong những
vấn đề nổi tiếng nhất về toán học "Giả thuyết Riemann" liên quan đến
một tổng vô hạn gọi là hàm de-ta s =
∞
n=1
1
n
s
.
Viện toán học Clay ở Cambridge, Massachusetts đã trao giải thưởng
một triệu đôla cho người chứng minh được giả thuyết Riemann. Theo
Daniel A. Goldston, kết quả nói trên sẽ cho phép cung cấp những lời
giải thích rõ ràng hơn về hàm dê-ta.
1.4.6. Số nguyên tố Mersenne
Định nghĩa:
Giả sử m là một số nguyên dương, khi đó M
m
= 2
m
− 1 được gọi là
số Mersenne thứ m. Nếu p là số nguyên tố và M
p
cũng là số nguyên tố,
thì M
p
được gọi là số nguyên tố Mersenne.
Ví dụ: M
2
, M
−1, 2
q
−1) = 2
(p,q−1)−1
. Ước chung này lớn hơn 1, vì nó là bội của q.
Do đó (p, q − 1) = p, vì p nguyên tố . Ta có q = mp + 1 và vì q lẻ, nên
m = 2k. Định lý được chứng minh.
Sau đây là ví dụ cho thấy ứng dụng của định lý trên:
Ví dụ: Để xét xem M
13
= 2
13
− 1 = 8191 có phải là số nguyên tố hay
không, ta cần xem các phép chia cho những số nguyên tố không vượt
quá
√
8191 90 . Mặt khác, theo Định lý trên, mọi ước nguyên tố đều
phải có dạng 26k + 1. Như vậy chỉ cần thử với hai số 53 và 79 : Ta thấy
M
13
là số nguyên tố.
Có nhiều thuật toán đặc biệt để kiểm tra nguyên tố các số Mersenne.
nhờ đó, người ta phát hiện được những số nguyên tố rất lớn. Mỗi lần
có một số nguyên tố Mersenne ta lại được một số hoàn hảo, số nguyên
tố Mersenne tìm được gần đây nhất (năm 2009) là số Mersenne thứ
47 là M
42643801
gồm 12837064 chữ số. Được tìm thấy bởi Old Magnar
Strindmo từ Melhus, Norway. Ông là một giáo sư công nghệ thông tin,
máy tính của ông đã làm việc với GIMPS (Great Internet Mersenne
do Pervushin tìm thấy vào năm 1883. Hai số nữa M
89
và M
207
đượ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 đến 257. Danh sách của ông đã mắc một số sai lầm, như bao
gồm cả M
67
, M
257
, và bỏ quên M
61
, M
89
và M
107
.
Phương pháp tốt nhất để kiểm tra tính nguyên tố của các số Mersenne
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) M
n
= 2
n
− 1 là số
nguyên tố nếu và chỉ nếu M
n
M
2281
đã được tìm thấy với cùng chương trình trên sau nhiều tháng nữa.
M
4253
là số nguyên tố Mersenne đầu tiên siêu lớn, trên 1000 chữ số thập
phân (titanic), và M
44497
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ố có dạng 2
43112609
− 1 . Cũng như nhiều số nguyên tố
Mersenne trước đó, nó được tìm ra nhờ dự án máy tính phân tán trên
19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyê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).
Danh sách các số nguyên tố Mersenne đã biết
STT Số nguyên tố Chữ số Ai Khi nào Bình luận
1 2
6972593
− 1 2098960 G4 1999 Mersenne 38
2 2
13466917
− 1 4053946 G5 2001 Mersenne 39
3 2
20996011
− 1 6320430 G6 2003 Mersenne 40
đó, Euler chỉ ra trường hợp 2
32
+ 1 = 4294967297 là chia hết cho 641, và
như vậy không phải là số nguyên tố:
Các số có dạng 2
n
−1 cũng thu hút sự chú ý vì dễ thấy rằng nếu n không
là số nguyên tố, số này phải là hợp số. Những số như thế được gọi là số
Mersenne M
n
vì Mersenne nghiên cứu chúng.
Euler là người có ảnh hưởng lớn đến lí thuyết số nói chung và các
số nguyên tố nói riêng. Ông mở rộng định lí Fermat bé và đưa ra phi
hàm Euler Φ(n). Như đã đề cập ở trên ông phân tích số Fermat thứ năm
20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
32
+ 1, và ông phát biểu (nhưng đã không thể chứng minh) điều mà
ngày nay gọi là luật thuận nghịch bình phương.
1.4.8. Một số số nguyên tố lớn được biết đến
Các số nguyên tố sinh đôi
Số nguyên tố sinh đôi là số nguyên tố có dạng p và p + 2 chúng khác
nhau 2 đơn vị.
Ngày 28.9.2002 Daniel Papp phát hiện ra một số nguyên tố sinh đôi
có 51090 chữ số ( 33218925.2
169690
±1,) Danh sách một số số nguyên tố
sinh đôi đã biết:
STT Số nguyên tố Chữ số Ai Khi
333333
+ 1 100355 L923 2009 Twin(p+2)
Các số nguyên tố Sophie Germain
Một số nguyên tố Sophie Germain là một nguyên tố lẻ p mà 2p + 1
cũng là một số nguyên tố.
Ngày 18.1.2003, David Underbakko đã phát hiện ra một nguyên
tố Sophie Germain có 34547 chữ số (2540041185.2
114729
− 1).
Danh sách các số nguyên tố Sophie Germain đã được tìm thấy
21
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
STT Số nguyên tố Chữ số Ai Khi
nào
Bình luận
1 18912879.2
98395
− 1 29628 p94 2002 SophieGermain(p)
2 112886032245.2
108000
− 1 32523 L99 2006 SophieGermain(p)
3 1124044292325.2
107999
− 1 32523 L99 2006 SophieGermain(p)
4 2540041185.2
114729
− 1 34547 g294 2003 SophieGermain(p)
5 7068555.2
121301
− 1 36523 L100 2005 SophieGermain(p)
Danh sách các số nguyên tố giai thừa đã biết:
22
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
STT Số nguyên tố Chữ số Ai Khi nào Bình luận
1 13033 − 1 5610 CD 1992 Primorial
2 13649 + 1 5862 D 1987 Primorial
3 15877 − 1 6845 CD 1992 Primorial
4 18523 + 1 8002 D 1989 Primorial
5 23801 + 1 10273 C 1993 Primorial
6 24029 + 1 10387 C 1993 Primorial
7 42209 + 1 18241 p8 1999 Primorial
8 15877 + 1 63142 p21 2000 Primorial
9 366439 + 1 158936 p16 2001 Primorial
10 392113 + 1 169966 p16 2001 Primorial
Vẫn còn nhiều câu hỏi mở (một số trong số đó có niên đại hàng trăm
năm) liên quan đến số nguyên tố.
1.4.9. Một số vấn đề chưa được giải quyết
1. Có vô hạn số nguyên tố sinh đôi?
2. Phỏng đoán của Goldbach (phát biểu trong một bức thư của Gold-
bach gửi Euler vào năm 1742) rằng mỗi số nguyên lớn hơn 2 có thể được
viết như là tổng của hai số nguyên tố?
3. Có vô hạn số nguyên tố dạng n
2
+ 1 ?
4. Luôn luôn có một số nguyên tố giữa n
2
và (n + 1)
2
?
5. Có vô hạn số nguyên tố Fermat?
Định nghĩa : Giả sử b là một số nguyên dương. Nếu n là hợp số nguyên
dương và b
n
≡ b (mod n), thì n được gọi là số giả nguyên tố cơ sở b.
Trong trường hợp (a, b) = 1 , ta thường dùng định nghĩa tương
đương b
n−1
≡ 1 (mod n)
Ví dụ : Số nguyên 561 = 3.11.17 là số giả nguyên tố cơ sở 2. Thật vậy,
áp dụng Định lý Fermat bé, ta có :
2
560
= (2
2
)
280
≡ 1 (mod 3)
2
560
= (2
10
)
56
≡ 1 (mod 11)
24
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
560
= (2
16
= 2kn, và do đó m = (2
n
− 1)/(2
nk
− 1) = 2
m−1
− 1
Tức là 2
m−1
≡ 1 (mod m). Vậy m là giả nguyên tố cơ sở 2.
Như vậy, để kiểm tra một số có phải là nguyên tố hay không trước
tiên ta xem nó có là giả nguyên tố cơ sở 2 hay không, sau đó có thể
tiếp tục kiểm tra đối với các cơ sở khác. Tuy nhiên, tồn tại các số giả
nguyên tố đối với mọi cơ sở, đó là các số Carmichael.
25
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Copyright: Tài liệu đại học ©