ĐẠ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
ĐẠ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
i
Mục lục
Mở đầu 1
1 Số nguyên tố 3
1.1 Định nghĩa và các tính chất . . . . . . . . . . . . . . . . 3
1.2 Một số định lý quan trọng của số học . . . . . . . . . . . 4
2 Sự phân bố các số nguyên tố 9
2.1 Một vài ký hiệu . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Hàm logarit . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Ước giá đơn giản nhất của π(x) . . . . . . . . . . . . . . 11
2.4 Hàm Chebyshev . . . . . . . . . . . . . . . . . . . . . . . 15

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
rằng nếu giới hạn lim
x→∞
π(x)
x/lnx
tồn tại thì giới hạn đó chỉ có thể bằng 1, tuy
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
2
đã định nghĩa hai hàm ϑ(x), ψ(x) và chứng minh định lý "π(x) ∼
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 c ao học K2 trường Đại học Khoa Học. Em xin bày tỏ

< d. Suy ra d
1
là ước thực
sự của d. Vì vậy d
1
là ước của a, d
1
< 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 = 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
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 ≤
√

1
và đó là sự phân tích a thành thừa số
nguyên tố.
Nếu a
1
> 1 thì a
1
phải có một ước nguyên tố p
2
, và ta có a
1
= p
2
.a
2
,
do đó a = p
1
.p
2
.a
2
, với 1 ≤ a
2
< a
1
. Nếu a
2
= 1 thì a = p
1

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
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

2
2
q
β
l
l
, ∀i = 1, , k. Vì các q
j
(j = 1, , l) là đôi
một khác nhau nên mỗi p
i
trùng với một q
j
nào đó và tương tự mỗi q
j
trùng với một p
i
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ì p
i
= q
i
, ∀i.
Nếu α
i
> β
i
thì ta chia cả hai phân tích trên cho p
β

β
i−1
i−1
.p
β
i+1.
i+1
p
β
k
k
.
Khi đó vế trái của đẳng thức trên chia hết cho p
i
nhưng vế phải thì
không chia hết cho p
i
. Đ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.

n
|(Q
n
−n!) = 1.
Mâu thuẫn. Vậy q
n
> 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 Go ldbach):
Số F
n
= 2
2
n
+ 1 được gọi là số Fermat thứ n. Cho trước hai số Fermat
F
n
và F
n+k
(k > 0), giả sử m|F
n
, m|F
n+k
.
Đặt x = 2
2
n
, ta có:
F

k
−1
− x
2
k
−2
+ − 1
Vì vậy F
n
|(F
n+k
− 2). Mặt khác m|F
n
nên m|(F
n+k
− 2). Từ đó suy ra
m|2. Do F
n
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ố F
1
, F
2
, , F
n
đề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á F
n

1
(n
0
, p, t).
Suy ra p|f(n
0
+pt) với t tuỳ ý. Ta chọn được t đủ lớn để |f(n
0
+pt)| > p.
Suy ra f(n
0
+ 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

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
−β

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
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

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) = o(g(x)), x → ω, nghĩa là lim
x→ω
f(x)
g(x)
= 0.
* f(x) ∼ g(x), x → ω, nghĩa là lim
x→ω
f(x)
g(x)
= 1, hay f(x) = g(x) +
o(g(x)), x → ω.
Ví dụ:
Khi x → +∞ ta có:
10x = O(x); sinx = O(1)
x = o(x
2
); x + 1 ∼ x
Khi x → 0 ta có:
x
2
= O(x); x
2
= o(x)
sinx ∼ x; 1 + x ∼ 1
* f(x)  g(x), x → ω, nghĩa là ∃A, A

> 0 : A.f(x) < g(x) < A


+
x
−n
.e
x
>
x
(n + 1)!
−→ ∞ khi x −→ ∞
Vì vậy hàm e
x
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 e
x
. 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.
Nghĩa là ta có
lnx
x
δ
−→ 0, khi x −→ ∞, hay lnx = o(x
δ
), ∀δ > 0.
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.
Hàm
x
lnx
là hàm số quan trọng trong lý thuyết các số nguyên tố và
nó sẽ được sử dụng nhiều trong quá trình chứng minh các định lý dưới

−1
=
n

i=1
(1 +
1
p
i
+
1
p
2
i
+ )
=

1
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
số nguyên tố p
1
, p
2
, , p
n
, kể cả 1. Vì vậy

p≤x

p≤x
(1 −
1
p
)
−1
≤
π(x)+1

k=2
(1 −
1
k
)
−1
=
π(x)+1

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 = p
n
thì π(p
n

−1
> lnx
suy ra

p≤x
−ln(1 −
1
p
) > lnlnx.
Ta có:
−ln(1 −
1
p
) =
1
p
+
1
2p
2
+
1
3p
3
+
<
1
p
+
1


p≤x
1
p(p −1)
> lnlnx −
∞

m=2
1
m(m −1)
= lnlnx −1.
Vậy chuỗi

1
p
là chuỗi phân kỳ.
Định lí 2.3. ∀x ≥ 1 ta có:
π(x) ≥
lnx
2ln2
p
n
≤ 4
n
.
Chứng minh.
Giả sử 2, 3, 5, , p
j
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

khác nhau nên m
không thể nhận nhiều hơn 2
j
giá trị khác nhau. Mặt khác, với mỗi số n
ta luôn có n
2
1
≤ n ≤ x nên n
1
≤
√
n ≤
√
x. Điều đó chứng tỏ không có
nhiều hơn
√
x giá trị khác nhau của n
1
. Từ đó suy ra N(x) ≤ 2
j
√
x.
Tiếp theo ta đặt j = π(x), ta được p
j+1
> x, và N(x) = x.
Ta có: x = N(x) ≤ 2
π(x)
.
√
x

Định lí 2.4. (Định lý Legendre)
lim
x→∞
π(x)
x
= 0.
Chứng minh.
Ta có đẳng thức sau:
1+π(x)−π(
√
x) = [x]−
r

i=1
[
x
p
i
]+

1≤i<j≤r
[
x
p
i
p
j
]+ +(−1)
r
[

1
+ C
r
2
+ + C
r
r
= 2
r
.
Vì thế nếu bỏ dấu [ ] ở vế phải sẽ có một sai số R mà |R| < 2
r
. Suy ra:
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
15
1 + π(x) − π(
√
x) = x −
r

i=1
x
p
i
+

1≤i,j≤r
x
p
i

p≤x
(1 −
1
p
)
−1
> lnx hay

p≤
√
x
(1 −
1
p
) <
1
ln
√
x
.
Từ đó suy ra
1 + π(x) − π(
√
x) <
x
ln
√
x
+ 2
r

ln2
. Đặt u = αlnx với α <
1
ln2
ta được:
π(x) < αlnx +
x
lnlnx + lnα
+ x
αln2
suy ra π(x) < c
x
lnlnx
suy ra
π(x)
x
<
c
lnlnx
→ 0, x → ∞.
Vậy lim
x→∞
π(x)
x
= 0.
2.4 Hàm Chebyshev
Định nghĩa 2.2. Định nghĩa hai hàm Chebyshev ϑ(x) và ψ(x) như sau:
ϑ(x) =

p≤x

ψ(x) =

p
k
≤x,k≥1
lnp
=

p≤x
(

p
k
≤x,k≥1
1)lnp
=

p≤x
[
lnx
lnp
]lnp
≤

p≤x
lnx = π(x)lnx.
Bổ đề 2.1. Với n ≥ 1 và 1 ≤ k ≤ n ta luôn có:
C
k−1
n

r(k) =
C
k
n
C
k−1
n
=
n!
k!(n − k)!
n!
(k − 1)!(n − k + 1)!
=
(k − 1)!(n − k + 1)!
k!(n − k)!
=
n −k + 1
k
.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
17
Vậy r(k) > 1 ⇔ n − k + 1 > k ⇔ k <
n + 1
2
r(k) < 1 ⇔ n −k + 1 < k ⇔ k >
n + 1
2
r(k) > 1 ⇔ n −k + 1 = k ⇔ k =
n + 1
2

n−1
2n
< C
n
2n
C
n−2
2n
< C
n−1
2n
< C
n
2n

C
1
2n
< C
n
2n
C
n+1
2n
< C
n
2n
C
n+2
2n

2n
+ 1
≤ 2 + (2n − 1)C
n
2n
≤ 2nC
n
2n
.
Suy ra
2
2n
2n
≤ C
n
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
18
Định lí 2.5. Ta luôn có:

p≤n
p < 4
n
, ∀n ∈ R
∗
+
. (2.4)
ϑ(x) < xln4, ∀x ∈ R, x ≥ 1. (2.5)

m
.
Nếu p là số nguyên tố thoả mãn m + 2 ≤ p ≤ 2m + 1 thì p chia hết
tích (2m + 1)2m(2m −1)(2m −2) (m + 2), nhưng p không chia hết m!.
Vì vậy p|M, suy ra

m+2≤p≤2m+1
|M, ∀m ∈ Z
∗
+
.
Từ đó suy ra

m+2≤p≤2m+1
≤ M < 4
m
. (2.6)
Tiếp theo ta sẽ chứng minh (2.4) bằng phương pháp quy nạp theo n
Rõ ràng bất đẳng thức (2.4) đúng cho n = 1, n = 2.
Giả sử (2.4) đúng cho mọi số nguyên dương m < n
+ Nếu n chẵn thì

p≤n
p =

p≤n−1
p < 4
n−1
< 4
n

.4
m
= 4
2m+1
= 4
n
.
Ta có biểu thức (2.4).
Nếu x ≥ 1 thì n = [x] ≥ 1 và ϑ(x) = ϑ(n) = ln

p≤n
p < ln4
n
≤ xln4.
Vậy ϑ(x) ≤ xln4.
Bổ đề 2.3. Cho α là một số thực dương và d là một số tự nhiên lớn hơn
0, thế thì số các bội dương của d không vượt quá α bằng [
α
d
].
Chứng minh.
Thật vậy, gọi m là số các số tự nhiên khác 0, bội của d, không vượt
quá α, thế thì các bội đó là d, 2d, 3d, , md và ta có:
md ≤ α < (m + 1)d
⇔ m ≤
α
d
< m + 1
⇔ m = [
α

p
2
] số là bội của p
2
.
Từ 1 đến n có [
n
p
3
] số là bội của p
3
.

Vì vậy luỹ thừa của p trong dạng phân tích tiêu chuẩn của n! là luỹ
thừa của p trong tích p.2p [
n
p
]p = p

n
p

[
n
p
]!. Lập luận tương tự ta có
luỹ thừa của p trong dạng phân tích tiêu chuẩn của [
n
p
]! là luỹ thừa của

p
3
]! ta được luỹ thừa của p trong
phân tích tiêu chuẩn của n! là e
p
=

k≥1
[
n
p
k
] ( Chú ý rằng trong tổng
trên chỉ gồm một số hữu hạn số hạng khác 0).
Định lí 2.6. Giả sử a, b là các số nguyên với a < b và f(t) là một hàm
đơn điệu trên đoạn [a, b], ta có:
min(f(a), f(b)) ≤
b

n=a
f(n) −

b
a
f(t)dt ≤ max(f(a), f(b)). (2.8)
Chứng minh.
Nếu f(t) là một hàm tăng trên đoạn [n, n + 1] thì ta có :
f(n) ≤

n+1

f(t)dt ≤
b

n=a
f(n) ≤ f(a) +

b
a
f(t)dt.
Như vậy, nếu f(t) là một hàm đơn điệu trên đoạn [a, b] thì ta có (2.8).
Định lí 2.7. Với ∀x ≥ 2 ta có:

n≤x
lnn = xlnx − x + O(lnx). (2.9)
Chứng minh.
Xét hàm f(t) = lnt là hàm số tăng trên đoạn [1, x]. Theo định lý 2.6
ta có:
ln1 +

x
1
lntdt ≤

n≤x
lnn ≤ lnx +

x
1
lntdt.
Vậy

Chứng minh.
Theo bổ đề 2.4 ta c ó:
n! =

p≤n
p
e
p
, e
p
=

k≥1
[
n
p
k
]. (2.10)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
22
Logarit hoá hai vế của (2.10) ta được:
lnn! =

p≤n

k≥1
[
n
p
k

p
2
] + [
n
p
3
] +

≤ n

p≤n
lnp

1
p
2
+
1
p
3
+

≤ n

p≤n
lnp.
1
p(p −1)
≤ n
∞

[
n
p
]lnp = nlnn + O(n). (2.12)
Sử dụng (2.12) với n và 2n ta được:

p≤2n

[
2n
p
] −2[
n
p
]

lnp = O(n). (2.13)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên