..
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ YẾN
SỐ NGUYÊN TỐ VÀ SỰ PHÂN
BỐ SỐ NGUYÊN TỐ
LUẬN VĂN THẠC SỸ TOÁN HỌC
THÁI NGUYÊN - NĂM 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ YẾN
SỐ NGUYÊN TỐ VÀ SỰ PHÂN
BỐ SỐ NGUYÊN TỐ
Chuyên nghà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:
PGS. TS. NÔNG QUỐC CHINH
THÁI NGUYÊN - NĂM 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
i
Mục lục
Mở đầu
1
1 Số nguyên tố
1.1 Định nghĩa và các tính chất . . . . . . . . . . . . . . . .
1.2 Một số định lý quan trọng của số học . . . . . . . . . . .
3
3
4
2 Sự phân bố các số nguyên tố
2.1 Một vài ký hiệu . . . . . . . . . . . .
2.2 Hàm logarit . . . . . . . . . . . . . .
2.3 Ước giá đơn giản nhất của π(x) . . .
2.4 Hàm Chebyshev . . . . . . . . . . . .
2.5 Định lý Mertens . . . . . . . . . . . .
2.6 Định lý số nguyên tố và chứng minh
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
10
11
11
15
25
32
Kết luận
46
Tài liệu tham khảo
47
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1
Mở đầu
Vành số nguyên Z là một vành chính mà +1 và −1 là các phần tử khả
nghịch duy nhất. Ta đã biết mọi số nguyên khác 0 và khác ±1 đều phân
tích được một cách duy nhất thành một tích các phần tử bất khả quy
trong Z. Một số nguyên dương bất khả quy được gọi là một số nguyên
tố. Vì vậy mọi số tự nhiê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 thừa số nguyên tố. Vấn đề số nguyên tố là một trong
những vấn đề trọng tâm của lý thuyết số. Một câu hỏi đương nhiên được
đặt ra là "có bao nhiêu số nguyên tố trong tập hợp số tự nhiên?". Nếu
chỉ có một số hữu hạn các số nguyên tố thì vấn đề số nguyên tố sẽ trở
nên rất đơn giản, và các vấn đề khác trong số học cũng trở thành đơn
giản. Song, ngay từ thời Euclid người ta đã biết rằng tập các số nguyên
tố là vô hạn. Từ đó một loạt các câu hỏi được đặt ra. Bài toán về mật
độ các số nguyên tố trong dãy số tự nhiên, bài toán tìm một biểu thức
lấy giá trị là các số nguyên tố với mọi giá trị tự nhiên của biến, bài toán
tìm số nguyên tố thứ n,.... Một vấn đề lớn của lý thuyết số nguyên tố
là nghiên cứu hàm π(x), biểu thị số các số nguyên tố không vượt quá x,
với x là một số thực dương.
Người ta không hi vọng xác định được dễ dàng π(x) theo x. Đầu tiên
π(x)
A. M. Legendre đã chứng minh được rằng lim
= 0, nghĩa là hầu
x→∞ x
khắp các số tự nhiên là hợp số. Tiếp theo, người ta tìm một hàm số sơ
cấp f (x) tương đương với π(x). P. L. Chebyshev đã chứng minh được
π(x)
rằng nếu giới hạn lim
tồn tại thì giới hạn đó chỉ có thể bằng 1, tuy
x→∞ x/lnx
nhiên ông không chứng minh được sự tồn tại giới hạn trên. Sau đó ông
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2
x
lnx
nếu và chỉ nếu ψ(x) ∼ x"Năm 1896, định lý số nguyên tố đã được chứng
minh bởi Hadamard và Dela Vallee Poussin bằng cách sử dụng phương
pháp giải tích phức. Năm 1949, Selberg đã chứng minh được định lý số
nguyên tố bằng phương pháp sơ cấp, không sử dụng giải tích phức. Với
mục đích nghiên cứu sự phân bố các số nguyên tố trong tập các số tự
nhiên chúng tôi đã chọn đề tài này.
Nội dung của luận văn gồm 2 chương:
Chương 1: Số nguyên tố. Trình bày định nghĩa số nguyên tố, những
tính chất cơ bản của số nguyên tố và một số định lý quan trọng của số
học.
Chương 2: Sự phân bố các số nguyên tố. Nêu khái niệm hàm π(x),
trình bày ước giá đơn giản nhất của hàm π(x) và chứng minh định lý số
nguyên tố.
Trong quá trình thực hiện luận văn của mình em đã nhận được sự
hướng dẫn, giúp đỡ tận tình của PGS. TS. Nông Quốc Chinh, nhận được
những ý kiến quý báu của các thầy cô khoa Toán - tin cùng tập thể các
bạn học viên lớp cao học K2 trường Đại học Khoa Học. Em xin bày tỏ
lòng cảm ơn sâu sắc tới thầy giáo Nông Quốc Chinh, em xin chân thành
cảm ơn các thầy cô và các bạn. Em xin chân thành cảm ơn trường THPT
Lê Hồng Phong và gia đình đã giúp đỡ, động viên em hoàn thành khoá
học. Đến nay luận văn đã được hoàn thành. Tuy nhiên với khoảng thời
gian không nhiều, và năng lực của bản thân có hạn nên luận văn không
tránh khỏi những thiếu sót. Em rất mong nhận được những ý kiến đóng
góp của các thầy cô cùng toàn thể bạn đọc.
đã định nghĩa hai hàm ϑ(x), ψ(x) và chứng minh định lý "π(x) ∼
Thái Nguyên, ngày 20 tháng 08 năm 2010.
Nguyễn Thị Yến.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
3
Chương 1
Số nguyên tố
1.1
Định nghĩa và các tính chất
Định nghĩa 1.1. Số nguyên p được gọi là số nguyên tố nếu p > 1 và p
chỉ có ước là 1 và chính nó. Số nguyên p > 1 không là số nguyên tố thì
là hợp số.
Tập các số nguyên tố thường được kí hiệu là P .
Tính chất 1.1. Ước tự nhiên khác 1 nhỏ nhất của một số tự nhiên là
một số nguyên tố.
Chứng minh.
Cho số a ∈ N , cho d là ước nhỏ nhất của a, d 6= 1. Nếu d không
nguyên tố thì d = d1 .d2 , trong đó 1 < d1 , d2 < d. Suy ra d1 là ước thực
sự của d. Vì vậy d1 là ước của a, d1 < d. Điều này mâu thuẫn với sự nhỏ
nhất của d.
Tính chất 1.2. Cho p nguyên tố, a ∈ N , a 6= 0. Khi đó:
(a, p) = p ⇔ p|a.
(a, p) = 1 ⇔ p - a.
Tính chất 1.3. Nếu tích của nhiều số chia hết cho số nguyên tố p thì
có ít nhất một thừa số chia hết cho p.
Tính chất 1.4. 2 là số nguyên tố nhỏ nhất và là số nguyên tố chẵn duy
nhất.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
4
Tính chất 1.5. Nếu n là hợp số thì n có ít nhất một ước nguyên tố
√
không vượt quá n.
Chứng minh.
Giả sử n là hợp số, n = a.b, trong đó a, b ∈ Z, 1 < a ≤ b < n. Ta có
√
√
√
hoặc a ≤ n hoặc b ≤ n. Giả sử a ≤ n, vì a có ước nguyên tố, giả
√
sử đó là p, nên p cũng là ước của n, p ≤ n.
√
Vậy n có ước nguyên tố không vượt quá n.
Hệ quả 1.1. Nếu số tự nhiên a > 1 không có ước nguyên tố nào trong
√
nửa khoảng (1, a] thì a là số nguyên tố.
1.2
Một số định lý quan trọng của số học
Định lí 1.1. Mọi số nguyên dương a > 1 đều phân tích được thành tích
các thừa số nguyên tố, sự phân tích đó là duy nhất nếu không kể đến thứ
tự các thừa số.
Chứng minh.
* Tính phân tích được: Giả sử a là số nguyên bất kì thoả mãn a > 1,
thế thì a phải có một ước nguyên tố, chẳng hạn là p1 . Vậy ta có a = p1 .a1 ,
trong đó 1 ≤ a1 < a.
Nếu a1 = 1 thì ta có a = p1 và đó là sự phân tích a thành thừa số
nguyên tố.
Nếu a1 > 1 thì a1 phải có một ước nguyên tố p2 , và ta có a1 = p2 .a2 ,
do đó a = p1 .p2 .a2 , với 1 ≤ a2 < a1 . Nếu a2 = 1 thì a = p1 .p2 là dạng
phân tích của a thành thừa số nguyên tố, còn nếu a2 > 1 thì ta lập lại
lý luận ở trên được số nguyên tố p3 ,.... Quá trình này phải kết thúc sau
một số hữu hạn lần vì ta có a > a1 > a2 > ...., nên tồn tại n ∈ N thoả
mãn an = 1, và ta được a = p1 .p2 .....pn .
Trong sự phân tích trên thì có thể xảy ra trường hợp trong tích có
nhiều thừa số nguyên tố lặp lại, gọi p1 , p2 , ....., pk là các thừa số nguyên
tố đôi một khác nhau của a, với các bội tương ứng là α1 , α2 , .....αk ,
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
(αi > 0, i = 1, ..., k), thì ta được a = pα1 1 .pα2 2 ....pαk k , gọi là dạng phân tích
tiêu chuẩn của a.
* Tính duy nhất: Ta giả sử a có hai dạng phân tích tiêu chuẩn:
a = pα1 1 .pα2 2 ....pαk k = q1β1 .q2β2 ....qlβl .
Khi đó: pi | q1β1 .q2β2 ....qlβl , ∀i = 1, ...., k. Vì các qj (j = 1, ..., l) là đôi
một khác nhau nên mỗi pi trùng với một qj nào đó và tương tự mỗi qj
trùng với một pi nào đó. Vì vậy k = l và nếu trong hai dạng phân tích
tiêu chuẩn trên đều sắp xếp các thừa số nguyên tố theo thứ tự tăng dần
thì pi = qi , ∀i.
Nếu αi > βi thì ta chia cả hai phân tích trên cho pβi i , ta được:
i−1
i+1.
pα1 1 .pα2 2 ...piαi −βi ....pαk k = pβ1 1 .pβ2 2 ....pi−1
.pi+1
....pβk k .
β
β
Khi đó vế trái của đẳng thức trên chia hết cho pi nhưng vế phải thì
không chia hết cho pi . Điều này là mâu thuẫn.
Tương tự, nếu βi > αi ta dễ dàng suy ra mâu thuẫn.
Vì vậy αi = βi , ∀i.
Định lí 1.2. (Định lý thứ nhất của Euclid)
Nếu p nguyên tố, p|ab thì p|a hoặc p|b.
Chứng minh.
Giả sử p là số nguyên tố và p|ab. Nếu p - a thì (a, p) = 1, do đó
∃x, y : xa + yp = 1 hay xab + ypb = b. Mà p|ab và p|pb nên suy ra
p|b.
Hệ quả 1.2. Nếu p|abc....l thì p|a hoặc p|b ............hoặc p|l.
Định lí 1.3. (Định lý thứ hai của Euclid)
Số các số nguyên tố là vô hạn.
Chứng minh.
* Cách 1 (Chứng minh của Euclid): Giả sử 2, 3, 5, ....., p là dãy
các số nguyên tố không vượt quá p. Đặt q = 2.3.5....p + 1, khi đó q không
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
6
chia hết cho số nào của dãy 2, 3, 5, ...., p. Từ đó suy ra q nguyên tố hoặc
q phân tích được thành tích các thừa số nguyên tố, trong đó không có
thừa số nào là 2, 3, 5, ..., p nên phải có một ước nguyên tố nằm trong
khoảng(p, q) hay q chia hết cho một số nguyên tố nằm trong khoảng
(p, q). Từ đó suy ra luôn tồn tại số nguyên tố lớn hơn p. Định lý được
chứng minh.
* Cách 2: Xét số Qn = n! + 1, n ≥ 1. Khi đó Qn có ít nhất một ước
nguyên tố, kí hiệu là qn . Nếu qn ≤ n thì qn |n! và do đó qn |(Qn − n!) = 1.
Mâu thuẫn. Vậy qn > n, tức là với mọi số nguyên dương n thì đều tồn
tại số nguyên tố lớn hơn n nên tập các số nguyên tố là vô hạn. Định lý
được chứng minh.
* Cách 3 (Chứng minh của Goldbach):
n
Số Fn = 22 + 1 được gọi là số Fermat thứ n. Cho trước hai số Fermat
Fn và Fn+k (k > 0), giả sử m|Fn , m|Fn+k .
n
Đặt x = 22 , ta có:
n+k
Fn+k − 2 (22 + 1) − 2
=
Fn
22n + 1
n+k
22 − 1
= 2n
2 +1
k
x2 − 1
=
x+1
k
k
= x2 −1 − x2 −2 + ... − 1
Vì vậy Fn |(Fn+k − 2). Mặt khác m|Fn nên m|(Fn+k − 2). Từ đó suy ra
m|2. Do Fn là số lẻ nên m = 1. Như vậy ta chứng minh được hai số
Fermat bất kỳ không có ước chung lớn hơn 1.
Từ đó suy ra rằng mỗi một trong các số F1 , F2 , ..., Fn đều chia hết cho
một số nguyên tố lẻ p mà p không là ước của bất kỳ số nào khác trong
dãy trên. Vậy có ít nhất n số nguyên tố không vượt quá Fn . Do dãy số
Fermat là vô hạn nên có vô hạn số nguyên tố.
Định lí 1.4. Tồn tại những dãy số liên tục là các hợp số mà độ dài của
nó lớn hơn một số n bất kỳ cho trước.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
7
Chứng minh.
Cho trước số n bất kỳ. Theo định lý Euclid ở trên ta thấy luôn tồn
tại số nguyên tố p > n. Xét dãy 2, 3, 5, ..., p các số nguyên tố không vượt
quá p. Đặt q = 2.3.5....p thì q + 2, q + 3, q + 4, ....., q + p là các hợp số.
Rõ ràng đó là p-1 số hợp số liền nhau thoả mãn p − 1 > n.
Định lí 1.5. Không tồn tại đa thức f (x) ∈ Z[x] mà tất cả các giá trị
của nó tại các điểm x ∈ Z đều là nguyên tố.
Chứng minh.
Giả sử f (x) ∈ Z[x], degf (x) ≥ 1. Khi đó lim f (x) = ±∞. Suy ra
x→+∞
∃n0 ∈ Z sao cho |f (n0 )| > 1. Giả sử p là một ước nguyên tố của f (n0 ),
xét khai triển
f (n0 + pt) = f (n0 ) + p.f1 (n0 , p, t).
Suy ra p|f (n0 + pt) với t tuỳ ý. Ta chọn được t đủ lớn để |f (n0 + pt)| > p.
Suy ra f (n0 + pt) là một hợp số.
Định lí 1.6. Cho a là một số nguyên với dạng phân tích tiêu chuẩn
a = pα1 1 .pα2 2 ....pαk k . Khi đó số nguyên d là ước của a khi và chỉ khi nó có
dạng d = pβ1 1 .pβ2 2 ....pβk k với 0 ≤ βi ≤ αi , i = 1, ..., k.
Chứng minh.
Giả sử d là ước của a, khi đó tồn tại số nguyên q sao cho a = dq.
Đẳng thức này chứng tỏ rằng nếu d > 1 thì mọi ước nguyên tố của d là
ước nguyên tố của a và số mũ của ước nguyên tố ấy trong dạng phân
tích tiêu chuẩn của d không lớn hơn số mũ của nó trong dạng phân tích
tiêu chuẩn của a. Bởi vậy:
d = pβ1 1 .pβ2 2 ....pβk k , 0 ≤ βi ≤ αi , i = 1, ..., k.
Nếu d = 1 thì ta viết d = pβ1 1 .pβ2 2 ....pβk k , βi = 0, ∀i.
Ngược lại, giả sử a và d là hai số nguyên thoả mãn điều kiện của định
lý, khi đó αi − βi ≥ 0, i = 1, ..., k nên q = pα1 1 −β1 .pα2 2 −β2 ....pαk k −βk là một
số nguyên và a = dq, nghĩa là d là ước của a.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
8
Định lý trên cho ta xác định tất cả các ước của một số tự nhiên a > 1,
nếu số nguyên a > 1 có dạng phân tích tiêu chuẩn a = pα1 1 .pα2 2 ....pαk k thì
số các ước nguyên dương của a là (α1 + 1)(α2 + 1)...(αk + 1), định lý trên
cũng cho ta phương pháp để tìm ước chung lớn nhất và bội chung nhỏ
nhất của nhiều số.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
9
Chương 2
Sự phân bố các số nguyên tố
Dãy các số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
.... Bằng cách dùng sàng Eratosthenes ta dễ dàng xây dựng một bảng
các số nguyên tố trong giới hạn N .
Ta đã biết nếu n là số tự nhiên, n ≤ N và n không là số nguyên tố thì
√
n chia hết cho một số nguyên tố nhỏ hơn hoặc bằng n. Ta viết xuống
dãy các số 2, 3, 4, 5, 6, 7, 8, ....N và thực hiện tiến trình như sau:
* Vì 2 là số nguyên tố đầu tiên nên ta xoá những số sau 2 và chia hết
cho 2. Số đứng sau 2 còn lại đầu tiên là 3 nên 3 là số nguyên tố.
* Tiếp tục bỏ những số sau 3 và chia hết cho 3. Số đứng sau 3 còn
lại đầu tiên là 5 nên 5 là số nguyên tố.
* Gạch bỏ những số sau 5 và chia hết cho 5. Số đứng sau 5 còn lại
đầu tiên là 7 nên 7 là số nguyên tố.
Tiếp tục quá trình như vậy ta gạch bỏ khỏi dãy những số chia hết
√
cho các số nguyên tố nhỏ hơn N . Quá trình sẽ dừng lại cho đến khi
√
gặp số nguyên tố lớn hơn hoặc bằng N . Tất cả các số chưa bị xoá là
số nguyên tố.
Như vậy theo thuật toán trên, để kiểm tra tính nguyên tố của n ta
cần thực hiện số phép chia đúng bằng số các số nguyên tố nhỏ hơn hoặc
√
bằng n. Tuy nhiên số phép chia đó là rất lớn nếu n là những số lớn.
Giả sử rằng 2, 3, 5, 7, ...., p là dãy các số nguyên tố không vượt quá
p. Khi đó mọi số nhỏ hơn hoặc bằng p đều chia hết cho một số nào
đó trong dãy trên. Vì vậy nếu đặt q = 2.3.5.7...p thì tất cả các số
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
q ± 2, q ± 3, q ± 4, ..., q ± p đều là hợp số. Như vậy mặc dù số các số
nguyên tố là vô hạn, tức p có thể rất lớn, nhưng tất cả các số nguyên tố
ấy chỉ là một vài điểm so với tập các hợp số.
Khi nói đến sự phân bố các số nguyên tố có một vài câu hỏi được
đặt ra như sau: Có một công thức tổng quát, đơn giản nào để xác định
số nguyên tố thứ n không? Có một công thức tổng quát để xác định số
nguyên tố tiếp theo một số nguyên tố cho trước không? Có một quy tắc
để từ một số nguyên tố p đã cho có thể tìm được số nguyên tố q lớn
hơn không? Có bao nhiêu số nguyên tố không vượt quá một số x cho
trước?... Nhiệm vụ chính của chương này là trình bày câu trả lời của
những câu hỏi đó.
2.1
Một vài ký hiệu
Cho f (x), g(x) là các hàm số xác định trên D, g(x) ≥ 0, ∀x ∈ D.
Ta đưa vào các ký hiệu sau đây:
* f (x) = O(g(x)), x → ω, nghĩa là ∃A : |f (x)| < Ag(x), x → ω.
f (x)
* f (x) = o(g(x)), x → ω, nghĩa là lim
= 0.
x→ω g(x)
f (x)
* f (x) ∼ g(x), x → ω, nghĩa là lim
= 1, hay f (x) = g(x) +
x→ω g(x)
o(g(x)), x → ω.
Ví dụ:
Khi x → +∞ ta có:
10x = O(x);
sinx = O(1)
x = o(x2 );
x+1∼x
x2 = O(x);
x2 = o(x)
sinx ∼ x;
1+x∼1
Khi x → 0 ta có:
* f (x) g(x), x → ω, nghĩa là ∃A, A0 > 0 : A.f (x) < g(x) < A0 .f (x).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
Chú ý rằng f (x) = O(1) nghĩa là ∃C : |f (x)| < C, hay hàm f (x) bị
chặn.
2.2
Hàm logarit
Lý thuyết về sự phân bố các số nguyên tố cần sử dụng một số kiến
thức về tính chất của hàm logarit. Trong luận văn này chúng ta sẽ thừa
nhận và sử dụng những tính chất của hàm logarit và hàm mũ đã được
học trong giải tích cổ điển. Xét hàm số f (x) = ex , ta có:
x2 x3
xn
xn+1
+
+ .... +
+
+ ...
2!
3!
n! (n + 1)!
x
x−n .ex >
−→ ∞ khi x −→ ∞
(n + 1)!
ex = 1 + x +
Vì vậy hàm ex tiến ra ∞ nhanh hơn so với hàm luỹ thừa của x. Ta đã
biết hàm lnx là hàm ngược của hàm ex . Nên hàm lnx tiến ra ∞ chậm
hơn so với hàm luỹ thừa dương của x.
lnx
Nghĩa là ta có δ −→ 0, khi x −→ ∞, hay lnx = o(xδ ), ∀δ > 0.
x
Tương tự, ta có hàm ln(lnx) tiến ra ∞ chậm hơn so với hàm luỹ thừa
dương của lnx.
x
Hàm
là hàm số quan trọng trong lý thuyết các số nguyên tố và
lnx
nó sẽ được sử dụng nhiều trong quá trình chứng minh các định lý dưới
đây.
2.3
Ước giá đơn giản nhất của π(x)
Định nghĩa 2.1. Định nghĩa π(x) là hàm số học biểu thị số các số
nguyên tố không vượt quá x
X
π(x) =
1.
p≤x
Chẳng hạn: π(10) = 4, π(100) = 25. Do tập các số nguyên tố là vô hạn
nên ta có π(x) → ∞ khi x → ∞.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
12
Định lí 2.1. Với ∀x ≥ 1 ta luôn có π(x) > lnx − 1; Nếu ta kí hiệu pn
là số nguyên tố thứ n thì pn < en+1 < 3n+1 .
Chứng minh.
Ta có :
n
n
Y
1 −1 Y
1
1
(1 − ) =
(1 + + 2 + ....)
pi
pi pi
i=1
i=1
X1
=
.
n
Trong tổng trên n chạy qua tất cả các số tự nhiên là tích của các thừa
Q
P1
1
số nguyên tố p1 , p2 , ..., pn , kể cả 1. Vì vậy p≤x (1 − )−1 =
, trong
p
n
tổng đó n chạy qua tất cả các số tự nhiên mà các thừa số nguyên tố của
nó nhỏ hơn hoặc bằng x.
Ta có:
Z [x]+1
[x]
X1 X
dt
1
≥
>
= ln([x] + 1) > lnx.
n n=1 n
t
1
π(x)+1
Y
1 −1
1
(1 − ) ≤
(1 − )−1
p
k
p≤x
Y
k=2
π(x)+1
=
Y
k=2
k
k−1
2.3...π(x).(π(x) + 1)
1.2....π(x)
= π(x) + 1.
=
Suy ra π(x) + 1 > lnx hay π(x) > lnx − 1.
Nếu x = pn thì π(pn ) = n. Vì vậy:
n = π(pn ) > lnpn − 1 ⇒ lnpn < n + 1
⇒ pn < en+1 < 3n+1 .
Định lí 2.2. (Định lý Euler)
P1
Chuỗi
là chuỗi phân kỳ.
p
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
13
Chứng minh.
Theo định lý 2.1 ta có:
Y
1
(1 − )−1 > lnx
p
p≤x
suy ra
1
−ln(1 − ) > lnlnx.
p
p≤x
X
Ta có:
1
1
1
1
−ln(1 − ) = + 2 + 3 + ...
p
p 2p
3p
1
1
1
< + 2 + 3 + ...
p p
p
1
1
= +
p p(p − 1)
nên
X1
p≤x
p
+
X
p≤x
1
> lnlnx.
p(p − 1)
Từ đó suy ra
X1
p≤x
p
> lnlnx −
> lnlnx −
X
p≤x
∞
X
1
p(p − 1)
1
m(m − 1)
m=2
= lnlnx − 1.
Vậy chuỗi
P1
là chuỗi phân kỳ.
p
Định lí 2.3. ∀x ≥ 1 ta có:
lnx
2ln2
pn ≤ 4n .
π(x) ≥
Chứng minh.
Giả sử 2, 3, 5, ..., pj là j số nguyên tố đầu tiên. Kí hiệu N (x) là hàm
biểu thị số các số nguyên n không vượt quá x và không chia hết cho bất
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
14
kỳ số nguyên tố nào lớn hơn pj . Biểu thị số nguyên n dưới dạng n = n21 .m,
trong đó m không chia hết cho bình phương của một số nguyên tố bất
b
kỳ. Khi đó ta thấy m = 2b1 3b2 ....pjj , trong đó các bk (k = 1, 2...j) hoặc
bằng 0, hoặc bằng 1. Vì vậy có đúng 2j bộ b1 , b2 , ..., bj khác nhau nên m
không thể nhận nhiều hơn 2j giá trị khác nhau. Mặt khác, với mỗi số n
√
√
ta luôn có n21 ≤ n ≤ x nên n1 ≤ n ≤ x. Điều đó chứng tỏ không có
√
√
nhiều hơn x giá trị khác nhau của n1 . Từ đó suy ra N (x) ≤ 2j x.
Tiếp theo ta đặt j = π(x), ta được pj+1 > x, và N (x) = x.
√
Ta có: x = N (x) ≤ 2π(x) . x
√
⇔
lnx ≤ ln(2π(x) . x)
√
⇔ lnx ≤ π(x).ln2 + ln x
1
lnx ≤ π(x).ln2
⇔
2
lnx
⇔ π(x) ≥
.
2ln2
lnpn
Nếu đặt x = pn thì π(x) = n, khi đó n ≥
⇔ lnpn ≤ 2nln2 ⇔
2ln2
pn ≤ 4n .
Định lí 2.4. (Định lý Legendre)
π(x)
= 0.
x→∞ x
lim
Chứng minh.
Ta có đẳng thức sau:
r
X
X
√
x
x
x
1+π(x)−π( x) = [x]− [ ]+
[
]+...+(−1)r [
]. (2.1)
p
p
p
p
...p
i
i
j
1
r
i=1
1≤i lnx hay
p
p≤x
Y
Y
1
1
(1 − ) < √ .
p
ln x
√
p≤ x
Từ đó suy ra
√
1 + π(x) − π( x) <
√
2x
x
√ + 2r <
+ 2 x.
lnx
ln x
√
√
Áp dụng lập luận trên nhưng thay x bởi u mà 1 < u < x ta được:
x
x
π(x) − π(u) <
+ 2u . Suy ra π(x) < u +
+ 2u .
lnu
lnx
x
lnx
1
Chọn u sao cho 2u <
, khi đó u <
. Đặt u = αlnx với α <
lnu
ln2
ln2
ta được:
x
π(x) < αlnx +
+ xαln2
lnlnx + lnα
x
suy ra
π(x) < c
lnlnx
π(x)
c
suy ra
<
→ 0, x → ∞.
x
lnlnx
π(x)
Vậy lim
= 0.
x→∞ x
2.4
Hàm Chebyshev
Định nghĩa 2.2. Định nghĩa hai hàm Chebyshev ϑ(x) và ψ(x) như sau:
X
Y
ϑ(x) =
lnp = ln
p.
p≤x
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
p≤x
http://www.lrc-tnu.edu.vn
16
ψ(x) =
X
lnp = ln
Y
p.
pk ≤x
pk ≤x
Chẳng hạn:
ϑ(10) = ln2 + ln3 + ln5 + ln7.
ψ(10) = 3ln2 + 2ln3 + ln5 + ln7.
Hàm ϑ(x) và ψ(x) đếm các số nguyên tố p ≤ x và các luỹ thừa nguyên
tố pk ≤ x, rõ ràng ϑ(x) ≤ ψ(x).
lnx
Nếu pk ≤ x thì k ≤ [
], và vì vậy:
lnp
X
ψ(x) =
lnp
pk ≤x,k≥1
=
X
(
X
1)lnp
p≤x pk ≤x,k≥1
X lnx
=
[
]lnp
lnp
p≤x
X
lnx = π(x)lnx.
≤
p≤x
Bổ đề 2.1. Với n ≥ 1 và 1 ≤ k ≤ n ta luôn có:
n+1
Cnk−1 < Cnk nếu và chỉ nếu k <
2
n
+
1
Cnk−1 > Cnk nếu và chỉ nếu k >
2
n+1
k−1
k
Cn = Cn nếu và chỉ nếu k =
, n lẻ.
2
Trong đó Cnk là tổ hợp chập k của n.
Chứng minh.
Đặt
Cnk
r(k) = k−1
Cn
n!
k!(n − k)!
=
n!
(k − 1)!(n − k + 1)!
(k − 1)!(n − k + 1)! n − k + 1
=
=
.
k!(n − k)!
k
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
17
n+1
2
n+1
r(k) < 1 ⇔ n − k + 1 < k ⇔ k >
2
n+1
r(k) > 1 ⇔ n − k + 1 = k ⇔ k =
, n lẻ.
2
Bổ đề 2.2. Với mọi số nguyên dương n ta có:
Vậy r(k) > 1 ⇔ n − k + 1 > k ⇔ k <
22n
n
≤ C2n
< 22n .
2n
Chứng minh.
Theo công thức nhị thức Newton ta có:
2n
2
= (1 + 1)
2n
=
2n
X
k
n
C2n
> C2n
.
(2.2)
k=0
Theo bổ đề 2.1 ta có:
n−1
n
C2n
< C2n
n−2
n−1
n
C2n
< C2n
< C2n
................
1
n
C2n
< C2n
n+1
n
C2n
< C2n
n+2
n+1
n
C2n
< C2n
< C2n
................
2n−1
n
C2n
< C2n
.
Cộng vế với vế của các bất đẳng thức trên ta được:
2n
2
=
2n
X
k
C2n
=1+
k=0
≤ 2 + (2n −
2n−1
X
k=1
n
1)C2n
k
C2n
+1
n
2nC2n
.
≤
Suy ra
22n
n
≤ C2n
.
2n
(2.3)
Từ (2.2) và (2.3) ta có điều phải chứng minh.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -