Định lý thặng dư trung hoa

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

nguyÔn h÷u b¹n

®Þnh lý thÆng d­ trung hoa

LUËN V¡N TH¹C SÜ TO¸N HäC

TH¸I NGUY£N - 2014

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN HỮU BẠN

ĐỊNH LÝ THẶNG DƯ TRUNG HOA

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
MÃ SỐ: 60.46.01.13

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

Mục lục
Lời mở đầu

2

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

3

1.1

Định nghĩa đồng dư và các tính chất . . . . . . . . . . . . . . . .

3

1.1.1

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

3

1.1.2

Các tính chất của đồng dư

. . . . . . . . . . . . . . . . .

3

1.2

Một vài định lý cần dùng . . . . . . . . . . . . . . . . . . . . . .

4

1.3

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

5

1.4

Nghịch đảo modulo m . . . . . . . . . . . . . . . . . . . . . . . .

6

2 Định lý Thặng dư Trung Hoa và ứng dụng
2.1

2.2

7

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

7

2.1.1

Một số kết quả bổ trợ . . . . . . . . . . . . . . . . . . . .

7

2.1.2

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

9

2.1.3

Mở rộng định lý Thặng dư Trung Hoa . . . . . . . . . . .

13

Một vài ứng dụng của định lý thặng dư Trung Hoa . . . . . . . .

15

2.2.1

Chứng minh sự tồn tại của một mệnh đề . . . . . . . . .

15

2.2.2

Ứng dụng trong tổ hợp

. . . . . . . . . . . . . . . . . . .

35

2.2.3

Ứng dụng trong đa thức . . . . . . . . . . . . . . . . . . .

36

2.2.4

Tìm số nghiệm nguyên của một phương trình nghiệm nguyên 38

2.2.5

Giải hệ phương trình đồng dư tuyến tính . . . . . . . . .

41

2.2.6

Phân tích các số nguyên lớn . . . . . . . . . . . . . . . . .

44

Kết luận

47

Tài liệu tham khảo

48
1

LỜI MỞ ĐẦU
Trong các kỳ thi chọn học sinh giỏi Quốc gia và Quốc tế, các bài toán về số
học thường đóng vai trò quan trọng. Khi nhắc đến số học hay lý thuyết số, ta
không thể không nhắc tới định lý thặng dư Trung Hoa. Các bài toán sử dụng
định lý này thường là những bài toán hay và khó.
Định lý Thặng dư Trung Hoa là tên người phương Tây đặt cho định lý này.
Người Trung Quốc gọi nó là Bài toán Hàn Tín điểm binh. Tục truyền rằng khi
Hàn Tín điểm quân số, ông cho quân lính xếp hàng 3, hàng 5, hàng 7 rồi báo
cáo số dư. Từ đó, căn cứ vào lượng quân thì ông tính được chính xác quân số
đến từng người.
Luận văn này được chia làm hai chương:
• Chương 1. Kiến thức chuẩn bị
Trong chương này, tác giả trình bày những kết quả đã biết trong số học như
quan hệ đồng dư, hệ đồng dư, các định lý: Fermat, Euler, Wilson, ... Những
kiến thức này sẽ được sử dụng trong việc giải các bài toán trong chương 2.
• Chương 2. Định lý thặng dư Trung Hoa
Nội dung chương này được chia làm hai phần. Phần đầu, tác giả nêu và
chứng minh định lý thặng dư Trung Hoa và định lý thặng dư Trung Hoa dạng
mở rộng. Phần thứ hai, tác giả trình bày những ứng dụng của định lý thặng dư
Trung Hoa vào giải toán.
Luận văn được thực hiện và hoàn thành tại trường Đại học Khoa học - Đại
học Thái Nguyên dưới sự hướng dẫn khoa học của PGS. TS. Nông Quốc Chinh.
Qua đây, tác giả xin được gửi lời cảm ơn sâu sắc đến thầy giáo, người hướng
dẫn khoa học của mình, PGS. TS. Nông Quốc Chinh, người đã đưa ra đề tài và
tận tình hướng dẫn trong suốt quá trình nghiên cứu của tác giả. Đồng thời tác
giả cũng chân thành cảm ơn các thầy cô trong trường Đại học Khoa học, Đại
học Thái Nguyên, đã tạo mọi điều kiện cho tác giả về tài liệu và thủ tục hành
chính để tác giả hoàn thành bản luận văn này. Tác giả cũng gửi lời cảm ơn đến
gia đình, các đồng nghiệp đã động viên giúp đỡ tác giả trong quá trình học tập
và làm luận văn.
Thái Nguyên, ngày 19 tháng 08 năm 2014
Tác giả

2

Chương 1

Kiến thức chuẩn bị
1.1
1.1.1

Định nghĩa đồng dư và các tính chất
Định nghĩa

Định nghĩa 1.1.1. Cho a, b, m là các số nguyên, m khác 0. Nếu a − b chia hết
cho m thì a được gọi là đồng dư với b modulo m, ký hiệu là a ≡ b (mod m).

1.1.2

Các tính chất của đồng dư

Cho a, b, c, d là các số nguyên. Khi đó, ta có các tính chất sau đây
1) Nếu a ≡ b (mod m) thì b ≡ a (mod m).
2) Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m).
3) Nếu a ≡ b (mod m) và c ≡ d (mod m) thì a + c ≡ b + d (mod m).
4) Nếu a ≡ b (mod m) và c ≡ d (mod m) thì ac ≡ bd (mod m).
5) Nếu a ≡ b (mod m) và k là số nguyên dương thì ak ≡ bk (mod m).
6) Nếu a ≡ b (mod m) và d|m thì a ≡ b (mod d).
7) Nếu a ≡ b (mod m) thì ac ≡ bc (mod m) với mọi c khác 0.
8) Nếu ab ≡ ac (mod m) và (a, m) = 1 thì b ≡ c (mod m).
9) a ≡ b (mod mi ) (i = 1, 2, ..., n) ⇔ a ≡ b (mod [m1 , m2 , ..., mn ]).
3

1.2

Một vài định lý cần dùng

Định lý 1.2.1. Định lý Fermat nhỏ
Giả sử p nguyên tố, a là một số nguyên dương, (a, p) = 1. Khi đó ap−1 ≡ 1
(mod p).
Chứng minh. Xét dãy gồm p − 1 số: a, 2a, 3a, ..., (p − 1)a. Ta chứng minh rằng
trong dãy không tồn tại hai số đồng dư với nhau trong phép chia cho p.
Giả sử ka ≡ la (mod p) với k, l ∈ {1, 2, ..., p − 1} và k khác l. Khi đó
.
.
a(k − l) .. p ⇒ k − l .. p ⇒ k = l (mâu thuẫn). Vậy khi chia p − 1 số trong dãy
trên cho p ta nhận được p − 1 số dư khác nhau từ 1, 2, ..., p − 1. Suy ra
a · 2a · · · (p − 1)a ≡ 1 · 2 · · · (p − 1)

(mod p) ⇔ (p − 1)!ap−1 ≡ (p − 1)! (mod p).

Do ((p − 1)!, p) = 1 nên ta có điều phải chứng minh.
Nhận xét 1.2.2. • Từ định lý trên ta có ap ≡ a (mod p) (với p nguyên tố ).
• Định lý đảo của định lý nhỏ Fermat không đúng. Ví dụ như ta có thể kiểm
tra được rằng với mọi số nguyên dương a mà (a, 561) = 1 thì
a560 ≡ 1

(mod 561).

Nhưng 561 = 3 · 11 · 17 không phải là số nguyên tố. Những số có tính chất đặc
biệt như vậy gọi là số giả nguyên tố với mọi cơ sở, hoặc số Carmichael. Ta có
một định lý quan trọng về số Carmichael như sau: “Nếu n là số giả nguyên tố
với mọi cơ sở, tức là ∀a ∈ N∗ , (a, n) = 1 ⇒ an−1 ≡ 1 (mod n), thì n = p1 p2 ...pk
với pi là các số nguyên tố sao cho pi − 1|n với mọi i.
Bằng định lý Thặng dư Trung Hoa, ta đã xác định được dạng phân tích cơ
sở của các số Carmichael. Tuy nhiên các số này rất hiếm. Hai số Carmichael
đầu tiên là 561 và 41041.
Định lý 1.2.3. Định lý Euler
Nếu m là số nguyên dương và (a, m) = 1, thì
aφ(m) ≡ 1

(mod m),

trong đó φ(m) là số các số nguyên dương nhỏ hơn m và nguyên tố cùng nhau
với m.
4

Định lý 1.2.4. Định lý Wilson
p là số nguyên tố khi và chỉ khi (p − 1)! + 1 chia hết cho p.
Chứng minh.
• Nếu (p − 1)! + 1 chia hết cho p thì hiển nhiên p là số nguyên tố. Vì khi đó
p sẽ nguyên tố cùng nhau với các số từ 1 đến p − 1. Do đó nó không có ước nào
khác ngoài 1 và chính nó.
• Ngược lại, nếu p là số nguyên tố thì ta chứng minh (p − 1)! + 1 chia hết
cho p.
Xét đa thức
g(x) = (x − 1)(x − 2)...(x − (p − 1))
và
f (x) = g(x) − (xp−1 − 1).
Rõ ràng phương trình g(x) ≡ 0 (mod p) có p − 1 nghiệm là 1, 2, ..., p − 1.
Theo định lý Fermat nhỏ, xp−1 −1 ≡ 0 (mod p) có p−1 nghiệm là 1, ..., p−1.
Suy ra đa thức f (x) ≡ 0 (mod p) cũng có p − 1 nghiệm. Nhưng đa thức
f (x) có bậc nhỏ hơn p − 1, nên theo định lý Lagrange, các hệ số của f (x) đồng
dư 0 theo modulo p. Hơn nữa, (p − 1)! + 1 lại là hệ số tự do trong f (x). Vậy
(p − 1)! + 1 chia hết cho p.

1.3



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

• Tập hợp x1 , x2 , ..., xn được gọi là một hệ thặng dư đầy đủ modulo m nếu
với mỗi số nguyên y tồn tại duy nhất một số xi sao cho y ≡ xi (mod m).
• Tập {1, 2, ..., m − 1, m} là một hệ thặng dư đầy đủ modulo m.
• Mọi hệ thặng dư đầy đủ modulo m đều có đúng m phần tử.
• Một tập gồm m phần tử là một hệ thặng dư đầy đủ modulo m nếu và chỉ
nếu hai phần tử khác nhau bất kỳ của nó không đồng dư với nhau theo modulo
m.
• Cho số nguyên a và m > 0. Tập hợp tất cả các số nguyên x thỏa mãn
x ≡ a (mod m) được gọi là một lớp đồng dư modulo m, ký hiệu a = {a + mt :
t ∈ Z}. Có m lớp đồng dư phân biệt modulo m thu được bằng cách lấy lần lượt
a = 1, 2, ..., m.

5

• Một tập hợp {r1 , r2 , ..., rn } được gọi là một hệ thặng dư thu gọn modulo
m nếu (ri , m) = 1, ri 6= rj với mọi i 6= j, 1 ≤ i, j ≤ n và với mọi số nguyên x
nguyên tố cùng nhau với m thì tồn tại ri sao cho ri ≡ x (mod m).
Định lý 1.3.1. Cho (a, m) = 1 và {r1 , r2 , ..., rn } là một hệ thặng dư thu gọn
(đầy đủ) modulo m. Khi đó ar1 , ar2 , ..., arn cũng là một hệ thặng dư thu gọn
(đầy đủ) modulo m.

1.4

Nghịch đảo modulo m

Định nghĩa 1.4.1. Giả sử a, m là các số nguyên, m > 1. Nghiệm của phương
trình ax ≡ 1 (mod m) được gọi là nghịch đảo của a modulo m.
Định lý 1.4.2. Nghịch đảo của a modulo m tồn tại ⇔ (a, m) = 1.
Hệ quả 1.4.3. Nếu p nguyên tố thì mỗi phần tử của tập hợp {1, 2, ..., p − 1}
đều có nghịch đảo duy nhất modulo p.

6

Chương 2

Định lý Thặng dư Trung
Hoa và ứng dụng
Định lý Thặng dư Trung Hoa là tên người phương Tây đặt cho định lý này.
Người Trung Quốc gọi nó là Bài toán Hàn Tín điểm binh. Tục truyền rằng khi
Hàn Tín điểm quân số, ông cho quân lính xếp hàng 3, hàng 5, hàng 7 rồi báo
cáo số dư. Từ đó ông tính được chính xác quân số đến từng người.
Trong chương này, chúng tôi sẽ trình bày nội dung của định lý Thặng dư
Trung Hoa và một số ứng dụng của định lý này.

2.1
2.1.1

Định lý thặng dư Trung Hoa
Một số kết quả bổ trợ

Bổ đề 2.1.1. Giả sử rằng m, n là các số nguyên khác 0 thỏa mãn (m, n) = 1.
Giả sử a là một số nguyên tùy ý. Khi đó mn|a ⇔ m|a và n|a.
Chứng minh. • Nếu mn|a thì a = mnt = m(nt) = n(mt) với số nguyên t nào
đó, và do vậy m|a và n|a.
• Ngược lại, nếu m|a thì ta có a = mb với số nguyên b nào đó. Do n|mb và
(n, m) = 1 nên chúng ta có n|b. Do vậy b = nc với số nguyên c nào đó. Từ đó
a = mb = mnc ⇒ mn|a.

7

Hệ quả 2.1.2. Giả sử rằng m, n là các số nguyên dương thỏa mãn (m, n) = 1
và a, b ∈ Z. Khi đó a ≡ b (mod mn) ⇔ a ≡ b (mod m) và a ≡ b (mod n).
Chứng minh. a ≡ b (mod mn) ⇔ mn|(a − b) ⇔ m|(a − b) và n|(a − b) (theo Bổ
đề 2.1.1) ⇔ a ≡ b (mod m) và a ≡ b (mod n).
Bổ đề 2.1.3. Giả sử rằng m1 , m2 , ..., mt , m là các số nguyên khác 0 thỏa mãn
(m, mi ) = 1 với i = 1, 2, ..., t. Khi đó (m, m1 · · · mt ) = 1.
Chứng minh. Ta dùng phản chứng. Giả sử rằng (m, m1 · · · mt ) > 1. Khi đó tồn
tại một số nguyên tố p thỏa mãn p|m và p|m1 · · · mt . Do p nguyên tố, p|mi
với i nào đó nên (m, mi ) khác 1 (trái với giả thiết). Vậy ta có điều phải chứng
minh.
Bổ đề 2.1.4. Giả sử rằng m1 , m2 , ..., mt là các số nguyên dương thỏa mãn
(mi , mj ) = 1 nếu i khác j (Chúng ta gọi điều này là tập các số nguyên đôi một
nguyên tố cùng nhau). Đặt m = m1 · · · mt . Nếu a, b ∈ Z thì
a ≡ b (mod m) ⇔ a ≡ b (mod mi ) với mọi i = 1, 2, ..., t.
Chứng minh.
• Nếu a ≡ b (mod m) thì dễ dàng suy ra a ≡ b (mod mi ) với mọi i =
1, 2, ..., t.
• Ngược lại, giả sử a ≡ b (mod mi ) với mọi i = 1, 2, ..., t, ta sẽ chứng minh
a ≡ b (mod m) bằng cách quy nạp theo t.
Nếu t = 2 thì đó chính là Hệ quả 2.1.2.
Giả sử kết quả đúng với t, và m1 , m2 , ..., mt , mt+1 là các số đôi một nguyên
tố cùng nhau cho trước.
Đặt m = m1 · · · m2 · · · mt+1 . Do (mt+1 , mi ) = 1 với mọi i = 1, 2, ..., t nên suy
ra rằng (mt+1 , m1 · · · mt ) = 1 (theo Bổ đề 2.1.3). Ta viết m = (m1 · · · mt )·mt+1 .
Khi đó
a ≡ b (mod m)
⇔ a ≡ b (mod m1 · · · mt ) và a ≡ b (mod mt+1 ) (theo Hệ quả 2.1.2)
⇔ a ≡ b (mod mi ) với mọi i ≤ t và a ≡ b (mod mt+1 )
⇔ a ≡ b (mod mi ) với mọi i ≤ t + 1.

8

Hệ quả 2.1.5. Giả sử m > 1 và giả sử rằng m = pa1 1 . . . pat t là phân tích nguyên
tố của m. Nếu a, b ∈ Z chúng ta có
a ≡ b (mod m) ⇔ a ≡ b (mod pai i ) với mọi i = 1, 2, ..., t.

2.1.2

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

Định lý 2.1.6. Định lý thặng dư Trung Hoa
Giả sử rằng m1 , m2 , ..., mt là các số nguyên dương và đôi một nguyên tố
cùng nhau. Đặt m = m1 . . . mt . Giả sử a1 , ..., at ∈ Z.
1) Tồn tại c ∈ Z thỏa mãn


c





c








c

≡ a1

(mod m1 ),

≡ a2
..
.

(mod m2 ),

≡ at

(mod mt ).

2) Nếu c là một nghiệm thì nghiệm tổng quát là x = c + ms, s ∈ Z.
Chứng minh.

m
. Vì vậy m = mi ni . Chú ý rằng (mi , ni ) = 1
mi
với mọi i (theo Bổ đề 2.1.3) do các số m1 , m2 , ..., mt đôi một nguyên tố cùng
1) Với i = 1, 2, ..., t đặt ni =

nhau.
Bởi vậy, với mỗi i, phương trình đồng dư
ni x ≡ 1 (mod mi )
là giải được; tức là, với mỗi i đều tồn tại một số nguyên bi thỏa mãn
ni bi ≡ 1

(mod mi ).

(2.1)

Mặt khác nếu j khác i thì
nj bj ≡ 1 (mod mj )

do mi |nj .

Bây giờ, đặt
c := a1 n1 b1 + . . . + at nt bt .

9

(2.2)

Cố định một i nào đó, theo (2.2) ta có
aj nj bj ≡ 0

(mod mi ),

nếu i khác j

và vì vậy
c ≡ ai ni bi

(mod mi ).

Tuy nhiên, theo (2.1) ta có
n i bi ≡ 1

(mod mi )

và vì vậy
c ≡ ai

(mod mi ).

Ta đã chứng minh xong khẳng định thứ nhất.
2) Giả sử rằng d là một nghiệm khác của hệ đồng dư trên. Khi đó
c ≡ d (mod mi ) với mọi i ⇒ c ≡ d (mod m) (theo Bổ đề 2.1.4),
vì vậy d = c + ms với s nào đó.
Ngược lại nếu d = c + ms với s nào đó thì d ≡ c (mod m), và vì vậy với mỗi
i, d ≡ c ≡ ai (mod mi ). Điều này có nghĩa là d cũng là một nghiệm.



Chú ý 2.1.7. Định lý Thặng dư Trung Hoa khẳng định rằng nếu m1 , m2 , ..., mt
là các số nguyên dương và đôi một nguyên tố cùng nhau, m = m1 . . . mt và
a1 , ..., at ∈ Z thì hệ đồng dư tuyến tính


x ≡ a1 (mod m1 ),





x ≡ a2 (mod m2 ),
..


.





x ≡ at (mod mt ).
luôn có nghiệm và có vô số nghiệm. Nghiệm của hệ này được cho bởi khẳng
định 2).
Nhận xét 2.1.8. Định lý Thặng dư Trung Hoa khẳng định về sự tồn tại duy
nhất của một lớp thặng dư các số nguyên thỏa mãn đồng thời nhiều phương
trình đồng dư tuyến tính. Do đó ta có thể sử dụng định lý này để giải quyết các
bài toán về sự tồn tại và số các số nguyên thỏa mãn một hệ phương trình đồng
dư tuyến tính, chia hết, ... Việc sử dụng hợp lý các bộ số nguyên m1 , m2 , ..., mt
10

và a1 , a2 , ..., at (trong định lý) cho ta nhiều kết quả thú vị và từ đó đưa ra nhiều
bài tập hay và khó.
Ngoài cách chứng minh bên trên, ta có thể chứng minh định lý Thặng dư
Trung Hoa bằng phép quy nạp.
Trước khi đi vào ví dụ của phần này, chúng tôi nêu ra phương pháp chứng
minh của Knuth cho định lý thặng dư Trung Hoa.
Giả sử chúng ta có sẵn một tập gồm n số nguyên dương m1 , m2 , ..., mn đôi
một nguyên tố cùng nhau. Giả sử M = m1 ∗ m2 ... ∗ mn . Giả sử u1 , u2 , ..., un là
các số nguyên dương đã biết ≤ m1 , m2 , ..., mn tương ứng. Khi đó tồn tại một
và chỉ một số nguyên dương u thỏa mãn
0 < u ≤ mj và u ≡ uj

(mod mj ),

1 ≤ j ≤ n.

(1)

Đây chính là nội dung của định lý thặng dư Trung Hoa. Trước khi chứng
minh định lý này, ta nhắc lại một chút về hàm Euler - φ(n). Nếu n biểu diễn
dưới dạng
n = pε11 ∗ ... ∗ pεss ,
trong đó p1 , p2 , ..., ps là các số nguyên tố đôi một khác nhau, thì khi đó




1
1
φ(n) = n ∗ 1 −
∗ ... ∗ 1 −
.
p1
ps

(2)

(3)

Đặc biệt nếu n là số nguyên tố p, thì
φ(p) = p − 1.

(4)

Ví dụ với số nguyên tố 83, ta có φ(83) = 82. Trong khi với số không nguyên
tố như n = 225600 = 26 ∗ 3 ∗ 52 ∗ 47, ta có
φ(225600) = 58880.

(5)

Như vậy, nếu phân tích của n là không tầm thường, thì φ(n) sẽ rất lớn nếu
như n lớn. Điều này sẽ gây ra khó khăn trong tính toán.
Chứng minh định lý thặng dư Trung Hoa theo cách của Knuth.
Ta đặt

Mj =

M
mj

φ(mj )
,

11

1 ≤ j ≤ n.

(6)

Khi đó theo định lý Euler, số nguyên u bất kỳ thỏa mãn phương trình đồng
dư
u ≡ (u1 ∗ M1 + ... + un ∗ Mn )

(mod M )

(7)

sẽ thỏa mãn hệ phương trình đồng dư
u ≡ uj

1 ≤ j ≤ n.

(mod mj ),

(8)

Vì tính duy nhất là hiển nhiên nên ta đã chứng minh xong định lý.
Bài toán bây giờ là đi tìm các số nguyên và thường là số nguyên dương nhỏ
nhất thỏa mãn (1). Để làm điều này, ta đặt
kj ∗

M
≡1
mj

(mod mj ),

j = 1, 2, ..., n.

(9)

Số kj được gọi là tỷ số nhân.
Đặt
Nj = k j ∗

M
≡ 1 (mod mj ).
mj

(10)

Nj được gọi là các số dư. Khi đó, số u cần tìm sẽ thỏa mãn phương trình
(11) dưới đây
X

u=

u j ∗ Nj

j=1,2,...,n

hay
X

u=

uj ∗ kj ∗

j=1,2,...,n

M
.
mj

(11)

Với nghiệm λ bất kỳ (λ có thể dương, hoặc âm, hoặc bằng 0), chúng ta có
X

u=

uj ∗ kj ∗

j=1,2,...,n

M
+ λ ∗ M.
mj

(11’)

Để có một số ý tưởng so sánh giữa phương pháp phương đông và phương
pháp của chúng ta, ta hãy xét bài toán dưới đây.
Hãy tìm u sao cho
u≡1

(mod 19),

u ≡ 14

(mod 17),

u ≡ 1 (mod 12).

Theo phương pháp Quin Jiushao, chúng ta có
M = m1 ∗ m2 ∗ m3 = 3876,
12

M
= 204, 228, 323,
mj
kj = 15, 5, 11,
Nj = 15 ∗ (17 ∗ 12), 5 ∗ (19 ∗ 12), 11 ∗ (19 ∗ 17).
Cuối cùng, chúng ta có
u≡

3
X

ui ∗ Ni

i=1

hay
u ≡ 15 ∗ (17 ∗ 12) + 5 ∗ (19 ∗ 12) + 11 ∗ (19 ∗ 17)

(mod 3876).

Từ đó, chúng ta tìm được số nguyên dương u nhỏ nhất thỏa mãn.
Nếu ta sử dụng phương pháp phương đông, thì ta có
N1 = (17 ∗ 12)φ(19) = 20418 ,

N2 = (19 ∗ 12)φ(17) = 22816 ,

N3 = (19 ∗ 17)φ(13) = 32312 ,
và cuối cùng
u ≡ 20418 + 14 ∗ 22817 + 32312

(mod 3876).

Các phép tính toán này rõ ràng là rất kinh khủng!

2.1.3

Mở rộng định lý Thặng dư Trung Hoa

Trong định lý Thặng dư Trung Hoa có điều kiện m1 , m2 , ..., mn là các số
nguyên dương đôi một nguyên tố cùng nhau. Câu hỏi đặt ra là nếu m1 , m2 , ..., mn
không thỏa mãn điều kiện nguyên tố cùng nhau thì kết quả của định lý sẽ như
thế nào ?
Định lý 2.1.9. Định lý Thặng dư Trung Hoa mở rộng
Cho m1 , m2 , ..., mn là các số nguyên dương, r1 , r2 , ..., rn là các số nguyên bất
kỳ. Khi đó, điều kiện cần và đủ để hệ phương trình đồng dư


x ≡ r1 (mod m1 ),





x ≡ r2 (mod m2 ),


...




x ≡ r
n (mod mn ),
13

có nghiệm là ri ≡ rj (mod gcd(mi , mj )) với mọi 1 ≤ i < j ≤ n.
Nếu x0 và x1 là hai nghiệm thỏa mãn hệ phương trình trên thì x0 ≡ x1
(mod m) với m = lcd (m1 , m2 , ..., mn ). Tức là hệ phương trình đã cho có nghiệm
duy nhất theo modulo m.
Chứng minh. Trước hết ta giả sử hệ phương trình đã cho có nghiệm x0 . Đặt
gcd(mi , mj ) = d, ta có

x0 − ri ≡ 0 (mod mi ),
x − r ≡ 0 (mod m ).
0
j
j
Suy ra ri ≡ rj (mod gcd(mi , mj )). Do i, j tùy chọn nên
ri ≡ rj

(mod gcd(mi , mj ))

với mọi 1 ≤ i < j ≤ n. Đây là điều kiện cần để hệ phương trình có nghiệm.
Ngược lại, ta sẽ chứng minh bằng quy nạp theo n rằng nếu điều kiện trên
được thỏa mãn thì hệ phương trình luôn có nghiệm duy nhất theo modulo m
với m = lcd (m1 , m2 , ..., mn ).
• Với n = 2, đặt gcd(m1 , m2 ) = d ⇒ m1 = dd1 , m2 = dd2 với gcd(d1 , d2 ) =
1. Suy ra
ri ≡ rj ≡ r

(mod d).

Đặt r1 = r + k1 d, r2 = r + k2 d.

x ≡ r1
x ≡ 1



(x − r) − k1 d ... dd1
⇔

(x − r) − k2 d ... dd2

(mod m1 )

(mod m2 )
x − r

≡ k2


 d
⇔



x − r ≡ k
2
d

(mod d1 )

(mod d2 )

Do (d1 , d2 ) = 1 nên theo định lý thặng dư Trung Hoa, tồn tại một số dương
x−r
x sao cho x ≡ k1 (mod d1 ): x ≡ k2 (mod d2 ). Vì x và
là hai nghiệm của
d
phương trình

x ≡ k1 (mod d1 )
x ≡ k (mod d )
2

2

14

nên

x−r
≡ x (mod d1 d2 )
d

hay
x ≡ xd + r

(mod dd1 d2 ).

