TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
======

HOÀNG THỊ THÚY HƯỜNG

VỀ ĐỊNH LÝ THẶNG DƯ TRUNG HOA VÀ
ỨNG DỤNG TRONG GIẢI TOÁN SƠ CẤP

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Đại số

HÀ NỘI - 2019


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
======

HOÀNG THỊ THÚY HƯỜNG

VỀ ĐỊNH LÝ THẶNG DƯ TRUNG HOA VÀ
ỨNG DỤNG TRONG GIẢI TOÁN SƠ CẤP

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Đại số

Người hướng dẫn khoa học

TS. Nguyễn Thị Kiều Nga


luận của mình.
Sinh viên

Hoàng Thị Thúy Hường


Mục lục

Lời mở đầu

1

1 Kiến thức chuẩn bị

3

1.1

1.2

1.3

1.4

Đồng dư thức và các tính chất . . . . . . . . . . . . . . . .

3

1.1.1


1.3.1

Định lý Euler . . . . . . . . . . . . . . . . . . . . .

7

1.3.2

Định lý Fermat nhỏ . . . . . . . . . . . . . . . . . .

8

1.3.3

Nghịch đảo môđun . . . . . . . . . . . . . . . . . .

8

Phương trình, hệ phương trình đồng dư bậc nhất một ẩn . .

9

1.4.1

Phương trình đồng dư bậc nhất một ẩn . . . . . . .

9

1.4.2


Phương pháp 3: Chứng minh định lý theo phương
pháp của Knuth . . . . . . . . . . . . . . . . . . . . 19

2.3

Ý nghĩa của định lý thặng dư Trung Hoa . . . . . . . . . . 21

2.4

Ứng dụng của định lý thặng dư Trung Hoa trong giải toán
sơ cấp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.1

Giải phương trình, hệ phương trình đồng dư và các
bài toán liên quan . . . . . . . . . . . . . . . . . . . 21

2.4.2

Chứng minh sự tồn tại của một số nguyên thỏa mãn
điều kiện cho trước . . . . . . . . . . . . . . . . . . 28

2.4.3

Đếm số nghiệm của phương trình đồng dư . . . . . . 42

2.4.4

Ứng dụng vào giải các bài toán chia hết . . . . . . . 47

2.4.5

thặng dư Trung Hoa chúng ta có thể giải quyết được nhiều bài toán hay
và khó trong các kỳ thi học sinh giỏi cấp quốc gia và quốc tế.
Vì lý do trên và với niềm yêu thích môn đại số, em đã chọn đề tài
“Về định lý thặng dư Trung Hoa và ứng dụng trong giải toán sơ cấp ” làm
đề tài khóa luận của mình.
Nội dung khóa luận gồm hai chương:
Chương 1: Kiến thức chuẩn bị
Chương này nhắc lại một số kiến thức cơ bản về lý thuyết đồng dư.
Chương 2: Định lý thặng dư Trung Hoa và ứng dụng trong giải toán
sơ cấp.
Chương này trình bày về định lý thặng dư Trung Hoa và một số ứng dụng

1


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường

của định lý thặng dư Trung Hoa trong việc giải các bài toán sơ cấp.
Do thời gian có hạn và năng lực bản thân còn nhiều hạn chế nên
khóa luận không tránh khỏi những thiếu sót. Em rất mong được sự góp ý
của các Thầy, Cô giáo và các bạn.
Em xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2019
Sinh viên

Hoàng Thị Thúy Hường

2


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường

ii) m | (a − b);
iii) Tồn tại số nguyên t sao cho a = b + mt.

1.1.2

Các tính chất

Cho a, b, c, d là các số nguyên, m ∈ N∗ . Ta có các tính chất sau đây:
1. a ≡ b (mod m) khi và chỉ khi a − b ≡ 0 (mod m).
2. Nếu a ≡ b (mod m) thì b ≡ a (mod m).




a ≡ b (mod m)
3. Nếu
thì a ≡ c (mod m).



b ≡ c (mod m)

4. Nếu



10. Nếu a ≡ b (mod m) và t | a, b, m thì

m
a b
≡ (mod ).
t
t
t

11. Nếu a ≡ b (mod m) và c ∈ Z+ thì ac ≡ bc (mod mc).
4


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường

12. Cho m, n ∈ Z+ , (m, n) = 1 và a, b ∈ Z. 



a ≡ b (mod m)
Khi đó a ≡ b (mod mn) khi và chỉ khi



a ≡ b (mod n)

.


– Với mọi a ∈ Z, tập a + A = {a + a1 , a + a2 , ..., a + an } là hệ
thặng dư đầy đủ môđun n;
– Với mọi c ∈ Z, (c, n) = 1 thì tập cA = {ca1 , ca2 , ..., can } là hệ
thặng dư đầy đủ môđun n;
5


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường

– Số phần tử của A là | A |= n.
Ví dụ:

• Tập A = {0, 1, ..., n − 1} là hệ thặng dư đầy đủ môđun n và được gọi
là hệ thặng dư đầy đủ không âm nhỏ nhất.

n−1 n−1
n−1
,−
+ 1, ...,
là hệ thặng dư đầy đủ
2
2
2
môđun n, gọi là hệ thặng dư đầy đủ với giá trị tuyệt đối nhỏ nhất.

• Nếu n lẻ thì −

• Nếu n chẵn thì hệ thặng dư đầy đủ môđun n với giá trị tuyệt đối nhỏ

i) (bi , n) = 1;
ii) bi ≡ bj (mod n) với 1

i=j

k;

iii) Số phần tử của B là ϕ(n) (với ϕ(n) là số các số nguyên dương
nhỏ hơn hoặc bằng n nguyên tố cùng nhau với n).
Điều kiện iii) tương đương với điều kiện: Với mọi m ∈ Z, (m, n) = 1
thì tồn tại duy nhất bi ∈ B sao cho m ≡ bi (mod n).
6


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường

• Từ định nghĩa suy ra nếu tập B = {b1 , b2 , ..., bk } là hệ thặng dư thu
gọn môđun n và với c ∈ Z, (c, n) = 1 thì cB = {cb1 , cb2 , ..., cbk } là
hệ thặng dư thu gọn môđun n.
Ví dụ: Tập B = {1, 2..., p − 1} là hệ thặng dư thu gọn môđun p không âm
nhỏ nhất, với p là một số nguyên tố.

1.3
1.3.1

Một số định lý quan trọng của Số học
Định lý Euler


Định lý Fermat nhỏ

Định lí 1.3.2 Nếu p là một số nguyên tố và a là số nguyên không chia
hết cho p thì

ap−1 ≡ 1

(mod p).

Hoặc phát biểu dạng tương đương: Cho p là số nguyên tố thế thì với mọi
số nguyên a ta có đồng dư thức: ap ≡ a (mod p).

1.3.3

Nghịch đảo môđun

Định nghĩa 1.3.3 Giả sử a, m là các số nguyên và m > 1. Nghiệm của
phương trình ax ≡ 1 (mod m) được gọi là nghịch đảo môđun m của a.
Định lí 1.3.3 Nghịch đảo môđun m của a tồn tại khi và chỉ khi có điều
kiện (a, m) = 1.
Chứng minh:
Thật vậy, giả sử (a, m) = d > 1 suy ra d | a, d | m. Gọi a là nghịch
đảo môđun m của a suy ra aa ≡ 1 (mod m) nên từ đây ta có aa ≡ 1

(mod d) (∗) mà d | a suy ra aa ≡ 0 (mod d) mâu thuẫn với (∗) cho nên
giả sử sai. Vậy (a, m) = 1.
Ngược lại, ta có (a, m) = 1 nên tồn tại x, y ∈ Z thỏa mãn:

ax + my = 1.
Từ đây ta có ax ≡ 1 (mod m). Do đó x là nghịch đảo môđun m của a.

+ Giả sử (1) có nghiệm, như vậy ta có x0 ∈ Z nghiệm đúng phương trình,
nghĩa là ta có đồng dư thức ax0 ≡ b (mod m). Vì d | a và d | m nên

