ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
- - - - - - - - - - - - - - - - - -
LÊ VĂN DUY
MỘT SỐ ĐỊNH LÝ CƠ BẢN CỦA
LÝ THUYẾT SỐ VÀ ÁP DỤNG
LUẬN VĂN THẠC SỸ TOÁN HỌC
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60.46.01.13
Người hướng dẫn khoa học:
TS. NGUYỄN VĂN MINH
THÁI NGUYÊN - NĂM 2014
1
Mục lục
Lời cảm ơn 2
Mở đầu 3
1 Số nguyên tố và một số định lý quan trọng của lý thuyết
số 5
1.1 Định nghĩa số nguyên tố và một số tính chất . . . . . . . . 5
1.1.1 Định nghĩa số nguyên tố . . . . . . . . . . . . . . . 5
1.1.2 Một vài tính chất về số nguyên tố . . . . . . . . . . 5
1.2 Một số định lý cơ bản của lý thuyết số . . . . . . . . . . . . 6
1.2.1 Một vài định nghĩa và kí hiệu . . . . . . . . . . . . . 6
1.2.2 Các định lý cơ bản của lý thuyết số . . . . . . . . . 7
2 Áp dụng giải một số bài toán sơ cấp 24
2.1 Ứng dụng Định lý Dirichlet về cấp số cộng . . . . . . . . . 24
2.2 Ứng dụng Định lý Euler, Định lý Fermat nhỏ. . . . . . . . 29
2.3 Ứng dụng Định lý Wilson . . . . . . . . . . . . . . . . . . 33
2.4 Ứng dụng Định lý Trung Quốc về phần dư . . . . . . . . . 33
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Tài liệu tham khảo 40

2
Lời cảm ơn
Sau một thời gian nghiên cứu, luận văn thạc sỹ của tôi đã được hoàn
thành với tên đề tài Một số định lý cơ bản của lý thuyết số và áp
dụng. Những kết quả mà luận văn có được đó là nhờ sự hướng dẫn tận
tình và nghiêm khắc của TS. Nguyễn Văn Minh. Tôi xin bày tỏ lòng biết
ơn chân thành và sâu sắc đến thầy.
Tôi xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo và Khoa
Toán - Tin của Trường Đại học Khoa học - Đại học Thái Nguyên đã tạo
điều kiện cho tôi hoàn thành luận văn này trong thời gian vừa qua. Đội
ngũ cán bộ của phòng đào tạo và Khoa Toán - Tin đã hết lòng ủng hộ,
giúp đỡ lớp Cao học Toán K6A chúng tôi với một thái độ nhiệt tình và
thân thiện nhất. Điều này sẽ mãi là ấn tượng rất tốt đẹp trong lòng mỗi
chúng tôi đối với nhà trường.
Tôi xin cảm ơn gia đình, bạn bè và những người đã quan tâm, tạo điều
kiện, động viên cổ vũ để tôi có thể hoàn thành nhiệm vụ của mình.
Thái Nguyên, tháng 05 năm 2014
Người thực hiện
Lê Văn Duy
3
Mở đầu
1. Lý do chọn đề tài
Lý thuyết số là một ngành của toán học lý thuyết nghiên cứu về tính
chất của số nói chung và của số nguyên nói riêng, cũng như những lớp
rộng hơn các bài toán mà phát triển từ những nghiên cứu của nó. Trong lý
thuyết số, 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.
Luận văn Một số định lý cơ bản của lý thuyết số và áp dụng
trình bày một số vấn đề liên quan đến mảng số nguyên tố và các định lý
quan trọng của lý thuyết số.
2. Mục đích nghiên cứu
Đề tài "Một số định lý cơ bản của lý thuyết số và áp dụng"
nhằm hệ thống lại một số định lý quan trọng của lý thuyết số và áp dụng
các định lý đó vào giải toán sơ cấp.
3. Đối tượng và phạm vi nghiên cứu
Nghiên cứu về số nguyên tố, các định lý cơ bản của lý thuyết số, nhằm
hệ thống các định lý các bài toán liên quan đến đề tài nghiên cứu.
4
4. Phương pháp nghiên cứu
Tổng hợp các tài liệu liên quan, nắm vững cốt lõi của nội dung kiến
thức từ đó sắp xếp, trình bày hệ thống và khai thác các ứng dụng theo đề
tài nghiên cứu.
5. Ý nghĩa khoa học và thực tiễn của đề tài
Có được một tài liệu phù hợp cho việc dạy học ở cấp trung học cơ sở
và trung học phổ thông.
6. Cấu trúc của luận văn
Luận văn gồm phần mở đầu, 2 chương, kết luận và tài liệu tham khảo.
Chương 1. Số nguyên tố và một số định lý quan trọng của số học
Chương 2. Áp dụng giải một số bài toán sơ cấp
Thái Nguyên, tháng 05 năm 2014
Người thực hiện

