Đại học Khoa Học Tự Nhiên - Đại học Quốc Gia Hà Nội
Khối Trung học phổ thông chuyên Toán - Tin
ĐỊNH LÝ THẶNG DƯ TRUNG HOA VÀ MỘT SỐ ỨNG DỤNG
Nguyễn Thành Công, Nguyễn Hữu Phúc, Nguyễn Khương Linh,
Nguyễn Đăng Quang, Vũ Xuân Thành Long.
Lớp 10A1 Toán
Giáo viên hướng dẫn: Ts. Phạm Văn Quốc
Hà Nội, tháng 3 năm 2010
là những số nguyên khác 0 và ñôi một nguyên tố cùng nhau
gcd(m
i
,m
j
)=1
với i
≠
j, thì với a
1
,a
2
,a
3
, ,a
n
nguyên bất kì, hệ ñồng dư x
≡
a
i
(mod m
i
)

có nghiệm và nghiệm
này xác ñịnh duy nhất modulo
1
r
mi
∏

j
)=d
i,j
│(b
i
-b
j
) và
nếu nó có nghiệm thì nghiệm ñó là duy nhất theo module lcm(m
1
,m
2
, …,m
n
).

II) Những kết quả và kĩ thuật mới
2.1) Ứng dụng trong chứng minh sự tồn tại của 1 mệnh ñề lý thuyết số
Định lý thặng dư Trung Hoa có rất nhiều ứng dụng trong Lý Thuyết số, ñặc biệt là với những
bài toán về sự tồn tại của 1 mệnh ñề lý thuyết số.
Bài1: Chứng minh rằng với bất cứ số tự nhiên n nào, ñều tồn tại n số tự nhiên liên tiếp mà 1
trong số n số tự nhiên ñó có ít nhất 1 ước số là số chính phương.
Giải: Xét hệ ñồng dư x
≡
-i (mod p
i
2
) với p
i
là 1 số nguyên tố (i=

2,…
,p
n
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ệ. Dễ dàng thấy ñược x+i chia hết cho p
i
nhưng không chia hết cho p
i
2
(ĐPCM ).

Bài3:(Hàn Quốc 1999) Tìm tất cả các số tự nhiên n thỏa mãn: 2
n
-1 chia hết cho 3 và có 1 số
m
∈
Z mà
n
2 1
3
−
| 4m
2
+1.
Giải:
Nếu n≡1 (mod 2) thì 2
n
≡-1 (mod 3), như vậy 2
n
-1 không chia hết cho 3. Nếu n≡0 (mod 2), ñặt

k
. Ta chứng minh rằng n=2
k
thỏa mãn ñề bài bằng cách chỉ ra 1 số m thỏa mãn ñiều
kiện ñề bài:
2 1
3
n
−
=F
1
.F
2
…F
k-1
với F
i
là số Fermat: F
i
=2
2
i
+1. Không khó ñể chứng minh
gcd(F
i
,F
j
)=1 với i≠j.
Áp dụng Định lý Thặng Dư Trung Hoa thì có 1 số chẵn c bằng 2m mà
C

+1. Chứng minh rằng tất cả các ước khác {1, 3, 2
n
-1} của hệ
ñều ñồng dư với 1 (mod 2
q
), q≠1 và k
∈
N*.
Không dễ dàng ñể chứng minh bài toán này mà không có kết quả của bài trước. Tuy nhiên sử
dụng bài toán trước với bổ ñề sau ñây còn có thể giải bài toán này dễ dàng hơn.
Bổ ñề: Chứng minh rằng nếu p là 1 ước nguyên tố của F
m
=2
2
m
thì p≡1 ( mod 2
m+1
)
Bổ ñề trên ta có thể dễ dàng chứng minh ñược bằng tính chất của cấp của một số.
Lời giải bài 4. Theo bài toán trước, n=2
k
và tất cả các ước của 2
n
-1 là ước của số Fermat F
m

(m=1, 2, 3, …, k-1). Cũng từ bổ ñề trên , ta có tất cả các ước nguyên tố của 2
n
-1 trừ {1,3, 2
n

β
.
p
2
2
β
.
p
3
3
β

p
r
r
β

với p
i
i
β
≡
1 (mod 2
i
q
) như vậy d
≡
1(mod 2
i
q

Z mà p
i
không
là ước của f(a
i
) hay f(a
i
) không
≡
0(mod p
i
). Ta xét hệ ñồng dư sau: a
≡
a
i
mod p
i
với
i
∈
{1,2,3,…r}. Áp dụng Định lý Thặng Dư Trung Hoa ta có thể tìm ñược 1 số nguyên a thỏa
mãn hệ này. Mặt khác ta dễ dàng chứng minh f(a)
≡
f(a
i
) mod p
i
với i
∈
{1,2…r}. Do vậy, có 1

Z
Giải: Tương tự với bài trước, ta giả sử rằng kết luận ñề bài sai. Vậy với mỗi i
∈
{1,2, ,n}, tồn
tại số nguyên x
i
ñể f(x
i
) không chia hết cho a
i
.
Từ ñó, tồn tại 1 số p
i
ki
với p
i
là số nguyên tố- thỏa mãn p
i
ki
| a
i
nhưng f(x
i
) không chia hết cho
p
i
ki

Cho i chạy từ 1 ñến n ta ñược tập hợp các số sau: {p
1

,…,p
m
là những số nguyên tố phân biệt).
Chú ý rằng a
i
chia hết cho 1 số số hạng trong tập này.
Từ p
1
q1
, p
2
q2
, … ,
p
m
qm là
những số ñôi một nguyên tố cùng nhau, ta xét hệ ñồng dư x≡x
i
(mod
p
i
qi
) với i
∈
{1,2,…,n}
Áp dụng Định lý Thặng Dư Trung Hoa, ta có nghiệm của hệ.
Mặt khác, x≡x
i
(mod p
i

ba
2
,….,ba
n
} bao gồm những luỹ thừa ñúng của 1 số nguyên.
Giải. Đặt p
1
,p
2
,p
3
,…,p
k
là các số nguyên tố có mặt trong phép phân tích a
1
,a
2
, a
3
, …., a
n

thành thừa số nguyên tố. Ta có a
i
=p
1
bi1
.p
2
bi2

d3
….p
k
dk
. Ta sẽ chứng minh rằng có thể tìm ñược d
1
,d
2
, d
k
mà b thỏa mãn
ñiều kiện ñề bài.
Để có ba
1
là lũy thừa bậc q
1
của 1 số nguyên thì b
11
+d
1
, b
12
+d
2
, b
13
+d
3
, …., b
1k

2,
…
b
n1
+d
1
, b
n2
+d
2
, b
n3
+d
3
,…., b
nk
+d
k
chia hết cho q
n.

Từ ñó phải xác ñịnh d
1
, d
2
, d
3
…, d
k
thỏa mãn d

. Từ ñó tồn tại b (ĐPCM).
Bài toán này có thể có rất nhiều hệ quả, ñặc biệt là bài toán IMO 33
rd
long list:
Bài8. Chứng minh rằng với mọi số nguyên dương n, tồn tại 1 tập số nguyên ñể tổng các phần
tử của các tập con không rỗng của nó là 1 lũy thừa.
Giải: Ta xét tập số nguyên S={x
1
, x
2
, x
3
,…, x
n
}, có 2
n-1
tập con không rỗng của S. Đặt
S
1
,S
2
,S
3
,S
4
,…, S
2 1
n
−
là tổng các phần tử của các tập này. Áp dụng bài trước, tồn tại 1 số b

a1
.p
2
a2
. … , .
p
k
ak

Ta có x
2
≡x (mod m). Từ ñó x
2
≡x (mod p
i
ai
) với i
∈
{1, 2,…, k} (gcd(p
i
ai
,p
j
aj
)=1 with i≠j)
x(x-1)≡0 (mod p
i
ai
) với i
∈

2008
. Có bao nhiêu số n sao cho n<m và n(2n+1)(5n+1) chia
hết cho m ?
Giải: Ta dễ dàng nhận thấy gcd(m,10)=1
n(2n+1)(5n+2)≡0 (mod m)
Do ñó 10n(10n+5)(10n+4)≡0 (mod m) (1)
Ta có m=3
4016
.223
2008
.
Đặt 10n=x, 3
4016
=q
1
, 223
2008
=q
2
. Vì gcd(q
1
,q
2
)=1nên (1) tương ñương với
x(x+5)(x+4)≡0(mod q
1
) (2)
x(x+5)(x+4)≡0(mod q
2
) (3)

1
)
Áp dụng Định lý Thặng Dư Trung Hoa, hệ chỉ có 1 nghiệm (mod 10q
1
q
2
)
Với mỗi cặp (r
1
, r
2
), chỉ có 1 số x. Nhưng lại có 3
2
cách chọn cặp (r
1
, r
2
), vậy sẽ có 9 số x thỏa
mãn. III) Một số bài áp dụng
Thay lời kết cho bài báo này chúng tôi ñưa ra một số bài toán thú vị về ñịnh lí thặng dư Trung
Hoa. Mong các bạn có thể tìm ra ñược những lời giải hay và ñẹp nhất.
Bài2. Tìm tất cả các số m
∈
Z: 2
n
-1 | m
2

C phân biệt
sao cho (a+k,b+k)>1. Giả sử rằng ta có một tập tốt mà tổng các phần tử trong ñó bằng 203.
CMR ta có thể loại ñi 1 phần tử trong tập C sao cho tập còn lại vẫn là tập tốt.
Bài6(Czech-Slovakia 1997). CMR tồn tại vô số dãy vô hạn tăng {a
n
} của các số tự nhiên thoả
mãn với k
∈
N, dãy {k+a
n
} chứa hữu hạn số nguyên tố.

IV) Tài liệu tham khảo.
[1] Number Theory, Structures, Examples and Problems, Springer (Titu Andresscu and Dorin
Andrica )
[2]Bài giảng số học I, II, Nhà xuất bản giáo dục (Nguyễn Vũ Lương )
[3]Một số tài liệu từ mạng Internet và các diễn ñàn toán học
+ www.mathscope.org
+ www.diendantoanhoc.net
+ www.mathlinks.ro