Do m = lcd (m1 , m2 ) = dd1 d2 nên theo định lý thặng dư Trung Hoa, hệ có
nghiệm duy nhất theo modulo m.
Giả sử định lý đúng đến n − 1. Ta sẽ chứng minh định lý đúng đến n. Đặt
m01 = lcd (m1 , m2 , ..., mn−1 ), m02 = mn , r20 = rn . Vì ri ≡ rj (mod gcd(mi , mj ))
với mọi 1 ≤ i < j ≤ n nên theo giả thiết quy nạp, hệ phương trình

x ≡ ri (mod mi ),
i = 1, n − 1
có nghiệm duy nhát x ≡ r10 (mod m01 ).
Mặt khác từ ri ≡ rj (mod gcd(mi , mj )) với mọi 1 ≤ i < j ≤ n suy ra
r10

≡ r20 (mod gcd(m01 , m02 )). Theo chứng minh trên cho trường hợp n = 2 ta có

hệ phương trình

x ≡ r 0

(mod m01 ),

x ≡ r 0

(mod m02 )

1
2

có nghiệm duy nhất theo modulo m = lcd (m01 , m02 ) = lcd (m1 , m2 , ..., mn ).
Theo nguyên lý quy nạp, ta có điều phải chứng minh.

2.2

Một vài ứng dụng của định lý thặng dư
Trung Hoa

2.2.1

Chứng minh sự tồn tại của một mệnh đề

Định lý Thặng dư Trung Hoa có rất nhiều ứng dụng trong Lý thuyết số.
Trong mục này, chúng tôi trình bày việc ứng dụng định lý này vào chứng minh
một mệnh đề trong Lý thuyết số.
Bài toán 2.2.1. Chứng minh rằng với mỗi số tự nhiên n, tồn tại n số tự nhiên
liên tiếp mà mỗi số trong n số đó đều là hợp số.

15

Lời giải. Giả sử p1 , p2 , ..., pn là n số nguyên tố đôi một khác nhau. Do đó ta có
(p2i , p2j ) = 1 nếu i khác j và 1 ≤ i, j ≤ n.
Xét hệ đồng dư tuyến tính


x ≡ −1 (mod p21 ),





x ≡ −2 (mod p22 ),
..


.





x ≡ −n (mod p2n ).
Theo Định lý thặng dư Trung Hoa thì hệ phương trình đồng dư trên có
nghiệm. Giả sử c là một nghiệm của nó, tức là
c ≡ −k

(mod p2k ),

∀k = 1, n.

Chọn t là số dương đủ lớn thì ta có
x0 = c + (p21 p22 ...p2n )t > 0.
Vẫn theo Định lý thặng dư Trung Hoa thì x0 cũng là một nghiệm của hệ
phương trình trên. Do vậy ta có

x0 ≡ −k (mod p2 ),
k
x > 0.

∀k = 1, n,

0

.
Từ đó suy ra (x0 + k) .. p2k với mọi k = 1, n. Nói cách khác, x0 + 1, x0 + 2,
..., x0 + n là n số tự nhiên liên tiếp mà mỗi số trong n số đó đều là hợp số. Đó
là điều phải chứng minh.



Bài toán 2.2.2. Chứng minh rằng với mọi số tự nhiên n, tồn tại n số tự nhiên
liên tiếp mà bất kỳ số nào trong các số đó đều không phải là lũy thừa với số
mũ nguyên dương của một số nguyên tố.
Lời giải.
Cách 1. Bài này có nét tương đồng với bài toán trước nên ta nghĩ đến việc
chọn một hệ đồng dư tương tự bài trên rồi áp dụng định lý Thặng dư Trung
Hoa để chứng minh.
Ta đã biết rằng nếu một số chia hết cho p nhưng lại không chia hết cho p2
thì số đó phải là lũy thừa của p. Điều này đưa ta đến việc lựa chọn hệ sau
x ≡ pi − i

(mod p2i ),
16

với i ∈ {1, 2, ..., n},

trong đó p1 , p2 , ..., pn là những số nguyên tố phân biệt. Áp dụng định lý Thặng
dư Trung Hoa, tồn tại x thỏa mãn hệ trên. Dễ thấy x + i chia hết cho pi nhưng
không chia hết cho p2i . Ta có điều phải chứng minh.



Cách 2. Giả sử n là một số tự nhiên bất kỳ và p1 , p2 , ..., pn , q1 , q2 , ..., qn là
các số nguyên tố khác nhau từng đôi một. Theo định lý Thặng dư Trung Hoa,
hệ phương trình đồng dư


x ≡ −1 (mod p1 q1 ),





x ≡ −2 (mod p2 q2 ),
..


.