Lê Văn Duy
5
Chương 1
Số nguyên tố và một số định lý
quan trọng của lý thuyết số
Chương này trình bày một vài tính chất cơ bản của số nguyên tố và
một số định lý quan trọng của lý thuyết số. Nội dung của chương được
tổng hợp từ các tài liệu tham khảo [2] [3] [5].
1.1 Định nghĩa số nguyên tố và một số tính chất
1.1.1 Định nghĩa số nguyên tố
Trong toán học có nhiều định nghĩa khác nhau về số nguyên tố, sau
đây tôi nêu một định nghĩa về số nguyên tố đơn giản và dễ hiểu nhất.
Định nghĩa 1.1. Số nguyên tố là số nguyên dương lớn hơn 1, chỉ chia hết
cho 1 và chính nó. Số nguyên dương khác 1 và không là số nguyên tố thì
được gọi là hợp số.
Kí hiệu P là tập các số nguyên tố.
1.1.2 Một vài tính chất về số nguyên tố
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 với d = 1. Nếu
d không nguyên tố thì d = d
1
.d
2
, trong đó 1 < d
1
, d
2
< d. suy ra d
1

là ước
thực sự của a, mà d
1
< d điều này mâu thuẫn với sự nhỏ nhất của d. Suy
ra điều phải chứng minh. ✷
Tính chất 1.2. Cho p là một số nguyên tố, và a ∈ N, a = 0 khi đó
(a, p) = p ⇔ p | a,
6
(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. Số 2 là số nguyên tố nhỏ nhất và là số nguyên tố chẵn
duy nhất.
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 và 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 và 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ý cơ bản của lý thuyết số
1.2.1 Một vài định nghĩa và kí hiệu
 Một số định nghĩa
Định nghĩa 1.2. Định nghĩa hàm Chebyshev ϑ(x) như sau:
ϑ(x) =

p≤x
lnp, x ∈ R, x > 1.
Ví dụ 1.1. ϑ(10) = ln2 + ln3 + ln5 + ln7.
Định nghĩa 1.3. Định nghĩa hàm π(x) như sau:
Hàm π(x), với x là số thực dương, số các số nguyên tố không vượt quá x.
Ví dụ 1.2. π(1) = 0, π(2) = 1, π(3) = 2.
Định nghĩa 1.4. Một hệ thặng dư đầy đủ modulo m là một tập hợp các
số nguyên sao cho mỗi số nguyên tùy ý đều đồng dư modulo m với đúng
một số của tập hợp.
Ví dụ 1.3. Tập hợp các số 0, 1, , m − 1 là một hệ thặng dư đầy đủ
modulo m. Hệ này gọi là hệ không âm bé nhất modulo m.
7
Định nghĩa 1.5. Giả sử m là một số nguyên dương. Phi hàm Euler được
định nghĩa là số các số nguyên dương nhỏ hơn m và nguyên tố cùng nhau
với m.
Kí hiệu Phi hàm Euler qua ϕ(m).
Ví dụ 1.4. ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(5) = 4.
Định nghĩa 1.6. Một hệ thặng dư thu gọn modulo m là một tập hợp
gồm ϕ(m) số nguyên sao cho mỗi phần tử của tập hợp đều nguyên tố cùng

nhau với m, và không có hai phần tử khác nhau nào đồng dư modulo m.
Ví dụ 1.5. Tập hợp 1, 3, 5, 7 là một hệ thặng dư thu gọn modulo 8. Tập
hợp −3, −1, 1, 3 cũng vậy.
 Một số kí hiệu
Cho f (x), g(x) là các hàm số xác định trên miền D ∈ R, g(x) ≥ 0,
∀x ∈ D. Ta đưa vào các kí hiệu sau đây.
∗f(x) = O(g(x)), x → w, có nghĩa là ∃A ∈ R, A > 0 : | f (x) |<
Ag(x), x → w.
∗ f(x) = o(g(x)), x → w, có nghĩa là lim
x→w
f(x)
g(x)
= 0.
∗ f(x) ∼ g(x), x → w, có nghĩa là lim
x→w
f(x)
g(x)
= 1, hay f(x) = g(x) +
o(g(x)), x → w.
∗ f(x) = O(1) nghĩa là tồn tại C : | f(x) |< C, hay hàm f (x) bị chặn.
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); 1 + x ∼ 1

sinx ∼ x.
1.2.2 Các định lý cơ bản của lý thuyết số
Định lý 1.1 (Định lý Cơ bản của Số học). M ọi số nguyên dương n > 1
đều biểu diễn được một cách duy nhất dưới dạng tích các số nguyên tố,
trong đó các thừa số nguyên tố được viết theo thứ tự không giảm.
Chứng minh. Để chứng minh định lý, ta cần bổ đề sau.
8
Bổ đề 1.1. Giả sử a, b, c là các số nguyên dương, đồng thời (a, b) = 1,
a | bc. Khi đó a | c.
Chứng minh. Vì (a, b) = 1 nên tồn tại các số nguyên x, y sao cho ax +
by = 1. Nhân 2 vế của phương trình này với c, ta có acx + bcy = c. Ta
thấy a | (acx + bcy), vì đó là tổ hợp tuyến tính của a và bc. Do đó a | c. ✷
Hệ quả 1.2. Nếu p | a
1
a
2
a
n
, trong đó p là số nguyên tố và a
1
, a
2
, , a
n
là các số nguyên, thì tồn tại i, 1 ≤ i ≤ n sao cho p | a
i
.
Chứng minh. Ta chứng minh bằng quy nạp. Trường hợp n = 1 là hiển
nhiên. Giả sử mệnh đề đúng với n. Xét tích n + 1 số nguyên , a
1

a
n+1
và
giả sử p | a
1
a
n+1
. Khi đó p | (a
1
a
n
)a
n+1
, nên theo Bổ đề 1.1, p | a
1
a
n
hoặc p | a
n+1
. Nếu p | a
1
a
n
theo giả thiết quy nạp thì tồn taị i, 1 ≤ i ≤ n
sao cho p | a
i
. Do đó p | a
i
với i nào đó, 1 ≤ i ≤ n + 1 ✷
Chứng minh định lý. Trước hết ta chứng tỏ rằng mọi số nguyên dương

n > 1 đều có thể viết dưới dạng tích các thừa số nguyên tố, ít nhất là bằng
một cách. Giả sử ngược lại, tồn tại các số nguyên dương không có tính
chất trên. Gọi n là số bé nhất trong các số đó. Nếu n là số nguyên tố thì
hiển nhiên n biểu diễn được dưới dạng tích các số nguyên tố (ở đây tích chỉ
gồm một phần tử). Như vậy, n là hợp số. Đặt n = a.b, với 1 < a < n và
1 < b < n. Nhưng a và b nhỏ hơn n nên chúng phải là tích các số nguyên
tố, và do đó, n cũng là tích các số nguyên tố. Mâu thuẫn này chứng minh
rằng số nguyên tùy ý biểu diễn được dưới dạng tích các số nguyên tố.
Ta chứng minh biểu diễn nói trên là duy nhất. Giả sử tồn tại số nguyên
dương có hơn một cách biểu diễn. Gọi n là số nguyên dương nhỏ nhất
trong các số đó, và n có hai cách biểu diễn.
n = p
1
p
2
p
s
= q
1
q
2
q
t
,
trong đó p
1
, p
2
, , p
s

và q
1
, q
2
, , q
t
đều là các số nguyên tố, và p
1
≤ p
2
≤
≤ p
s
và q
1
≤ q
2
≤ ≤ q
t
. Trước tiên ta sẽ chỉ ra rằng p
1
= q
1
. Giả
sử p
1
= q
1
. Không mất tính tổng quát, có thể giả thiết p
1

< q
1
. Như vậy,
p
1
< q
i
với mọi i = 1, 2, 3, , t (vì các số nguyên tố trong mỗi biểu diễn
được xếp theo thứ tự không giảm). Khi đó, p
1
 q
i
với mọi i. Theo Hệ quả
1.2, p
1
 q
1
q
t
= n : vô lý. Vậy p
1
= q
1
và n
.
.
. p
1
= p
2

p
3
p
s
= q
2
q
3
q
t
.
Vì n
.
.
. p
1
là số nguyên dương nhỏ hơn n, mà n là số nguyên dương nhỏ
nhất có quá một biểu diễn, nên n
.
.
. p
1
chỉ có thể biểu diễn dạng tích các
số nguyên tố theo một cách duy nhất. Như vậy, s = t và q
i
= p
i
với mọi i.
Vậy định lý được chứng minh. ✷
9

Định lý 1.2 (Định lý Euclid). Tồn tại vô hạn số nguyên tố.
Chứng minh.
Cách 1.
Xét số Q
n
= n! + 1, với n ≥ 1 . Khi đó Q
n
có ít nhất một ước nguyên tố,
kí hiệu là q
n
. Nếu q
n
≤ n thì q
n
| n! và do đó q
n
| (Q
n
− n!) = 1 suy ra
mâu thuẫn. Như vậy với mọi số nguyên dương n đều có số nguyên tố lớn
hơn n, nên tập các số nguyên tố là vô hạn. ✷
Cách 2 (Chứng minh của Euclid).
Giả sử tập hợp số nguyên tố 2, 3, 5 , p là hữu hạn. Ta xét số n là tích của
các số nguyên tố cộng thêm 1,
n = 2.3.5 p + 1.
Rõ ràng n sẽ có một ước nguyên tố q nào đó. Nhưng vì n không chia hết
cho số nguyên tố nào ở dãy trên nên ước số nguyên tố q của n sẽ không
nằm trong dãy số trên. Vậy suy ra mâu thuân với giả thiết. ✷
Định lý 1.3. Với mọi số nguyên dương n, tồn tại ít nhất n số liên tiếp,
mà mỗi một trong chúng đều là hợp số.

Chứng minh.
Xét dãy các số nguyên liên tiếp
(n + 1)! + 2, (n + 1)! + 3, , (n + 1)! + (n + 1).
Khi 2 ≤ j ≤ (n + 1), j | (n + 1)! + j. Vậy các số trong dãy nói trên đều
lá hợp số. ✷
Định lý 1.4. Chuỗi số

p∈P
1
p
là chuỗi số phân kì.
Chứng minh. Xét
n

i=1

1 −
1
p
i

−1
=
n

i=1

1 +
1
p

i
+
1
p
i
2
+

=

1
n
.
Trong tổng trên ta cho n chạy qua tất cả các số tự nhiên là tích của tất
cả các thừa số nguyên tố, p
1
, p
2
, , p
n
, kể cả 1.
Ta có

p≤x

1 −
1
p

−1

=

1
n
.
10
Trong tổng trên cho n chạy qua tất cả các số mà các thừa số của nó nhỏ
hơn hoăc bằng x. Suy ra

1
n
≥
[x]

n=1
1
n
>
[x]+1

1
dt
t
= ln([x] + 1) > lnx.
Vậy

p≤x

1 −
1

p

−1
> lnx.
Suy ra

p≤x
−ln

1 −
1
p

> lnlnx.
Mà
−ln

1 −
1
p

=
1
p
+
1
2p
2
+
1

3p
3
+
<
1
p
+
1
p
2
+
1
p
3
+
=
1
p
+
1
p(p −1)
,
nên

p≤x
1
p
+

p≤x

1
p(p −1)
> lnlnx.
Từ đó suy ra

p≤x
1
p
> lnlnx −

p≤x
1
p(p −1)
> lnlnx −
∞

m=2
1
m(m −1)
= lnlnx −1.
Vậy chuỗi

p∈P
là chuỗi phân kì. ✷
Định lý 1.5. Tồn tại một hằng số k sao cho

2<p≤x
1
p
< klnlnx, nếu x > 3.

11
Chứng minh. Ta có p
n
≥ B
1
nlnn suy ra ta có

2<p≤x
1
p
=
π(x)

n=2
1
p
n
<
π(x)

n=2
1
B
1
nlnx
<
1
B
1
[x]


n=2
1
nlnn
.
Hơn nữa ta cũng có
1
nlnn
=
n

n=1
dt
nlnn
≤
n

n=1
dt
tlnt
.
Do
1
nlnn
≤
1
tlnt
trên [n − 1, n] nếu n ≥ 3, khi đó

2<p≤x

1
p
<
1
B
1
[x]

n=2
1
nlnn
≤
1
2B
1
ln2
+
1
B
1
lnlnx −
1
B
1
lnln2
=
1
B
1
lnlnx + C < klnlnx.

Nếu k đủ lớn thì ta có điều phải chứng minh. ✷
Định lý 1.6.
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

x
p
1
p
r

, (1)
ở đây p
1
, p
2
, , p
r
là tất cả các số nguyên tố không vượt quá
√
x. Số các
số hạng trong vế phải của (1) là
1 + C
1
r
+ C
2
r
+ + C
r
r
= C
0

r
+ C
1
r
+ C
2
r
+ + 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
1 + π(x) −π(
√
x) = x −
r

i=1
x
p
i
+

1≤i<j≤r
x
p

i
p
j
+ + (−1)
r
x
p
1
p
r
+ R
= x
r

i=1

1 −
1
p
i

+ R = x

p≤
√
x
(1 −
1
p
) + R.

12
Ta đã có

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
<
2x
lnx
+ 2
√
x
.
Áp dụng lập luận trên nhưng thay
√
x bởi u mà 1 < u <
√
x ta được
π(x) − π(u) <
x
lnu
+ 2
u
. Suy ra π(x) < u +
x
lnu
+ 2
u
.
Chọn u sao cho 2
u
<

x
lnu
, khi đó u <
lnx
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. ✷
Định lý 1.7. Nếu x ≥ 2 thì


p≤x
p ≤ 4
x
.
Chứng minh. Hiển nhiên định lý đúng với 2 ≤ x < 3. Giả sử định lý
đúng với số tự nhiên n lẻ với n ≥ 3. Khi đó định lý đúng với n ≤ x < n+2
vì

p≤x
p =

p≤n
p < 4
n
< 4
x
Như vậy ta chỉ cần chứng minh định lý đúng với số nguyên lẻ n. Ta sử
dụng phương pháp quy nap. Định lý đúng với n = 3, ta giả sử định lý
đúng với mọi số tự nhiên lẻ nhỏ hơn hoặc bằng n (n ≥ 5). Đặt k =
n + 1
2
,
hoặc k =
n −1
2
sao cho k là một số lẻ, khi đó k ≥ 3 và n −k là số lẻ, hơn
nữa n−k = 2k ±1 ≥ k +1. Nếu p là số nguyên tố với k < p ≤ n thì p | n!.
Nhưng p không chia hết cho cả k! và (n −k)! bởi vậy p | C
k

n
=
n!
k!(n −k)!
.
Từ đó suy ra tích của tất cả các số nguyên tố chia hết cho C
k
n
và như vậy
ta có

k<p≤n
p ≤ C
k
n
. Do C
k
n
= C
n−k
n
và chúng đều là khai triển của nhị thức
(1 + 1)
n
. Suy ra C
k
n
< 2
n−1
. Do k < n và theo giả thiết quy nạp ta được


p≤n
p =

p≤k
p.

k<p≤n
p < 4
k
.2
n−1
= 2
n+2k−1
≤ 2
2n
= 4
n
.
13
Vậy suy ra điều phải chứng minh. ✷
Bổ đề 1.2. 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, ta 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 =

α
d

.
✷
Bổ đề 1.3. Với mọi n ≥ 2, n ∈ N ta có
n! =

p≤n
p
e
p
, e
p
=
∞

k=1

n
p
k


.
Chứng minh. Theo Bổ đề 1.2 thì
Từ 1 đến n có

n
p

số là bội của p.
Từ 1 đến n có

n
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 lũy thừa của p trong dạng phân tích tiêu chuẩn của n! là lũy thừa
của p trong tích p.2p


n
p

= p

n
p

.

n
p

!.
Lập luận tương tự ta có lũy thừa của p trong dạng phân tích tiêu chuẩn
của

n
p

! là lũy thừa của p trong tích
p.2p





n
p


p




.p = p

n
p
2

.

n
p
2

!.
Lập luận tương tự đối với

n
p
2

!,

n
p
3


!, Ta được lũy thừa của p trong
14
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 chi gồm một số hữu hạn số hạng khác 0.) ✷
Bổ đề 1.4. Giả sử c
1
, c
2
, c
3
, , c
n
là một dãy số cho trước. Với C(t) là
một hàm số được xác định như sau
C(t) =

n≤t
c
n
,

n
1
là số nguyên thỏa mãn c
j
= 0, với mọi j < n
1
, f(t) là một hàm số có
đạo hàm liên tục, với mọi t ≥ n
1
.
Khi đó ta có

n≤x
c
n
f(n) = C(x)f(x) −
x

n
1
C(t)f

(t)dt.
Định lý 1.8. Giả sử a, b là các số nguyên với a < b và f (t) là 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)
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

n
f(t)dt ≤ f(n + 1).
Nếu f(t) là một hàm tăng trên đoạn [a, b] thì ta có
f(a) +
b

a
f(t)dt ≤
b

n=a
f(n) ≤ f(b) +
b

a
f(t)dt.
Tương tự, nếu f(t) là một hàm giảm trên đoạn [n, n + 1] thì ta có
f(n + 1) ≤
n+1

n
f(t)dt ≤ f(n).

15
Nếu f(t) là một hàm giảm trên đoạn [a, b] thì ta có
f(b) +
b

a
f(t)dt ≤
b

n=a
f(n) ≤ f(a) +
b

a
f(t)dt.
Như vậy, nếu f(t) là hàm đơn điệu trên đoạn [a, b] thì ta có (2). ✷
Định lý 1.9. Với mọi x ≥ 2 ta có

n≤x
lnn = xlnx − x + O(lnx).
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ý 1.8 ta có
ln1 +
x

1
lntdt ≤

n≤x
lnn ≤ lnx +

x

1
lntdt.
Vậy ta có

n≤x
lnn ≤ lnx + xlnx − x + 1
⇔

n≤x
lnn ≤ xlnx −x + (lnx + 1)
⇔

n≤x
lnn ≤ xlnx −x + O(lnx).
✷
Định lý 1.10. Với mọi x ≥ 2 luôn ∃C
1
, C
2
, 0 ≤ C
1
≤ C
2
sao cho
C
1
x < ϑ(x) < C
2

x,

p≤x
lnp
p
= lnx + O(1).
Chứng minh. Theo Bổ đề 1.3 ta có
n! =

p≤n
p
e
p
, e
p
=
∞

k=1

n
p
k

. (3)
16
Lấy logarit hóa 2 vế của (3) ta được
lnn! =

p≤n


k≥1

n
p
k

lnp
=

p≤n

n
p

lnp +

p≤n
lnp

n
p
2

+

n
p
3


+

.
Mà ta lại có

p≤n
lnp

n
p
2

+

n
p
3

+

≤ n

p≤n
lnp

1
p
2
+
1

p
3
+

≤ n

p≤n
lnp.
1
p(p −1)
≤ n
∞

m=2
lnm
m(m −1)
= O(n).
Từ đó suy ra
lnn! =

p≤n

n
d

lnp + O(n). (4)
Theo Định lý 1.9 ta có

n≤x
lnn = xlnx − x + O(lnn)

⇔ lnn! = nlnn − n + O(lnn)
⇔ lnn! = nlnn + O(n).
Vì vậy
nlnn + O(n) =

p≤n

n
p

lnp + O(n).
Suy ra

p≤n

n
p

lnp = nlnn + O(n). (5)
Từ (5) với n = 2n ta được

p≤2n

2n
p

lnp −2

n
p


lnp

= O(n). (6)
17
Từ (6) suy ra
ϑ(2n) −ϑ(n) =

n<p≤2n
lnp ≤

p≤2n

2n
p

− 2

n
p

lnp.
Như vậy ϑ(2n) −ϑ(n) < Cn.
Đặt n = [x] ta có
ϑ(2x) −ϑ(x) = ϑ([2x]) − ϑ([x])
= ϑ([2x]) −ϑ(2[x]) + ϑ(2[x]) − ϑ([x]).
Từ đó suy ra ϑ(2x) − ϑ(x) < Cx. Lấy k =

lnx
ln2


+ 1 thì 2
k
> x và
ϑ(x) =
k

i=1

ϑ(
x
2
i−1
) −ϑ(
x
2
i
)

< C
∞

k=1
x
2
i
= Cx, (do
∞

i=1

1
2
i
= 1). Như vậy
∃C
2
> 0 để ϑ(x) < C
2
x.
Từ (5) ta có

p≤n
n
p
lnp + O(

p≤n
lnp) = nlnn + O(n)
⇔

p≤n
n
p
lnp + O(n) = nlnn + O(n)
⇔

p≤n
lnp
p
= lnn + O(1).

Với n = [x] ta được lnx −lnn = O(1). Suy ra

p≤n
lnp
p
=

p≤[x]
lnp
p
= lnx + O(1). (7)
Từ (6) ta có

αx<p<≤x
lnp
p
= ln
1
α
+ O(1), (0 < α < 1),

p≤αx
lnp
p
= lnαx + O(1). (8)
Lấy (7) trừ (8) ta được

αx<p<≤x
lnp
p

= lnx −lnαx + O(1) = ln
1
α
+ O(1).
18
Mặt khác

αx<p<≤x
lnp
p
<
1
α

αx<p<≤x
lnp =
1
αx
(v(x) −ϑ(2x)) =
ϑ(x)
αx
+ O(1).
Từ đó suy ra ϑ(x) > αx

ln
1
α
+ O(1)

. Khi α → 0

+
thi ln
1
α
→ +∞. Do
đó có thể chọn được α để ln
1
α
+O(1) > 0 vậy ∃C
1
> 0 sao cho ϑ(x) > C
1
x.
Định lý 1.10 đươc chứng minh. ✷
Định lý 1.11. Tồn tại hằng số b
1
sao cho

p≤x
1
p
= lnlnx + b
1
+ O(
1
lnx
), ∀x ≥ 2. (9)
Chứng minh. Ta có thể viết

p≤x

1
p
=

p≤x
lnp
p
.
1
lnp
=

2≤n≤x
f(n).g(n).
Trong đó
f(n) =



lnp
p
nếu n = p là một số nguyên tố,
0 trong các trường hợp khác.
g(n) =
1
lnt
, t ≥ 1.
Đặt F (t) =

n≤t

f(n) =

p≤t
lnp
p
thì F (t) = 0 với mọi t < 2. Theo Định
lý 1.10 ta có F (t) = ln(t) + r(t), trong đó r(t) = O(1), từ đó suy ra
∞

2
r(t)
t(lnt)
2
dt hội tụ tuyệt đối và
∞

x
r(t)
t(lnt)
2
dt = O(
1
lnx
).
Bằng phép lấy tổng riêng ta thu được

p≤x
1
p
=


n≤x
f(n)g(n)
= F (x)g(x) −
x

2
F (t)g

(t)dt
19
=
lnx + r(x)
lnx
+
x

2
lnx + r(x)
lnx
= 1 + O(
1
lnx
) +
x

2
1
tlnt
dt +

x

2
r(t)
t(lnt)
2
dt
= lnlnx + 1 −lnln2 +
∞

2
r(t)
t(lnt)
2
dt −
∞

x
r(t)
t(lnt)
2
dt + O(
1
lnx
)
= lnlnx + b
1
+ O(
1
lnx

).
Ở đây
b
1
= 1 −lnln2 +
∞

2
r(t)
t(lnt)
2
dt.
✷
Định lý 1.12. Nếu tồn tại giới hạn lim
x→+∞
π(x)lnx
x
thì giới hạn đó phải
bằng 1.
Chứng minh. Đặt α lim
x→+∞
π(x)lnx
x
, ta suy ra
π(x)lnx
x
= α + o(1), x → ∞.
Vậy
π(x) = α
x

lnx
+ o(
x
lnx
).
Áp dụng Bổ đề 1.4, với c
n
= 1, f(x) =
1
x
ta được

p≤x
1
p
=

p≤x
1.f(x) −
x

2
C(t).f

(t)dt (C(x) =

p≤x
1)
=
π(x)

x
+
x

2
π(t)
t
2
dt
20
=
α
lnx
+ o(
1
lnx
) +
x

2
[
αt
t
2
lnt
+ o(
t
t
2
lnt

)]dt
=
α
lnx
+ o(
1
lnx
) +
x

2
[
α
tlnt
+ o(
1
tlnt
)]dt.
Ta lại có
x

2
α
tlnt
dt = αlnlnt |
x
2
= αlnlnx −αlnln2,
x


2
o(
1
tlnt
)dt = o(lnlnx).
Vậy

p≤x
1
p
= αlnlnx + o(lnlnx).
Theo Định lý 1.11 ta suy ra α = 1. ✷
Định lý 1.13 (Định lý Dirichlet về cấp số cộng). Cho a, b là 2 số nguyên
dương và nguyên tố cùng nhau, thế thì sẽ có vô hạn số nguyên tố có dạng
ax + b với x > 0.
Việc chứng minh Định lý Dirichlet về cấp số cộng rất phức tạp,
vượt ra ngoài khuôn khổ của bài viết nên tác giả không chứng
minh.
Định lý 1.14 (Định lý Wilson). Với mọi số nguyên tố p, ta có
(p −1)! ≡ −1(modp).
Chứng minh. Để chứng minh định lý ta có bổ đề sau.
Bổ đề 1.5. Giả sử p là một số nguyên tố. Số nguyên a là nghịch đảo
modulo p của chính nó khi và chỉ khi
a ≡ 1 (mod p) hoặc a ≡ −1 (mod p).
Chứng minh bổ đề. Nếu a ≡ 1 (mod p) hoặc a ≡ −1 (mod p) thì a
2
≡ 1
(mod p) nên a là nghịch đảo của chính nó. Ngược lại, giả sử a là nghịch
đảo của chính nó, tức là a
2

