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

TRẦN THỊ THÙY LINH

LÝ THUYẾT ĐỒNG DƯ VÀ ỨNG DỤNG
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Đại số

HÀ NỘI – 2018


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

TRẦN THỊ THÙY LINH

LÝ THUYẾT ĐỒNG DƯ VÀ ỨNG DỤNG
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

HÀ NỘI – 2018


Lời cảm ơn
Em xin bày tỏ lòng cảm ơn tới các Thầy Cô khoa Toán, trường Đại

Học Sư Phạm Hà Nội 2 đã tận tình truyền đạt những tri thức quý
báu và tạo điều kiện thuận lợi để em hoàn thành tốt việc học và làm
khóa luận.
Đặc biệt, em xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc tới
TS. Nguyễn Thị Kiều Nga, người đã trực tiếp hướng dẫn, chỉ bảo tận
tình để em có thể hoàn thành khóa luận này.
Do thời gian, năng lực và điều kiện bản thân còn hạn chế nên bản
khóa luận không thể tránh khỏi những thiếu sót. Em rất mong nhận
được những ý kiến góp ý quý báu của các Thầy Cô và các bạn sinh
viên.
Em xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2018
Sinh viên

Trần Thị Thùy Linh

1


Lời cam đoan

Em xin cam đoan khóa luận "Lý thuyết đồng dư và ứng dụng" là
công trình nghiên cứu của riêng em dưới sự hướng dẫn của TS. Nguyễn
Thị Kiều Nga. Các nội dung nghiên cứu trong khóa luận là hoàn toàn
trung thực và có sử dụng một số tài liệu trong danh mục tài liệu tham
khảo. Em xin hoàn toàn chịu trách nhiệm về khóa luận của mình.
Hà Nội, tháng 5 năm 2018
Sinh viên

Trần Thị Thùy Linh


2


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

3

1.1.1

Định nghĩa . . . . . . . . . . . . . . . . . . . .


3

1.1.2

Tính chất . . . . . . . . . . . . . . . . . . . . .

3

Các định lý Euler, Fermat, Wilson

. . . . . . . . . . .

5

1.2.1

Hàm Euler . . . . . . . . . . . . . . . . . . . . .

5

1.2.2

Tính chất . . . . . . . . . . . . . . . . . . . . .

5

1.2.3

Định lý Euler, định lý Fermat, định lý Wilson .


6

Các lớp thặng dư . . . . . . . . . . . . . . . . . . . . .

6

1.3.1

Tập hợp các lớp thặng dư môđun . . . . . . . .

6

1.3.2

Vành các lớp thặng dư . . . . . . . . . . . . . .

7

1.3.3

Hệ thặng dư . . . . . . . . . . . . . . . . . . . .

8

Phương trình và hệ phương trình đồng dư . . . . . . .

10

1.4.1


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

10

1.4.2

Định lý thặng dư Trung Hoa . . . . . . . . . . .

13

1.4.3

Phương trình đồng dư bậc cao . . . . . . . . . .

15

i


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

2 Ứng dụng của lý thuyết đồng dư
2.1

2.2

20


Một số ứng dụng của lý thuyết đồng dư trong Toán học 20
2.1.1

Phát hiện dấu hiệu chia hết . . . . . . . . . . .

20

2.1.2

Xét xem một số có là số chính phương . . . . .

23

2.1.3

Tìm số dư trong phép chia . . . . . . . . . . . .

25

2.1.4

Chứng minh sự chia hết . . . . . . . . . . . . .

27

2.1.5

Giải phương trình, hệ phương trình đồng dư . .


28

2.1.6

Ứng dụng của Định lý thặng dư Trung Hoa . .

30

2.1.7

Bài tập áp dụng . . . . . . . . . . . . . . . . . .

33

Một số ứng dụng của lý thuyết đồng dư trong thực tế .

35

2.2.1

Luật mã số sách ISBN . . . . . . . . . . . . . .

35

2.2.2

Số nhận diện phương tiện (số VIN) . . . . . . .

37


2.2.3

Bài toán mật mã . . . . . . . . . . . . . . . . .

39

Kết luận

43

Tài liệu tham khảo

44

ii


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

Lời mở đầu
Số học là một nội dung quan trọng của toán học xuyên suốt từ
bậc tiểu học đến trung học phổ thông và đại học. Chúng ta được tiếp
xúc với số học bắt đầu bằng những khái niệm đơn giản số tự nhiên,
số nguyên, phân số, tính chia hết, ước chung lớn nhất, bội chung nhỏ
nhất... cho đến những vấn đề đòi hỏi nhiều tư duy hơn như đồng dư,
số nguyên tố, phương trình Diophantine, phương trình đồng dư,...
Đồng dư là khái niệm cơ bản trong lý thuyết số. Khái niệm này
do nhà toán học Đức Gauss (1777-1855), một trong những nhà toán

học lỗi lạc của nhân loại đưa ra. Nó đuợc trình bày trong tác phẩm
"Disquistiones Arthmeticcate" của ông xuất bản năm 1801 khi ông
mới 24 tuổi. Lý thuyết đồng dư được Gauss đưa ra có hệ thống chặt
chẽ và được ứng dụng rộng rãi trong toán, bổ sung giải quyết một số
vấn đề trong số học như: phát hiện dấu hiệu chia hết, tìm dư trong
phép chia,... Đặc biệt lý thuyết đồng dư còn có những ứng dụng quan
trọng trong thực tiễn đời sống.
Được sự gợi ý, động viên và giúp đỡ tận tình của Cô giáo Nguyễn
Thị Kiều Nga cùng sự say mê của bản thân, em đã chọn đề tài "Lý
thuyết đồng dư và ứng dụng" làm đề tài nghiên cứu 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: Ứng dụng của lý thuyết đồng dư
1


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

Chương này trình bày một số ứng dụng của lý thuyết đồng dư trong
toán học, trong thực tiễn đời sống.
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ông tránh khỏi thiếu sót. Em rất mong được sự đóng góp của các
Thầy, Cô giáo và các bạn sinh viên.
Em xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2018
Sinh viên


Trần Thị Thùy Linh

2


Chương 1
Kiến thức chuẩn bị
1.1

Đồng dư thức

1.1.1

Định nghĩa

Định nghĩa 1.1. Cho a, b, m là các số nguyên, m > 0. Số a được gọi
là đồng dư với b theo môđun m nếu a và b chia cho m có cùng số dư.
Kí hiệu: a ≡ b (mod m). Ngược lại kí hiệu: a ≡ b(mod m).
Chú ý.
• a ≡ b (mod m) khi và chỉ khi m|(a − b).
• a ≡ b (mod m) khi và chỉ khi tồn tại số nguyên k sao cho a = b+km.
1.1.2

Tính chất

a) Quan hệ đồng dư là quan hệ tương đương trên tập số nguyên Z.
b) Ta có thể cộng, trừ từng vế nhiều đồng dư thức theo cùng một
môđun, tức là nếu ai ≡ bi (mod m), i = 1, k thì:
k


k

ai .εi ≡
i=1

bi .εi (mod m) với εi = ±1 với mọi i = 1, k.
i=1

3


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

c) Ta có thể nhân từng vế nhiều đồng dư thức theo cùng một môđun,
tức là nếu ai ≡ bi (mod m), i = 1, k thì:
k

k

ai ≡
i=1

bi (mod m)
i=1

d) Hệ quả
- Nếu a ≡ b (mod m) thì a ± c ≡ b ± c (mod m).

- Nếu a ≡ b (mod m) thì ac ≡ bc (mod m).
- Nếu a ≡ b (mod m) thì a ≡ b + km (mod m).
- Nếu a + c ≡ b (mod m) thì a ≡ b − c (mod m)
- Nếu a ≡ b (mod m) thì an ≡ bn (mod m) với n là số nguyên dương.
e) Giả sử f (x) ∈ Z[x] và a ≡ b (mod m). Khi đó f (a) ≡ f (b) (mod
m) và f (a) ≡ f (a ± km) (mod m). Đặc biệt f (a) ≡ 0 (mod m) thì
f (a ± km) ≡ 0 (mod m).
f ) Ta có thể chia cả hai vế của một đồng dư thức cho một ước chung
nguyên tố với môđun, tức là nếu ac ≡ bc (mod m) và (c, m)=1 thì
a ≡ b (mod m).
m
).
d
g) - Ta có thể nhân cả hai vế và môđun của đồng dư thức với cùng

Trường hợp: ac ≡ bc (mod m) và (c, m) = d thì a ≡ b (mod

một số nguyên dương, tức là nếu a ≡ b (mod m) thì ac ≡ bc (mod
mc), ∀c ∈ Z+ .
- Ta có thể chia cả hai vế và môđun của đồng dư thức với cùng một
ước dương của chúng, tức là nếu a ≡ b (mod m), 0 < c, c là ước chung
a b
m
của a, b, m thì = (mod ).
c
c
c
h) Nếu a ≡ b (mod m1 ), a ≡ b (mod m2 ), ..., a ≡ b (mod mk ) thì
a ≡ b (mod [m1 , ..., mk ]).
4



Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

Đặc biệt: Nếu a ≡ b (mod m1 ), a ≡ b (mod m2 ), ..., a ≡ b (mod mk )
với m1 , ..., mk đôi một nguyên tố. Khi đó a ≡ b (mod m1 m2 ...mk ).
i) Nếu hai số đồng dư với nhau theo môđun m thì chúng cùng đồng
dư với nhau theo mọi môđun là ước của m, tức là nếu a ≡ b (mod m)
và c > 0, c|m thì a ≡ b (mod c)
k) Nếu hai số a, b đồng dư với nhau theo môđun m thì tập hợp các
ước chung của a và m trùng với tập hợp các ước chung của b và m và
(a, m) = (b, m).
Sau đây ta nhắc lại ba định lý nổi tiếng của số học liên quan đến đồng
dư thức.

1.2
1.2.1

Các định lý Euler, Fermat, Wilson
Hàm Euler

Định nghĩa 1.2. Cho n là số nguyên dương. Hàm Euler ϕ(n) là số
các số nguyên dương không vượt quá n và nguyên tố cùng nhau với
n, tức ϕ(n) = |{a ∈ N|0 ≤ a < n, (a, n) = 1}|.
Ví dụ: Với n = 4 thì ϕ(4) = 2. Nếu p là số nguyên tố thì ϕ(p) = p−1.
1.2.2

Tính chất


a) Hàm Euler có tích chất nhân, nghĩa là ϕ(mn) = ϕ(m).ϕ(n) với mọi
m, n ∈ N mà (m, n) = 1.
Từ tính chất nhân tính của hàm Euler, ta có các tính chất sau:

5


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

b) Cho p nguyên tố, α là số tự nhiên, α > 0 thì:
1
ϕ(pα ) = pα .(1 − )
p
c) (Công thức tính hàm Euler). Nếu số nguyên n ≥ 2 có sự phân tích
tiêu chuẩn n = pα1 1 pα2 2 ...pαk k thì
ϕ = p1α1 −1 (p1 − 1)pα2 2 −1 (p2 − 1) · · · pαk k −1 (pk − 1) hay
1
1
1
ϕ(n) = n(1 − )(1 − )...(1 − )
p1
p2
pk
1.2.3

Định lý Euler, định lý Fermat, định lý Wilson


Định lý 1.1. (Định lý Euler) Cho m là số nguyên dương và a là số
nguyên với (a, m) = 1. Khi đó, aϕ(m) ≡ 1 (mod m).
Định lý 1.2. (Định lý Fermat) Cho p là số nguyên tố và a là số
nguyên tùy ý thì ap ≡ a (mod p).
Định lý 1.3. (Định lý Wilson) Số nguyên p > 1 là số nguyên tố khi
và chỉ khi (p − 1)! +1 chia hết cho p hay (p − 1)! ≡ −1 (mod p).

1.3
1.3.1

Các lớp thặng dư
Tập hợp các lớp thặng dư môđun

Định nghĩa 1.3. Tập thương của tập số nguyên Z trên quan hệ đồng
dư môđun m được gọi là tập các lớp thặng dư môđun m(m ∈ N∗ ) và
kí hiệu Zm . Mỗi phần tử của Zm được gọi là một lớp thặng dư môđun
m. Ứng với mỗi A ∈ Zm , tồn tại a ∈ Z, để ta có A = a. Với a ∈ Zm

6


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

thì a được gọi là đại diện của lớp thặng dư a hay còn gọi là một thặng
dư môđun m.
Chú ý.
• b ∈ a (mod m) khi và chỉ khi b ≡ a (mod m) khi và chỉ khi b = a
•b∈

/ a (mod m) khi và chỉ khi b ≡ a (mod m) khi và chỉ khi b ∩ a = ∅.
Tính chất của tập hợp các lớp thặng dư
a) Tập Zm có m phần tử phân biệt Zm = 0, 1, ..., m − 1 .
b) Nếu n = md thì lớp thặng dư a = a + mZ là hợp của d lớp thặng
dư môđun m tức a + mZ =

d
k=0 (a

+ km + nZ).

c) Ước chung lớn nhất của mỗi thặng dư của một lớp môđun chỉ phụ
thuộc vào lớp đó, cụ thể là nếu a, b là hai số nguyên tùy ý của lớp
A(mod m) thì (a, m) = (b, m).
Định nghĩa 1.4. Ta gọi ước chung lớn nhất của một lớp A với môđun
m là ước chung lớn nhất của mỗi thặng dư của A với môđun m và ta
cũng kí hiệu là d = (A, m) = (a, m) = (a, m) với A = a(modm).
Đặc biệt, nếu (A, m) = 1 thì A gọi là lớp thặng dư nguyên tố với
môđun.
1.3.2

Vành các lớp thặng dư

Trong Zm ta định nghĩa hai phép toán cộng và nhân như sau: Giả sử
a, b ∈ Zm . Ta có
a
¯ + ¯b = a + b
a
¯.¯b = ab


7


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

Dễ kiểm tra được rằng các phép toán trên là phép toán hai ngôi trên
Zm .
Định lý 1.4. Tập hợp Zm cùng với phép cộng và nhân xác định ở
trên là một vành giao hoán có đơn vị.
Chứng minh. Dễ kiểm tra được rằng phép cộng và phép nhân trong
Zm thỏa mãn các điều kiện của vành giao hoán. Phần tử không của
Zm là 0 := 0, phần tử đối của a là −a, phần tử đơn vị của Zm là 1.
1.3.3

Hệ thặng dư

1.3.3.1

Hệ thặng dư đầy đủ

Định nghĩa 1.5. Cho tập A = {a1 , a2 , . . . , am }. Giả sử ri , 0 ≤ ri ≤
m − 1 là số dư khi chia ai cho m. Nếu tập số dư {r1 , r2 , . . . , rm } trùng
với tập {0, 1, 2, . . . , m − 1} thì ta nói A là một hệ thặng dư đầy đủ
môđun m.
Nhận xét. Từ định nghĩa, dễ thấy:
• Nếu A = {a1 , a2 , . . . , am } lập thành một hệ thặng dư đầy đủ
môđun m khi và chỉ khi nếu i = j thì ai ≡ aj (mod m).
• Nếu A = {a1 , a2 , . . . , am } là hệ thặng dư đầy đủ môđun m thì từ

định nghĩa dễ dàng suy ra:
– Với mọi n ∈ Z, tồn tại duy nhất ai ∈ A sao cho ai ≡
n(mod m).
– Với mọi a ∈ Z, tập a + A = {a + a1 , a + a2 , . . . , a + am } là
một hệ đầy đủ môđun m.
8


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

– Với mọi c ∈ Z và (c, m) = 1, tập cA = {ca1 , ca2 , . . . , cam } là
một hệ đầy môđun m.
– Tập A∗ = {0, 1, 2, 3, . . . , m − 1} là một hệ thặng dư đầy đủ
môđun m không âm nhỏ nhất.
– Số phần tử của tập A là m.
1.3.3.2

Hệ thặng dư rút gọn

Định nghĩa 1.6. Cho tập B = {b1 , b2 , · · · , bk } là một tập hợp gồm k
số nguyên và (bi , m) = 1 với mọi i − 1, k.
Giả sử bi = qi m + ri với 1 ≤ ri < m. Khi đó dễ thấy (ri , m) = 1.
Nếu tập {r− 1, r2 , · · · , rm } bằng tập K gồm tất cả các số nguyên dương
nhỏ hơn m và nguyên tố cùng nhau với m thì B được gọi là hệ thặng
dư thu gọn môđun m, gọi tắt là hệ thu gọn (môđun m).
Nhận xét. Ta có thể rút ra hai nhận xét:
• Dễ thấy tập hợp B = {b1 , b2 , · · · , bk } gồm k số nguyên lập thành
một hệ thu gọn khi và chỉ khi

– (bi , m) = 1
– bi ≡ bj (mod m) với 1 ≤ i = j ≤ k
– Với mỗi x ∈ Z, (x, m) = 1 tồn tại duy nhất bi ∈ B sao cho
xi ≡ bi (mod m).
• Từ định nghĩa suy ra cho tập B = {b1 , b2 , · · · , bk } là hệ thu gọn
môđun m và c ∈ Z, (c, m) = 1 thì tập cB = {cb1 , cb2 , · · · , cbk }
cũng là một hệ thu gọn môđun m.

9


Khóa luận tốt nghiệp Đại học

1.4
1.4.1

Trần Thị Thùy Linh

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

1.4.1.1

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

Định nghĩa 1.7. Phương trình đồng dư bậc nhất một ẩn là một đồng
dư thức dạng ax ≡ b(mod m) (1), với a không chia hết cho m.
Định lý 1.5. (Điều kiện có nghiệm và số nghiệm) Phương trình (1)
có nghiệm khi và chỉ khi UCLN d = (a, m) của a và m là ước của b.

Khi (1) có nghiệm thì nó có d nghiệm.
Chứng minh. Ta có thể giả thiết d > 0.
- Giả sử (1) có nghiệm. Khi đó tồn tại x0 ∈ Z sao cho 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 ta có d|b.
- Giả sử ngược lại (a, m) = d|b. Giả sử a = a1 d, b = b1 d, 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 , khi đó a1 x cũng chạy qua một hệ thặng dư đầy đủ
môđun m1 , cho nên có một hệ 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 (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)
10


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

là x0 , x0 + m1 , · · · , x0 + (d − 1)m1 (mod m). Vậy phương trình (1) có
nghiệm và có d nghiệm.
Phương pháp chung để giải:
Để xác định nghiệm ta chỉ xét phương trình ax ≡ b(mod m) (1) với
điều kiện a, m nguyên tố cùng nhau và ta có thể giả thiết 1 < a < m.
• Xác định nghiệm bằng phép chia cho a. Nếu a là ước của b thì
b
nghiệm của phương trình (1) là x ≡ (mod m). Nếu a không chia

a
hết cho b tồn tại k với 1 ≤ k ≤ a − 1 sao cho a chia hết b + km.
Khi đó (1) tương đương với phương trình
ax ≡ b + km(mod m)
b + km
(mod m). Cách này thường chỉ
a
sử dụng khi a tương đối nhỏ.

và ta được nghiệm là x ≡

• Sử dụng Định lí Euler. Vì (a, m) = 1 nên ta có aϕ(m) ≡ 1(mod m).
Do đó ta có aϕ(m) b ≡ b(mod m).
Vậy x ≡ aϕ(m)−1 b(mod m) là nghiệm của phương trình (1).
1.4.1.2

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

Định nghĩa 1.8. Hệ phương trình đồng dư bậc nhất một ẩn là hệ
phương trình có dạng

(∗)




x ≡ b1 (mod m1 )







x ≡ b2 (mod m2 )



···





x ≡ b (mod m )
k
k
11


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

với m1 , · · · , mk là những số nguyên lớn hơn 1 và b1 , · · · , bk là những
số nguyên tùy ý.
Nhận xét.
Trong trường hợp tổng quát, chúng ta có thể chứng minh được rằng:
Điều kiện cần và đủ để hệ phương trình (∗) có nghiệm là U CLN (mi ; mj )
chia hết bi − bj với i = j(1 ≤ i, j ≤ k)
Phương pháp chung để giải:

• Trường hợp 1: Hệ 2 phương trình


x ≡ b1 (mod m1 )

x ≡ b2 (mod m2 )
Với giả thiết d = (m1 , m2 ) chia hết cho b1 − b2 . Trước tiên ta nhận
xét rằng, mọi số z = b1 + m1 t, t ∈ Z là nghiệm của hệ phương
trình thứ nhất. Sau đó ta tìm cách xác định t sao cho x nghiệm
đúng phương trình thứ hai, nghĩa là hệ hai phương trình trên
tương đương với hệ phương trình


x = b1 + m1 t

b1 + m1 t ≡ b2 (mod m2 )
Vì giả thiết d = (m1 , m2 ) là ước b1 −b2 nên phương trình b1 +m1 t ≡
b2 (mod m2 ) tương đương với phương trình:
m1
b2 − b1
m2
t=
(mod
)
d
d
d
Nhưng (

m1 m2

,
) = 1 nên phương trình đồng dư này cho ta
d d
12


Khóa luận tốt nghiệp Đại học

nghiệm t ≡ t0 (mod

Trần Thị Thùy Linh

m2
), là tập hợp tất cả các số nguyên
d
t = t0 +

m2
u, u ∈ Z
d

Thay biểu thức của t vào biểu thức x ta được tập hợp các giá trị
của x nghiệm đúng cả hai phương trình đồng dư đang xét là:
x = b1 + m1 (t0 +

m2
m1 m2
u) = b1 + m1 t0 +
u, hayx = x0 + mu
d

d

với x0 = b1 + m1 t0 , m = BCN N (m1 , m2 ).
Vậy x ≡ x0 (mod m) là nghiệm của hệ hai phương trình đồng dư
đang xét.
• Trường hợp 2: Hệ gồm n phương trình. Đầu tiên giải hệ hai
phương trình nào đó của hệ đã cho, rồi thay trong hệ hai phương
trình nào đó của hệ đã cho, 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ẽ giải được nghiệm cần tìm.
1.4.2

Định lý thặng dư Trung Hoa

Định lý 1.6. Cho m1 , m2 , · · · , mn là các số nguyên dương đôi một
nguyên tố cùng nhau và r1 , r2 , · · · , rn là các số nguyên bất kì. Khi đó

13


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

hệ phương trình đồng dư



x ≡ r1 (mod m1 )







x ≡ r2 (mod m2 )

..


.





x ≡ r (mod m )
n
n
có nghiệm duy nhất môđun m = m1 m2 ...mn .
Chứng minh. -Sự tồn tại nghiệm.
m
Đặt si =
. Do m1 , m2 , · · · , mn n là các số nguyên dương đôi một
mi
nguyên tố cùng nhau nên ta có (si , mi ) = 1 với mọi i = 1, 2, · · · , n. Do
đó với mỗi i, , tồn tại một số nguyên si thỏa mãn si si ≡ 1(mod mi ).
Đặt
x0 = s1 s1 r1 + s2 s2 r2 + · · · + sn sn rn .

Vì sj chia hết cho mi nếu j = i nên x0 ≡ si si ri ≡ ri (mod mi ) với mọi
1 ≤ i ≤ n. Tức là hệ phương trình đồng dư đã cho có nghiệm.
- Tính duy nhất. Giả sử hệ phương trình đồng dư trên có nghiệm
khác x1 . Khi đó ta có x1 − x0 ≡ 0(mod mi ) hay x1 − x0 chia hết cho
mi với mọi i = 1, 2, · · · , n. Do m1 , m2 , · · · , mn là các số nguyên đôi
một nguyên tố cùng nhau nên từ đó suy ra x1 − x0 chia hết cho m =
m1 m2 · · · mn . Hay x1 ≡ x0 (mod m). Định lí được chứng minh.
Nhận xét. Định lí thặng dư Trung Hoa khẳng định sự tồn tại duy nhất
nghiệm của hệ phương trình đồng dư bậc nhất. Do đó có thể sử dụng
định lí để giải quyết các bài toán về sự tồn tại và đếm các số nguyên
thỏa mãn một hệ các điều kiện quan hệ đồng dư, chia hết...hay đếm
14


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

số nghiệm của một phương trình đồng dư. Việc sử dụng hợp lí các
bộ m1 , m2 , · · · , mn và bộ r1 , r2 , · · · , rn (trong định lí) cho ta nhiều kết
quả thú vị và từ đó có thể giải được nhiều bài tập hay và khó.
1.4.3

Phương trình đồng dư bậc cao

Xét phương trình f (x) ≡ 0(mod m) với f (x) ∈ Z[x]. Giả sử m có sự
k

n2
n

phân tích tiêu chuẩn là m = pn1
1 p2 · · · pk . Khi đó phương trình trên

tương đương với hệ f (x) ≡ 0(mod pni
i ), với i = 1, 2, · · · , k. Vì vậy
việc giải phương trình trên đưa về việc giải phương trình dạng f (x) ≡
0(mod pn ) trong đó p là số nguyên tố và n > 1. Chú ý rằng nếu một
i

trong các phương trình của hệ f (x) ≡ 0(mod pni ), với i = 1, 2, · · · , k
mà không có nghiệm thì cả hệ không có nghiệm và do đó phương trình
f (x) ≡ 0(mod m) không có nghiệm. Còn nếu mỗi phương trình f (x) ≡
i

i

0(mod pni ), có si nghiệm, i = 1, 2, · · · , k thì hệ f (x) ≡ 0(mod pni ), với
i = 1, 2, · · · , k hay phương trình f (x) ≡ 0(mod m) sẽ có s = s1 s2 · · · sk
nghiệm.
1.4.3.1 Phương trình f (x) ≡ 0(mod pk ) (trong đó p nguyên
tố và k > 1 và f (x) có bậc n)
Bổ đề 1.1. Nếu x = x0 nghiệm đúng phương trình f (x) ≡ 0(mod pk )(1)
và n > 1 thì x = x0 cũng nghiệm đúng phương trình f (x) ≡ 0(mod ps )
với mọi s = 1, 2, · · · , n − 1.
Điều này là hiển nhiên. Như vậy có nghĩa mỗi nghiệm của phương
trình (1) là một bộ phận của một nghiệm nào đó của phương trình
f (x) ≡ 0(mod ps ) với 1 ≤ 6s < n. Kết quả này cho phép ta tìm

15



Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

nghiệm của phương trình (1) chỉ trong các nghiệm của phương trình
f (x) ≡ 0(mod p).
Định lý 1.7. Giả sử x ≡ x0 (mod pn−1 )(n > 1) là một nghiệm của
phương trình f (x) ≡ 0(mod pn−1 )(2) và gọi f (x) là đạo hàm của f (x),
khi đó:
i) Nếu f (x) không đồng dư với 0 theo (mod p) thì trong lớp thặng dư
x ≡ x0 (mod pn−1 ) có một và chỉ một nghiệm của phương trình (1).
ii) Nếu f (x) ≡ 0(mod p) thì trong lớp thặng dư x ≡ x0 (mod pn−1 )
hoặc có p nghiệm, hoặc không có nghiệm nào của phương trình (1)
f (x0 )
tùy theo n−1 có chia hết cho p hay không.
p
Chứng minh. Đặt x = x0 +tpn với t ∈ Z, đó là các số của lớp thặng dư
x0 (mod pn−1 ). Ta hãy xét xem trong các số này, những số nào nghiệm
đúng phương trình (1). Điều này xảy ra khi và chỉ khi t nghiệm đúng
phương trình f (x0 + tpn − 1) ≡ 0(mod pn )(3). Áp dụng công thức
Taylor, ta được khai triển của f (x0 + tpn−1 ) theo lũy thừa tăng của t
là:
n−1

f (x0 +tp

n−1

) = f (x0 )+tp


2 2(n−1) f

f (x0 )+t p

k
(x0 )
k k(n−1) f (x0 )
+· · ·+t p
2!
n!

Từ đó phương trình (3) tương đương với phương trình
f (x0 ) + tpn−1 f (x0 ) ≡ 0(mod pn )
vì các số hạng bỏ đi đều là bội của pn vì các số hạng bỏ đi đều là bội
của pn . Vì f (x0 ) ≡ 0(mod pn−1 ) nên ta có thể chia hai vế và môđun
của phương trình này cho pn−1 , ta được phương trình (3) tương đương
16


Khóa luận tốt nghiệp Đại học

Trần Thị Thùy Linh

với
f (x0 )
+ tf (x0 ) ≡ 0(mod p)
pn−1

(4)


i) Nếu f (x0 ) không đồng dư với 0 theo mô đun p thì phương trình
(4) có nghiệm duy nhất, giả sử là t ≡ t0 (mod p), hay t = t0 + pu với
u ∈ Z. Nó cho ta trong lớp nghiệm x ≡ x0 (mod pn−1 ) của phương
trình (2) một nghiệm duy nhất
x = x0 + t0 pn−1 + upn , u ∈ Z
hay
x ≡ x0 + t0 pn−1 (mod pn )
của phương trình (1).
f (x0 )
không đồng dư với 0 theo môđun
pn−1
p thì phương trình (4) không có nghiệm, điều đó kéo theo là trong lớp
ii) Nếu f (x0 ) ≡ 0(mod p) và

x0 (mod pn−1 ) nghiệm của phương trình (2) không có nghiệm nào của
phương trình (1). Nếu f (x0 ) ≡ 0(mod p) và f (x0 )pn−1 ≡ 0(mod p)
thì phương trình (4) nghiệm đúng với mọi t ∈ Z(nghĩa là (4) có p
nghiệm.) Do đó mọi số của lớp x0 (mod pn−1 ) nghiệm của (2) đều
nghiệm đúng phương trình (1), nó cho ta p nghiệm của phương trình
(1) là x0 , x0 + pn−1 , ..., x0 + (p − 1)pn−1 (mod pn ). Do đó ta có điều phải
chứng minh.
Hệ quả 1.1. Nếu x ≡ x0 (mod p) là một nghiệm của phương trình
f (x) ≡ 0(modp) (5) mà f (x0 ) không đồng dư với 0 theo môđun p, thì
trong nghiệm này có một nghiệm duy nhất của phương trình (1).

17


Khóa luận tốt nghiệp Đại học


1.4.3.2

Trần Thị Thùy Linh

Phương trình đồng dư theo môđun nguyên tố

Định nghĩa 1.9. Phương trình đồng dư theo môđun nguyên tố là
phương trình có dạng f (x) ≡ 0(mod p) (1) trong đó p là một số
nguyên tố và f (x) = a0 xn + a1 xn−1 + · · · + an là một đa thức bậc n
với hệ số nguyên.
Định lý 1.8. Phương trình (1) hoặc nghiệm đúng với mọi x ∈ Z hoặc
tương đương với một phương trình có bậc không lớn hơn p − 1.
Chứng minh. Chia f (x) cho xp − x, giả sử ta được
f (x) = (xp − x)q(x) + r(x)
trong đó r(x) là đa thức không hoặc có bậc không lớn hơn p − 1.
Phương trình (1) trở thành
(xp − x)q(x) + r(x) ≡ 0(mod p).
Do với mọi x ∈ Z ta đều có xp − x ≡ 0(mod p) nên phương trình
(1) tương đương với phương trình r(x) ≡ 0(mod p) và điều đó chứng
minh mệnh đề trên.
Định lý 1.9. Nếu phương trình (1), với n < p có quá n nghiệm phân
biệt thì tất cả các hệ số a0 , a1 , · · · , an của f (x) đều là bội của p.
Chứng minh. Giả sử phương trình (1) có n + 1 nghiệm là
x ≡ x0 , x1 , · · · , xn (mod p)

18


Khóa luận tốt nghiệp Đại học


Trần Thị Thùy Linh

Ta hãy xác định các hệ số b0 , b1 , · · · , bn sao cho ta có khai triển
f (x) = a0 xn + a1 xn−1 + · · · + an
= b0 (x − x1 )(x − x2 ) · · · (x − xn ) + b1 (x − x1 )(x − x2 ) · · · (x − xn−1 )
+ · · · + bn−1 (x − x1 ) + bn.
Việc này được thực hiện bằng cách đồng nhất hóa hai vế, và ta có
kết quả là mỗi bi là tổ hợp tuyến tính nguyên của các aj , j ≤ i, và
ngược lại mỗi ai cũng là tổ hợp tuyến tính nguyên của các bj , j ≤ i.
Ta có f (x1 ) = bn . Vì x ≡ x1 (mod p) là một nghiệm của phương trình
(1) cho nên bn ≡ 0(mod p). Ta lại có f (x2 ) = bn−1 (x2 − x1 ) + bn .
Mặt khác vì x ≡ x2 (mod p) là nghiệm của phương trình (1) nên ta có
bn−1 (x2 −x1 )+bn ≡ 0(mod p). Từ đó ta có bn−1 (x2 −x1 ) ≡ 0(mod p). Vì
x2 , x1 thuộc các lớp thặng dư môđun p khác nhau nên (x2 − x1 , p) = 1.
Do đó ta được bn−1 ≡ 0(mod p). Bằng cách lập luận như vậy với
các giá trị f (x1 ), f (x2 ), · · · , f (xn ) và f (x0 ), ta được tất cả các hệ số
bn , bn−1 , · · · , b0 đều là bội của p. Vì ai là những tổ hợp tuyến tính
nguyên của bj , j ≤ i, nên với mọi ai , i = 0, 1, · · · , n đều là bội của
p.
Hệ quả 1.2. Một phương trình đồng dư bậc n theo môđun nguyên tố
p, với n < p có không quá n nghiệm.

19