x ≡ −n (mod pn qn ),
có nghiệm.
Chú ý rằng các số p1 q1 , p2 q2 , ..., pn qn nguyên tố cùng nhau đôi một. Hiển
nhiên ta có thể chọn x = c là một nghiệm của hệ này sao cho c ∈ N∗ . Khi đó
các số c + 1, c + 2, ..., c + n là n số tự nhiên liên tiếp và bất kỳ số nào trong
.
các số đó cũng chia hết cho ít nhất hai số nguyên tố khác nhau (c + 1) .. p1 q1 ,
.
.
(c + 2) .. p2 q2 , ..., (c + n) .. pn qn . Vì vậy không có số nào trong các số đó là lũy
thừa (với số mũ nguyên dương) của một số nguyên tố.



Bài toán 2.2.3. (Hàn Quốc 1999)
Tìm tất cả các số tự nhiên n thỏa mãn 2n − 1 chia hết cho 3 và có một số
2n − 1  2
m ∈ Z mà
4m + 1.
3
Lời giải.
• Nếu n ≡ 1 (mod 2) thì 2n ≡ −1 (mod 3). Như vậy 2n − 1 không chia hết
cho 3.
• Nếu n ≡ 0 (mod 2), đặt n = 2k · u (u là một số lẻ và u ≥ 1). Ta có
k

2n − 1 chia hết cho 3. Mặt khác, 2n − 1 = 22

·u

− 1 chia hết cho 2u − 1. Do vậy

2u − 1|4m2 + 1.
Vì u ≥ 3 nên 2u − 1 ≡ 3 (mod 4). Bởi vậy 2u − 1 sẽ có một ước nguyên tố
đồng dư −1 (mod 4). Vậy 4m2 + 1 chia hết cho p với p = 4r + 3, nên 4m2 chia
hết cho p và 1 cũng chia hết cho p (mâu thuẫn).
Vậy n = 2k . Ta chứng minh rằng n = 2k thỏa mãn đề bài bằng cách chỉ ra
một số m thỏa mãn điều kiện đề bài:
2n − 1
= F1 · F2 · · · Fk−1 ,
3
17

trong đó
i

Fi = 22 + 1.
Không khó để chứng minh gcd (Fi , Fj ) = 1 với i khác j.
Áp dụng định lý Thặng dư Trung Hoa thì tồn tại số c bằng 2m mà
i−1

i

c2 ≡ 22

(mod 22 ) với i = (1, k − 1).

2n − 1  2

4m + 1 với n = 2k .
3
Chú ý. Ta nhận thấy rằng bài toán này có một sự liên kết chặt chẽ tới những
Vậy sẽ tồn tại m thỏa mãn

tính chất của số Fermat nên nếu áp dụng một số tính chất này ta sẽ có phát
biểu thú vị của bài toán Hàn Quốc 1999.
Bài toán 2.2.4. Cho n thỏa mãn
2n − 1  2
4m + 1.
3
Chứng minh rằng tất cả các ước khác {1, 3, 2n − 1} của hệ đều đồng dư với 1
(mod 2q ), q 6= 1 và q ∈ N∗ .
Để giải bài toán này thì ngoài kết quả của bài toán trước, chúng ta cần thêm
bổ đề sau đây.
m

Bổ đề: Nếu p là một ước nguyên tố của Fm = 22

thì p ≡ 1 (mod 2m+1 ).

Lời giải bài toán 2.2.4. Theo bài trước, n = 2k và tất cả các ước của 2n − 1
là ước của số Fermat Fm (m = 1, 2, ..., k − 1). Theo bổ đề trên, ta có tất cả các
ước nguyên tố của 2n − 1 trừ {1, 3, 2n − 1} cùng có số dư 1 modulo 2q .
α2
αr
n
1
Giả sử 2n − 1 có dạng pα
1 .p2 . . . pr . Từ đó một ước của 2 − 1 có dạng

d = pβ1 1 .pβ2 2 . . . pβr r với pβi i ≡ 1 (mod 2qi ). Như vậy d ≡ 1 (mod 2qi ) với qi là số
nhỏ nhất trong tập {q1 , q2 , ..., qr }.



Bài toán 2.2.5. Cho f (x) là một đa thức với các hệ số nguyên. Giả sử rằng có
một tập hữu hạn các số nguyên tố {p1 , p2 , p3 , ..., pn } để cho với mọi số nguyên
n, f (n) chia hết cho pi nào đó. Chứng minh rằng sẽ có một số nguyên tố p để
p|f (n) với mọi n ∈ Z.
Lời giải. Giả sử rằng điều phải chứng minh là sai nên với mỗi pi sẽ tồn tại một
số ai ∈ Z mà pi không là ước của f (ai ) hay f (ai ) không ≡ 0 (mod pi ). Ta xét
hệ đồng dư sau
a ≡ ai

(mod pi ), với i ∈ {1, 2, ..., r}.
18