= a.a ≡ 1 (modp). Khi đó p | (a
2
− 1).Vì
a
2
− 1 = (a − 1)(a + 1) mà p nguyên tố, nên p | (a −1) hoặc p | (a + 1).
Do đó, a ≡ 1 (mod p) hoặc a ≡ −1 (mod p). ✷
21
Chứng minh định lý. Khi p = 2, ta có: (p − 1)! = 1 ≡ −1 (mod 2).
Như vậy, Định lý Wilson đúng với p = 2.
Bây giờ, giả sử p là số nguyên tố lớn hơn 2. Khi đó, với mỗi số nguyên a
thì 1 ≤ a ≤ p − 1, tồn tại nghịch đảo ¯a, 1 ≤ ¯a ≤ p − 1 sao cho a¯a ≡ 1
(mod p). Theo Bổ đề 1.5, các số nguyên dương mà nhỏ hơn p mà là nghịch
đảo của chinh nó là 1 và p −1. Như vậy ta có thể nhóm các số nguyên từ
2 đến p − 2 thành

p
p −3

cặp, mà tích của chúng đồng dư 1 modulo p.
Do đó
2.3 (p −3)(p − 2) ≡ 1 (mod p).
Nhân hai vế với 1 và p −1 ta được
(p −1)! ≡ 1.(p −1) ≡ −1 (mod p)
✷
Định lý 1.15 (Định lý Fermat nhỏ). Giả sử p nguyên tố và a là số nguyên
dương với p  a. Khi đó
a
p−1
≡ 1 (mod p).

Chứng minh. Xét p −1 số nguyên a, 2a, , (p −1)a. Không có số nguyên
nào trong các số nói trên chia hết cho p, vì nếu p | ja với j nào đó thì p | j
do (a, p) = 1. Mà ta có 1 ≤ j ≤ p − 1. Hơn nữa, không có hai số nguyên
nào trong dẫy đồng dư modulo p. Thật vậy nếu ja ≡ ka (mod p) thì do
(a, p) = 1 nên suy ra j ≡ k (mod p), tức là j = k, (vì 1 ≤ j, k ≤ p − 1).
Như vậy, các số nguyên a, 2a, , (p − 1)a là tập hợp (p − 1) số nguyên
không đồng dư 0 và không có 2 số nào đồng dư nhau modulo p, nên các
thặng dư dương bé nhất của hệ đó phải là 1, 2, , p − 1. xếp theo thứ tự
nào đó. Từ đó suy ra
a.2a (p −1)a ≡ 1 (p −1) (mod p).
Vậy
a
p−1
(p −1)! ≡ (p −1)! (mod p).
Vì ((p − 1)!, p) = 1 nên ta được
a
p−1
≡ 1 (mod p).
✷
22
Định lý 1.16 (Định lý Euler). Giả sử m là số nguyên dương và a là số
nguyên tố cùng nhau với m.
Khi đó
a
ϕ(m)
≡ 1 (mod m),
trong đó ϕ(m) là hàm Euler.
Chứng minh
Ta có bổ đề sau.
Bổ đề 1.6. Giả sử r

1
, r
2
, , r
ϕ(m)
là hệ thặng dư thu gọn modulo n, a là
số nguyên dương và (a, n) = 1. Khi đó, tập hợp ar
1
, ar
2
, , ar
ϕ(n)
cũng là
hệ thặng dư thu gọn modulo n.
Chứng minh bổ đề.
Trước tiên ta chứng tỏ rằng, mỗi số nguyên ar
j
là nguyên tố cùng nhau
với n. Giả sử ngược lại, (ar
j
, n) > 1 với mọi j nào đó. Khi đó tồn tại ước
nguyên tố p của (ar
j
, n). Do đó, hoặc p | a, hoặc p | r
j
, tức là hoặc p | a
và p | n, hoặc p | r
j
và p | n. Tuy nhiên, không thể có p | r
j

và p | n, vì r
j
và n nguyên tố cùng nhau. Tương tự không thể có p | a và p | n. Vậy, ar
j
và n nguyên tố cùng nhau với mọi j = 1, 2, , ϕ(n).
Bây giờ ta chứng tỏ không có 2 số ar
j
, ar
k
(j = k) nào đồng dư nhau
modulo n. Giả sử ar ≡ ar
k
(mod n), với j = k và 1 ≤ j ≤ ϕ(n);
1 ≤ k ≤ ϕ(n). Vì (a, n) = 1 nên ta suy ra r
j
≡ r
k
(mod n). Điều này mâu
thuẫn vì r
j
, r
k
cùng thuộc hệ thặng dư thu gọn ban đầu modulo n. ✷
Chứng minh định lý.
Giả sử r
1
, r
2
, , r
ϕ(m)