d | ax0 và d | m do đó theo tính chất của đồng dư thức d | b.
+ Giả sử ngược lại (a, m) = d và d | b.
Đặt a = a1 d, b = b1 d và m = m1 d thì phương trình (1) tương đương với
phương trình: a1 x ≡ b1 (mod m1 ) (2), trong đó (a1 , m1 ) = 1. Cho x
chạy qua một hệ thặng dư đầy đủ môđun m1 , cho nên có một thặng dư
duy nhất x0 trong hệ trên sao cho ta có a1 x0 ≡ b1 (mod m1 ), nghĩa là
phương trình (2) có một nghiệm duy nhất là lớp thặng dư x0 (mod m1 ).
Vì phương trình (2) tương đương với phương trình (1) cho nên lớp x0
9


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường

(mod m1 ) cũng là tập hợp các giá trị của x nghiệm đúng phương trình
(1), lớp này là hợp của d lớp thặng dư môđun m, đó là d nghiệm của
phương trình (1) x0 , x0 + m1 , ..., x0 + (d − 1)m1 (mod m). Vậy phương
trình (1) có nghiệm và có d nghiệm.
Ví dụ 1: Phương trình 18x ≡ 11 (mod 30) không có nghiệm bởi vì

(18, 30) = 6 không là ước của 11.
Ví dụ 2: Phương trình 18x ≡ 12 (mod 30) có nghiệm vì (18, 12) = 6 là
ước của 12, đó là các lớp x ≡ 4, 9, 14, 19, 24, 29 (mod 30).
1.4.1.2 Cách xác định nghiệm
Để xác định nghiệm ta chỉ xét trường hợp phương trình ax ≡ b (mod m)


Vậy x ≡ aϕ(m)−1 b (mod m) là nghiệm của phương trình (1 ).

10


Khóa luận tốt nghiệp

1.4.2

Hoàng Thị Thúy Hường

Hệ phương trình đồng dư bậc nhất một ẩn

Ta xét hệ phương trình bậc nhất một ẩn dạng sau:





x ≡ a1









x ≡ a2

nghiệm.
1.4.2.2 Cách xác định nghiệm
Đầu tiên ta xét trường hợp hệ hai phương trình





x ≡ a1 (mod m1 )



x ≡ a2 (mod m2 )

Với giả thiết d12 = (m1 , m2 ) | a1 − a2 . Từ phương trình thứ nhất ta có thể
đặt x = a1 + m1 t rồi tìm cách xác định t sao cho x cũng là nghiệm đúng
11


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường

phương trình sau, nghĩa là ta có





x = a1 + m1 t

x nghiệm đúng hệ phương trình đang xét là
x = a1 + m1 (t0 +
x = x0 +

m2
u)
d12

m1 m2
u
d12

hay

x = x0 + [m1 , m2 ]u
với mọi số nguyên u, nghĩa là nghiệm của hệ là x ≡ x0 (mod m12 ) với

x0 = a1 + m1 t0 , và m12 = [m1 , m2 ].
Đối với trường hợp một hệ n phương trình (n > 2) thì ta bắt đầu bằng
giải hai phương trình nào đó, rồi thay trong hệ hai phương trình đã giải
bằng nghiệm tìm thấy, ta sẽ được một hệ gồm n − 1 phương trình tương
đương với hệ đã cho. Tiếp tục như vậy sau n − 1 bước ta sẽ được nghiệm
phải tìm.

12


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường


x ≡ 2 (mod 60)

hệ này có

nghiệm là x ≡ 62 (mod 180).

Do đó hệ phương trình đã cho tương đương với hệ





x ≡ 62 (mod 180)



x ≡ 92 (mod 150)

có nghiệm là x ≡ 242 (mod 900). Vậy nghiệm của hệ đã cho là

x ≡ 242

(mod 900).

13


Chương 2
Định lý thặng dư Trung Hoa và ứng





x ≡ a1









x ≡ a2

(mod m1 )
(mod m2 )
(I)





...........................






Xét c = a1 M1 yi + a2 M2 y2 + ... + an Mn yn =
i=1

.
Vì Mi ..mj (∀i = j) nên ta có: ai Mi yi ≡ 0 (mod mj ), ∀i = j (i, j = 1, n).
Do đó c ≡ ai Mi yi (mod mi ), i = 1, n. Mà Mi yi ≡ 1 (mod mi ) nên c ≡ ai
15


Khóa luận tốt nghiệp

Hoàng Thị Thúy Hường

(mod mi ) với mọi i = 1, n tức là c là một nghiệm của hệ phương trình
đồng dư (I).
Vậy ta có x ≡ c (mod mi ), ∀i = 1, n suy ra x ≡ c (mod M ). Vậy hệ (I)
n

ai Mi yi theo môđun M = m1 m2 ...mn .

có tồn tại nghiệm c =
i=1

∗ Chứng minh tính duy nhất nghiệm
Giả sử hệ phương trình (I) có hai nghiệm là c và d. Do đó:






Vì m1 , m2 , ..., mn đôi một nguyên tố cùng nhau nên ta có:

c ≡ d (mod m1 m2 ...mn ) tức là c và d cùng thuộc một lớp thặng dư môđun
M = m1 m2 ...mn .

16


Khóa luận tốt nghiệp

2.2.2

Hoàng Thị Thúy Hường

Phương pháp 2: Chứng minh bằng phương pháp quy
nạp theo n

Ta có hệ phương trình đồng dư:





x ≡ a1










x ≡ a1

(mod m1 ) (1)




x ≡ a2

(mod m2 ) (2)

(II)

Do (m1 , m2 ) = 1 nên tồn tại y1 ∈ Z thỏa mãn: m1 y1 ≡ 1 (mod m2 ). Từ
(1) ta có: x = a1 + m1 t1 (t1 ∈ Z) (1 ) thay vào phương trình (2) ta được:

a1 + m1 t1 ≡ a2 (mod m2 ) suy ra m1 t1 ≡ a2 − a1 (mod m2 ) từ đây ta
có y1 m1 t1 ≡ y1 (a2 − a1 ) (mod m2 ) nên t1 ≡ y1 (a2 − a1 ) (mod m2 ) (vì

m1 y1 ≡ 1 (mod m2 )) suy ra t1 ≡ y1 (a2 − a1 ) + m2 t2 (t2 ∈ Z) thay vào
(1 ) ta được:
x = a1 + m1 [y1 (a2 − a1 ) + m2 t2 ] = a1 + m1 y1 (a2 − a1 ) + m1 m2 t2 (t2 ∈ Z).

17


Khóa luận tốt nghiệp




...........................









x ≡ an−1 (mod mn−1 )
có nghiệm duy nhất theo môđun m = m1 m2 ...mn−1 trong đó m1 , m2 , ...,

mn−1 là n−1 số nguyên dương đôi một nguyên tố cùng nhau và a1 , a2 , ..., an−1
là n − 1 số nguyên bất kì. Giả sử nghiệm đó là x = x0 + mt1 . Ta cần chứng
minh (∗) đúng đến n.
Thật vậy thay x = x0 + mt1 vào phương trình x ≡ xn (mod mn ) ta được

x0 + mt1 ≡ xn

(mod mn )

⇒ mt1 ≡ xn − x0

(mod mn ).

Theo giả thiết ta có m1 , m2 , ..., mn đôi một nguyên tố cùng nhau nên

(mi , ) = 1 và ta cũng có mj | , ∀i, j = 1, n, i = j.
mi
mi
M ϕ(mi )
Đặt Mi = ( )
trong đó ϕ(mi ) là hàm Euler của mi . Vì ta có
mi
M
(mi , ) = 1, ∀i = 1, n. Theo định lý Euler ta có:
mi

Mi = (

M ϕ(mi )
)
≡1
mi

(mod mi )

hay

Mi ≡ 1

(mod mi ), ∀i = 1, n.

Xét x ≡ a1 M1 + a2 M2 + ... + an Mn (mod M ). Từ đây ta có





x ≡ a1 M1 + a2 M2 + ... + an Mn (mod mn )

19