là một hệ thặng dư thu gọn gồm các số nguyên
không vượt quá m và nguyên tố cùng nhau với m. Theo Bổ đề 1.6 và do
(a, m) = 1, tập hơp ar
1
, ar
2
, , ar
ϕ(m)
cũng là một hệ thặng dư thu gọn
modulo m. Như vậy, các thăng dư bé nhất ar
1
, ar
2
, , ar
ϕ(m)
phải là số
nguyên r
1
, r
2
, , r
ϕ(m)
xếp theo thứ tự nao đó. Vì thế, nếu ta nhân các
hạng tử trong hệ thu gọn trên, ta được
ar
1
.ar
2
ar
ϕ(m)

≡ r
1
.r
2
r
ϕ(m)
(mod m).
Do đó
a
ϕ(m)
.r
1
.r
2
r
ϕ(m)
≡ r
1
.r
2
r
ϕ(m)
(mod m).
Vì (r
1
.r
2
r
ϕ(m)
, m) = 1. nên a

ϕ(m)
≡ 1 (mod m). ✷
Định lý 1.17 (Định lý Trung Quốc về phần dư). Giả sử m
1
, m
2
, , m
r
là
các số nguyên tố cùng nhau từng cặp. Khi đó hệ các đồng dư tuyến tính
23
x ≡ a
1
(mod m
1
)
x ≡ a
2
(mod m
2
)

x ≡ a
r
(mod m
r
)
có nghiệm duy nhất modulo M = m
1
m

2
m
r
.
Chứng minh.
Trước tiên, ta xây dựng một nghiệm của hệ đồng dư tuyến tính trên. Đặt
M
k
=
M
m
k
= m
1
m
2
m
k−1
m
k+1
m
r
.
Vì (m
k
, m
j
) = 1 với k = j nên (M
k
, m

k
) = 1. Do đó, tồn tại nghịch đảo
y
k
của m
k
modulo m
k
M
k
y
k
≡ 1 (mod m
k
).
Lập tổng
x = a
1
M
1
y
1
+ a
2
M
2
y
2
+ + a
r

M
r
y
r
.
Khi đó, x sẽ là nghiệm của hệ đồng dư x ≡ a
j
(mod m
j
), j = 1, , r. Thật
vậy, ta có m
j
| M
k
khi j = k nên M
j
≡ 0(mod m
k
), j = k. Từ đó suy ra
x ≡ a
k
M
k
y
k
(mod m
k
).
Do M
k

y
k
≡ 1 (mod m
k
) nên x ≡ a
k
(mod m
k
). Bây giờ ta sẽ chỉ ra rằng,
hai nghiệm tùy ý của hệ sẽ đồng dư nhau modulo M. Giả sử x
0
, x
1
là hai
nghiệm của hệ r đồng dư đang xét. Khi đó với mỗi k, x
0
≡ x
1
≡ a
k
(mod
m
k
). Do đó m
k
| (x
0
− x
1
). Từ đó suy ra x

0
≡ x
1
(mod M). Vậy hệ đồng
dư đang xét có nghiệm duy nhất modulo M. ✷
24
Chương 2
Áp dụng giải một số bài toán sơ cấp
Chương này trình bày một số bài toán, ứng dụng các định lý ở chương
1 để giải. Các bài toán này được tổng hợp từ tài liệu tham khảo [1] [4] [5]
2.1 Ứng dụng Định lý Dirichlet về cấp số cộng
Bài toán 2.1. Chứng minh rằng, tồn tại cấp số cộng với độ dài bất kỳ,
thành lập từ các số nguyên tố cùng nhau từng đôi.
Lời giải.
Giả sử m > 1 cho trước. Khi đó dãy x
k
= m!k + 1, k = 1, , m là cấp số
cộng với công sai m!. Bây giờ ta chứng minh dãy x
n
đôi một nguyên tố
cùng nhau.
Giả sử k < l ≤ m, giả sử (x
k
, x
l
) = d, ta có m > l − k = l(m!k + 1) −
k(m!l + 1)
.
.
. d, suy ra m!

.
.
. d suy ra m!k
.
.
. d, theo trên thì m!k + 1
.
.
. d,
mà (m!k, m!k + 1) = 1, suy ra 1
.
.
. d, vậy d = 1. ✷
Bài toán 2.2. Có tồn tại hay không một dãy số vô hạn các số chính
phương lập thành một cấp số cộng.
Lời giải.
Giả thiết rằng tồn tại một cấp số cộng vô hạn a
2
1
, a
2
2
, a
2
3
, trong đó a
1
<
a
2

< a
3
< là dãy vô hạn các số tự nhiên. Hiển nhiên ta có a
2
3
− a
2
2
=
a
2
2
− a
2
1
⇔ (a
3
+ a
2
)(a
3
− a
2
) = (a
2
+ a
1
)(a
2
− a

1
). Do a
3
+ a
2
> a
2
+ a
1
nên ta suy ra a
3
− a
2
< a
2
− a
1
. Tiếp tục lý luận như vậy ta có dãy số
tự nhiên sau: a
2
−a
1
, a
3
−a
2
, a
4
−a
3

, , a
k
−a
k−1
Đó là một dãy số tự
nhiên vô hạn giảm dần, trong đó a
k
− a
k−1
> 1 với mọi k. Đây là điều vô
lý.
Vậy giả thiết phản chứng là sai, tức là không tồn tại dãy vô hạn các số
chính phương lập thành cấp số cộng. ✷