Định lý số dư trung hoa
LỜI MỞ ĐẦU
Mang lại rất nhiều lợi ích trong điện toán, toán học và đặc biệt là lĩnh vực mật mã, Định lý Số dư
trung hoa là một trong những “viên kim cương” của Toán học, bởi nó kết hợp hài hòa giữa vẻ đẹp
Toán học thuần túy và ứng dụng thực tế cuộc sống và qua nhiều thời đại, mặc dù có cải biên dưới
nhiều hình thức nhưng dường như nó vẫn giữ một vai trò nhất định.
Đến đây có thể bạn sẽ thắc mắc, nội dung của định lý này là gì? Và nó như thế nào mà lại được ví
như “viên kim cương” của Toán học, hãy tự trả lời những vướng mắc của mình bằng cách đọc và
suy ngẫm phần nội dung của bài viết này nhé.
Mục tiêu đặt ra cho chuyên đề này là những ví dụ cụ thể minh họa cho định lý Số Dư Trung Hoa,
giúp người xem có cái nhìn bao quát về nội dung của nó. Hy vọng với những gì nhóm trình bày sẽ
mang lại cho người đọc một lợi ích nhất định dù có thể rất nhỏ.
Mặc dù nhóm chúng tôi đã cố gắng nhưng trong quá trình biên soạn có thể không tránh khỏi nhưng
sai sót, rất mong sự góp ý của mọi người để bài viết hoàn thiện hơn.
Cảm ơn TS Trần Nam Dũng đã tạo điều kiện để chúng tôi thực hiện bài viết này.
Nhóm thực hiện
MỤC LỤC
1. GIỚI THIỆU VỀ ĐỊNH LÝ SỐ DƯ TRUNG HOA ...................................................... 1
2. ĐỊNH LÝ SỐ DƯ TRUNG HOA ................................................................................... 1
3. ỨNG DỤNG ĐỊNH LÝ SỐ DƯ TRUNG HOA ............................................................. 2
3.1 Sử dụng hệ thặng dư trong các bài toán đa thức, chia hết ............................................. 2
3.2 Sử dụng hệ thặng dư trong phương trình Đi Ô Phăng bậc nhất .................................... 7
3.3 [Bài toán] Phương trình nghiệm nguyên, định lý phần dư Trung Hoa ......................... 9
3.4 [Bài toán] Định lý phần dư Trung Hoa ....................................................................... 10
3.5 [Bài toán] Ứng dụng định lý phần dư Trung Hoa ....................................................... 16
3.6 [Bài toán] Tính chất số nguyên tố, phần dư Trung Hoa .............................................. 20
3.7 Bài toán [Hệ đồng dư, số square - free]....................................................................... 21
Trang 1
1. GIỚI THIỆU VỀ ĐỊNH LÝ SỐ DƯ TRUNG HOA
Định lý số dư Trung Quốc 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. Hàn Tín là một danh tướng thời Hán Sở, từng được
phong tước vương thời Hán Cao Tổ Lưu Bang đang dựng nghiệp. Sử ký Tư Mã Thiên viết
rằng Hàn Tín là tướng trói gà không nổi, nhưng rất có tài quân sự. 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 chính xác quân số đến từng người.
Gần đây, định lý số dư Trung Quốc có nhiều ứng dụng trong các bài toán về số nguyên lớn
áp dụng vào lý thuyết mật mã.
Định lý Trung Hoa giúp ta giải quyết nhiều bài toán khó, làm cho nhiều bài toán khó trở
nên dễ dàng hơn và cho ta những lời giải khá bất ngờ. Như việc sử dụng định lý để chứng
minh công thức Euler, hay giải bài toán mở rộng của định lý Wilson và đếm số nghiệm của
phương trình đồng dư. Ngoài ra định lý còn được ứng dụng trong thực tế đó là việc xây
dựng lý thuyết mật mã, trong đó tiêu biểu là lý thuyết mật mã RSA.
2. ĐỊNH LÝ SỐ DƯ TRUNG HOA
Bản chất của bài toán Hàn Tín điểm binh là việc giải hệ phương trình đồng dư bậc nhất
x a1 mod m1
x a2 mod m2
...
x a mod m
k
k
Trong đó m1 , m2 ,..., mk đôi một nguyên tố cùng nhau.
Từ đó trong bài toán Hàn Tín ta hiểu k 3 và m1 3, m2 5, m3 7 .
Định lý: Hệ phương trình đồng dư trên có nghiệm duy nhất theo mođun m m1.m2 ...mk
là
x a1M1 y1 a2 M 2 y2 ... ak M k yk mod M
Trong đó
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 2
M
M
M
,M2
,..., M k
m1
m2
mk
M1
y1 M1
1
mod m1 ,
y2 M 2
1
mod m2 , …,
yk M k
1
mod mk
M1 mod m1 : là nghịch đảo theo modulo của m1 .
1
Với
y1 M1
1
mod m1 y1M1 1 mod m1
3. ỨNG DỤNG ĐỊNH LÝ SỐ DƯ TRUNG HOA
3.1 Sử dụng hệ thặng dư trong các bài toán đa thức, chia hết
Bài toán 1: Giải hệ phương trình đồng dư
x 2 mod 3
x 3 mod 5
x 5 mod 7
Lời giải:
Ta có
M 3.5.7 105; M1 5.7 35, M 2 3.7 21, M 3 3.5 15
y1 351 mod 3 21 mod 3 2;
y2 211 mod 5 11 mod 5 1;
y3 151 mod 7 11 mod 7 1.
Từ đó
x 2.35.2 3.21.1 5.15.1 mod105
x 140 63 75 mod105 278 mod105
x 68 mod105
Như vậy x có dạng x 68 k.105 , k là số nguyên (hoặc số nguyên thích hợp nếu tìm
nghiệm tự nhiên).
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 3
Bài toán 2: Tìm số nguyên dương nhỏ nhất có tính chất: Chia 7 dư 5, chia 11 dư 7 và
chia 13 dư 3.
Lời giải:
x 5(mod 7)
Xét hệ phương trình: x 7(mod11) ta có (7,11) (11,13) (13,7) 1 nên theo định
x 3(mod(13)
lí Thặng dư Trung hoa hệ trên có 1 nghiệm là a
3
N jb j a j
j 1
Trong đó:
n1 7, N1 11.13143, n2 11, N2 13.7 91, n3 13, N3 7.11 77
Nên ta có:
N1.b1 3b1 1(mod 7) b1 2
Tương tự b2 4, b3 1
Từ đó a 143.(2).5 91.4.7 77.(1).3 887 .
Tất cả các nghiệm của hệ có dạng b 887 1001t (t ) .
Vậy số cần tìm là 887.
2006
17 k
Bài toán 3: Tính tổng S
k 4 11
Lời giải:
a
Nhận xét 1: Nếu a r (mod b) với a, b, r ,0 r b 1 thì
b
ar
b
Nhận xét 2: Vì 1710 1(mod11) nên tập B {1710 k ,1710 k 1,...,710 k 9 } là hệ thặng dư
mod 11 nó là một hoán vị của tập {1,2,…,10}.
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 4
Nhận xét 3: Mỗi i
[0;9] gọi ni là số phần tử của tập hợp
Di {k | 4 k 2006, k i(mod10)} kiểm tra ta dễ thấy:
n4 n5 n6 201, và n0 n1 n2 n3 n7 n8 n9 200
Từ các nhận xét suy ra:
2006
2006
17
11
k 1
k
17k (n0 6n1 3n2 7n3 9n4 10n5 5n6 8n7 4n8 2n9 )
k 4
11
10
17 2003 1
17 .
(9 10 15) 200 j
17 1
j 1
4
11
17
259905
176
2007
172007 259905
Vậy S
.
176
Bài toán 4: Cho đa thức P x x3 11x 2 87 x m trong đó m
. Chứng minh rằng
với mọi m tồn tại số nguyên n sao cho P n 191 .
Lời giải:
Bồ đề: Cho p , p 2 mod 3 , x, y , x3 y 3 mod p x y mod p
Thật vậy:
Nếu x 0 mod p y3 0 mod p y 0 mod p x y mod p
Nếu x p y p , do p 2 mod 3 p 3k 2 k
Định lý số dư Trung Hoa
, theo định lý Fécma:
GVHD: TS Trần Nam Dũng
Trang 5
x p 1 x3k 1 1 mod p , y p 1 y 3k 1 1 mod p
x3k 1 y 3k 1 mod p theo giả thiết x3 y 3 mod p x3k y 3k mod p
Vậy y3k 1 x.x3 k x.y 3 k mod p x y mod p do y, p 1
Trở lại bài toán: P n n3 11n2 87n m
Ta chứng minh P n1 P n2 mod191 với n1 , n2
thì n1 n2 mod191 .
Thật vậy do
P n1 P n2 mod 191 27 P n1 27 P n2 mod 191
3n1 1 18.191n1 113 27m 3n2 1 18.191n2 113 27m
3
3n1 1 3n2 1
3
3
3
mod 191
mod 191
Theo bổ đề ta có:
3n1 1 3n2 1 mod191 n1 n2 mod191
// do 27,191 3,191 1
n1 , n2 A 1, 2,3,...,191 A là hệ đồng dư đầy đủ mod 191 thỏa mãn n1 n2 thì
P n1 P n2 mod 191 A* P 1 , P 2 ,..., P 191 là hệ thặng dư đầy đủ mod
191
Từ đó suy ra n A 1, 2,...,191 sao cho P n 191 mod 191 P n 191 .
Vậy với mọi m tồn tại số nguyên n sao cho P n 191 .
Bài toán 5: Chứng minh rằng với mọi số nguyên dương n, luôn tồn tại một tập hợp S
gồm n phần tử sao cho bất kì một tập con nào của S cũng có tổng các phần tử là lũy
thừa của một số tự nhiên.
Lời giải:
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 6
Giả sử rằng S a1 , a2 ,..., an1 , an
Ta chọn các số ai như sau
a1 1b1 12b2 3b3...k bk
a2 1b1 2b2 13b3...k bk
…
ai 1b1 2b2 ... i 1 i1 ibi 1 i 1 i1 ...k bk
b
b
...
an 1b1 2b2 3b3 ...n bn 1 ...k bk
Trong đó k là số nguyên dương thỏa mãn k 1 2 3 ... n
Giả sử T ai1 , ai 2 ,..., aim S m n
Khi đó ta có:
b 1
b 1
b 1
ai1 ai 2 ... aim 1b1 2b2 ...i1 i1 ...k bk 1b1 2b2 ...i2i2 ...k bk ... 1b1 2b2 ...bk imim ...k bk
1b1 2b2 ...k bk i1 i2 ... im
1b1 2b2 ... i1 i2 ... im i1i2 ...im
b
...k bk
Ta sẽ chọn ra k số nguyên tố phân biệt p1 , p2 ,..., pn thỏa mãn hệ sau
p1 b1 1, p1 b2 , b3 ,..., bk
p2 b2 1, p2 b1 , b3 ,..., bk
…
pk bk 1, pk b1 , b2 ,..., bk 1
Hiển nhiên chọn được theo định lý phần dư Trung Hoa, khi đó dễ thấy
aa1 ai2 ... aim A
pi1i2 im
Là lũy thừa của một số tự nhiên, trong đó
A 11
b pi1i2 ...im
b pi1i2 ...im
.2 2
... i1 i2 ... im i1i2...im ...k
b
bk pi1i2 ...im
và hiển nhiên A nguyên (bài toán được chứng minh).
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 7
3.2 Sử dụng hệ thặng dư trong phương trình Đi Ô Phăng bậc nhất
Bài toán 1: Cho a, b
tại x, y
, a, b 1 . Số nguyên dương n được gọi là đẹp nếu tồn
sao cho: n ax by .
1, Chứng minh rằng: n ab là số xấu lớn nhất.
2, Chứng minh rằng nếu n I a b; ab , n là đẹp số ab a b n là xấu.
3, Tìm số lượng các số xấu.
Lời giải:
1. Ta chứng minh n ab là số xấu lớn nhất.
Giả sử n ab đẹp phương trình ab ax by * có nghiệm nguyên dương
x bx
ax b
x b
do a, b 1 y a y ay1 x1; y1
by a
1
Khi đó phương trình (*) ab( x1 y1 ) ab x1 y1 1 (Vô lí) .Vậy điều
giả sử sai tức là n ab là số xấu.
Ta chứng minh mọi n ab thì phương trình n ax by có nghiệm nguyên
dương.
Do a, b 1 A aii 1 là HĐĐ mod b x 1, 2,..., b sao cho
b
ax n mod b n ax by y
ax by m
1 x b n ax n ab 0 by 0 y
Vậy tồn tại x, y
do
.
: ax by n n ab đều là số đẹp.
Từ hai điều trên ta thấy n ab là số xấu lớn nhất.
2. Chứng minh " " n là đẹp thì x, y
: ax by n .
Khi đó ab a b n ab a b (ax by) ab ( x 1)a ( y 1)b **
Giả sử ab a b n là số đẹp x1; y1
Định lý số dư Trung Hoa
: ab a b n ax1 by1 ***
GVHD: TS Trần Nam Dũng
Trang 8
Từ (**) và (***) ta có ab ( x x1 1)a ( y y1 1)b
mà ( x x1 1)
;( y y1 1)
Chứng minh " " x, y
n ab là số đẹp (vô lí).
: ax by n thì n là đẹp.
Đặt k ab a b n .Do a, b 1 A aii 1 là HĐĐ
b
mod b x 1, 2,..., b sao cho
ax b mod b k ax 0 mod b k ax by ax by k y
.
Theo giả thiết k là số xấu nên k ab y 0 .
Khi đó ta có n ab a b k ab a b (ax by ) a (b 1 x) b(1 y ) đẹp
do (b 1 x)
, (1 y )
.
3. Theo phần (1) mọi n ab đều là số đẹp.
n 1; a b 1 đều là số xấu ,trong đoạn này có tất cả a b 1 số xấu.
n a b; ab thì ab a b n a b; ab theo phần (2) ta thấy nếu
lấy một số đẹp thuộc đoạn a b; ab thì có một số xấu cũng thuộc đoạn
a b; ab , từ đó
số xấu trong đoạn a b; ab là:
Vậy tổng cộng có tất cả : a b a
Bài toán 2: Cho a, b, c
là đẹp nếu tồn tại x, y, z
ab a b 1
2
ab a b 1 ab a b 1
số số xấu.
2
2
, a, b b, c c, a 1 . Số nguyên dương n được gọi
: n bcx cay abz . Chứng minh rằng : n 2abc là số
xấu lớn nhất.
Lời giải:
Ta chứng minh n 2abc là số xấu lớn nhất.
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 9
Giả sử n 2abc đẹp phương trình 2abc bcx cay abz * có nghiệm nguyên
bcx a
x a x ax1
dương. cay b do a, b b, c c, a 1 y b y by1 x1 ; y1 ; z1
abz c
z c
z cz
1
Khi đó phương trình (*) abc( x1 y1 z1 ) 2abc x1 y1 z1 2 Vô lí .
Vậy điều giả sử là sai tức là n 2abc là số xấu.
Ta chứng minh mọi n 2abc thì phương trình n bcx cay abz có nghiệm nguyên
dương.
Do (a, b) (b, c) (c, a) 1 A n abii 1 là hệ đầy đủ mod c z 1, 2,..., c
c
sao cho n abz 0 mod c n abz tc t
mà n 2abc t
tức là t
Vậy x, y
.
n abc 2abc abc
ab .
c
c
, t ab .
: bx ay t
Từ đó ta có: n abz (bx ay )c n bcx cay abz n 2abc đều là số đẹp.
Từ hai điều trên ta thấy n 2abc là số xấu lớn nhất.
3.3 [Bài toán] Phương trình nghiệm nguyên, định lý phần dư Trung Hoa
Bài toán: Chứng minh rằng nếu p1 , p2 ,..., pn là các số nguyên tố phân biệt thì phương
n
trình x1p1 x2p2 ... xnp11 xnpn có vô số nghiệm nguyên dương x1 , x2 ,..., xn .
Lời giải:
Ta có đẳng thức sau
n 1
k
n 1 ... n 1 n 1
k
k
k 1
n 1
Khi đó ta chọn
k
k
k
k 1
x1 n 1 p1 , x2 n 1 p2 ,..., xn 1 n 1 pn1 , xn n 1 pn
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 10
n
Thì phương trình trở thành x1p1 x2p2 ... xnp11 xnpn
Vậy nếu ta chỉ ra được số nguyên dương k sao cho x1 , x2 ,..., xn đều nguyên thì ta có được
điều phải chứng minh.
Mà điều này tương đương với hệ sau có nghiệm
k 0 mod p1
k 0 mod p2
...
k 0 mod p
n 1
k 1 mod pn
Điều này luôn đúng theo định lý phần dư Trung Hoa vì p1 , p2 ,..., pn là các số nguyên tố
phân biệt.
3.4 [Bài toán] Định lý phần dư Trung Hoa
Bài toán 1:
a, (IMO 1989) Chứng minh rằng với mọi số nguyên dương n bất kỳ, luôn tồn tại n số
nguyên dương liên tiếp mà trong đó không có số nào là lũy thừa của một số nguyên
tố.
b, (Đề nghị Olympic 30-4 toán 10 năm 2013 THPT Chuyên Trần Hưng Đạo, Bình
Thuận) Chứng minh rằng với mọi số nguyên dương n tồn tại n số nguyên dương liện
tiếp sao cho bất kỳ số nào trong chúng cũng chia hết cho n số nguyên tố liên tiếp.
Lời giải:
a. Cách 1:
Xét hệ đồng dư tuyến tính:
x 1 (mod p1p 2 )
x 2 (mod p p )
3 4
x 3 (mod p5 p 6 )
...
x n (mod p 2 n 1p 2 n )
trong đó p1 , p2 ,..., p2 n là các số nguyên tố phân biệt.
Theo định lý phần dư Trung Hoa thì tồn tại x0 thõa hệ trên.
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 11
Khi đó:
p1 p2 | xo 1
p3 p4 | xo 2
...
p2 n 1 p2 n | xo n
Như vậy dãy số xo 1, xo 2,..., xo n gồm n số nguyên dương liên tiếp mà trong
đó không có số nào là lũy thừa của một số nguyên tố.
Cách 2:
Mỗi n
*
xét n số nguyên tố phân biệt p1 , p2 ,..., pn
x p1 1 mod p12
x p2 1 mod p2 2
Xét hệ phương trình
Theo định lý thặng dư Trung Hoa thì
....
2
x pn 1 mod pn
hệ phương trình trên có nghiệm a : a pi 1 mod pi2 i 1, n . Từ đó suy
ra các số a 1, a 2,..., a n đề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ố.
b. Xét hệ đồng dư tuyến tính:
x 1 (mod p1p 2 ...p n )
x 2 (mod p p ...p )
n 1 n 2
2n
x 3 (mod p 2 n 1p 2 n 2 ...p3n )
...
x n (mod p n2 n 1p n2 n 2 ...p n2 )
Trong đó pi P, i = 1,2,..,n 2 .Với kí hiệu pi , pi 1 được coi là hai số nguyên tố
liên tiếp.
Theo định lý phần dư Trung Hoa thì tồn tại x0 thõa hệ trên.
Khi đó:
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 12
p1p 2 ...p n | xo 1
p n 1p n 2 ...p 2 n | xo 2
...
p n2 n 1p n2 n 2 ...p n2 | xo n
Như vậy dãy số xo 1, xo 2,..., xo n gồm n số nguyên dương liên tiếp mà trong
đó số nào cũng chia hết cho n số nguyên tố liên tiếp.
Bài toán 2: Với mỗi cặp số nguyên dương nguyên tố cùng nhau (p, q) đặt
p 1 q
p 2q
S ...
p
q p
trong đó x là số nguyên lớn nhất không vượt quá x. hãy xác định các giá trị của p,
q để S là một số nguyên tố.
Lời giải:
Với mỗi a
đặt {a} a a khi đó với k
ta có
kq rk
ở đây rk là số dư trong phép chia kq cho p do vậy:
p p
S
0 rk p 1 ,
rp 1
q 2q
( p 1)q r1 r2
...
...
p p
p
p
p p
Vì ( p, q) 1 rk 0, k 1, 2,..., p 1 từ đó ta thấy tập A {r , r2 ,...., rp 1} chính
1
là một hoán vị của tập A {1,2,....,p 1} thật vậy ngược lại:
1 j i p 2
1 j i p 2
vô lí
i, j {1,2,..., p 1}, i j mà ri r j
( j 1)q p
j i p
rp 1 1 2 ... p 1 p 1
r r
( p 1)(q 1)
S
Từ đó 1 2 ...
(1)
p
p
p
p
2
2
Từ (1) để S là số nguyên tố cần có p 1, q 1 và ít nhất 1 trong 2 số p, q lẻ.
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 13
Trường hợp 1: p,q cùng là số lẻ p, q 3, p q do ( p, q) 1 , kết hợp với (1)
S là số chẵn lớn hơn 2 S không là số nguyên tố
Trường hợp 2: p là số chẵn q là số lẻ.
( p , q ) 1
p 1 1
p 2
q 1
2
q 2h 1(h )
S
(2)
q 3
( p , q ) 1
(t , t 2(mod 3))
p t 1
p 1
q 1 1
2
ở đây kí hiệu là tập số nguyên tố.
Trường hợp 3: q là số chẵn p là số lẻ do tính đối của p, q của biểu thức xác định S theo
trường hợp 2:
p 2m 1
q 2
q 3
p n 1
(m )
(3)
(n , n 2(mod 3))
Vậy tóm lại tất cả các giá trị p, q cần tìm là các cặp xác định ở (2) và (3).
Bài toán 3: Chứng minh rằng với mọi số nguyên dương n, tồn tại số tự nhiên gồm n
chữ số đều lẻ và nó chia hết cho 5n .
Lời giải:
Xét số a1a2 ...an 5n.a thỏa mãn ( với ai
lẻ , i 1, 2,..., n và a
)
Ta chứng minh bài toán bằng quy nạp toán học.
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 14
Với n 1 a1 5 51 Vậy mệnh đề đúng với n=1.
Giả sử mệnh đề đúng với n a1a2 ...an 5n.a ta cần chứng minh mệnh đề đúng với n+1.
Xét 5 số sau đây
1a1a2 ...an 5n 1.2n a
3a1a2 ...an 5n 3.2n a
5a1a2 ...an 5n 5.2n a
7a1a2 ...an 5n 7.2n a
9a1a2 ...an 5n 9.2n a
Do B 1,3,5,7,9 là hệ thặng dư đầy đủ mod 5
B* 1.2n a,3.2n a,5.2n a,7.2n a,9.2n a cũng là hệ thặng dư đầy đủ mod 5 nên
tồn tại một số duy nhất B* chia hết cho 5.
Trong 5 số 1a1a2 ...an , 3a1a2 ...an , 5a1a2 ...an , 7a1a2 ...an , 9a1a2 ...an có một số duy nhất
chia hết cho 5n1 mà số này gồm n+1 chữ số lẻ . vậy mệnh đề đúng với n+1.
Theo nguyên lý quy nạp, mệnh đề đúng với mọi n . Vậy với mọi số nguyên dương n, tồn
tại số tự nhiên gồm n chữ số đều lẻ và nó chia hết cho 5n .
Bài toán 4: Cho hai số nguyên dương p, q nguyên tố cùng nhau. Chứng minh rằng
tồn tại số nguyên k sao cho ( pq 1)n k 1 là hợp số với mọi số nguyên dương n.
Lời giải:
Ta có (p, q) 1 (vì: p,q nguyên tố cùng nhau) nên theo định lí phần dư Trung Hoa, tồn tại
k 1 (mod p)
số nguyên k thoả mãn:
k 1 (mod q)
Khi đó:
o Nếu n chẵn thì ( pq 1)n 1(mod q) ( pq 1)n k 1(mod q) ( pq 1)n k 1 q
o Nếu n lẻ thì ( pq 1)n 1(mod p) ( pq 1) n k 1(mod p) ( pq 1) n k 1 p
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 15
Vậy ( pq 1)n k 1 là hợp số với mọi số nguyên dương n.
Nhận xét:
Chứng minh trên thật gọn gàng nhờ vào việc sử dụng định lí đồng dư Trung Hoa. Mấu
chốt của vấn đề ở đây là chúng ta phải thấy rằng để ( pq 1)n k 1 là hợp số ta cần chỉ ra
( pq 1)n k 1 chia hết cho p hoặc q, khi phân tích tính chẵn lẻ của n ta dễ dàng thấy được
sự xuất hiện của hệ
k 1(mod p )
k 1(mod q ) .
Bài toán 5: Chứng minh rằng với mọi số tự nhiên n, luôn tồn tại n số tự nhiên liên tiếp
sao cho bất kì số nào trong các số đó cũng đều là hợp số.
Lời giải:
Nhận xét: n số tự nhiên liên tiếp có dạng a 1, a 2,..., a n . Các số này là hợp số nếu
tồn tại các số nguyên dương p1 , p2 ,..., pn khác 1 sao cho a i pi2 . Suy ra a là nghiệm
của hệ phương trình
x i mod pi2
i 1, n
x i mod pi2
Theo định lí đồng dư Trung Hoa hệ
có nghiệm khi p1 , p2 ,..., pn đôi một
i 1, n
nguyên tố cùng nhau.
Do đó ta chỉ cần chọn p1 , p2 ,..., pn là n số nguyên tố phân biệt.
Bài toán 6: Cho là tập S p1 , p2 ,..., pk gồm k số nguyên tố phân biệt, và f ( x ) là đa
thức với hệ số nguyên sao cho với mọi số nguyên dương n đều tồn tại pi trong S sao
cho pi | f (n) . Chứng minh rằng tồn tại i sao cho pi | f (n), n N * .
Lời giải:
Giả sử không tồn tại i sao cho pi | f (n), n N * , suy ra với mọi i 1, k luôn tồn tại ai
sao cho pi
f (a i ) .
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 16
x ai mod pi
Mặt khác theo định lý số dư Trung Hoa : tồn tại số tự nhiên x thỏa mãn
i 1, k
f x f ai mod pi
do đó
hay pi
i 1, k
f ( x), i 1, k ( mâu thuẫn)
Điều phải chứng minh.
3.5 [Bài toán] Ứng dụng định lý phần dư Trung Hoa
Bài toán 1: Chứng minh rằng với mọi số nguyên dương n luôn tồn tại một dãy gồm n số
nguyên liên tiếp sao cho bất kì số nào trong dãy cũng đều có ước dạng 2k 1.
Lời giải:
Bổ đề: Với m, n
là các số nguyên dương và a là số nguyên dương khác 1 thì ta có :
gcd(a m 1, a n 1) a gcd(m,n) 1
Chứng minh bổ đề :
m dm '
gcd(m',n')=1
Đặt d gcd( m, n) và
n dn '
Ta có:
a m 1 a dm ' 1 a d 1
và
a n 1 a dn ' 1 a d 1
Gọi
d ' gcd(a m 1, a n 1) thì d '
a d 1 (1)
vì d gcd(m,n) nên theo định lý Bezout thì tồn tại hai số nguyên dương x,y sao cho
mx ny 1 .
Từ đó:
a mx 1 a m 1 d '
Và
a ny 1 a n 1 d '
Do đó:
Định lý số dư Trung Hoa
GVHD: TS Trần Nam Dũng
Trang 17
a
mx
1 a ny 1 d ' a ny a mx ny 1 d '
a ny a d 1 d '
Nhưng vì a ny 1 d ' d ' a ny 1
ad 1 d '
nên
(2)
Từ (1) và (2) suy ra: a d 1 d '
Bổ đề chứng minh hoàn tất.
Trở lại bài toán, Xét hệ đồng dư tuyến tính:
x 1 (mod 2 p1 1)
p
x 2 (mod 2 2 1)
...
x n (mod 2 pn 1)
với p1 , p2 ,...., pn là các số nguyên tố phân biệt.
Theo bổ đề ta có: gcd 2 pi 1, 2 j 1 2
p
gcd pi , p j
1 2 1 1 i j; i, j 1, 2,..., n
Từ đó theo định lý phần dư Trung Hoa thì hệ này có nghiệm.
Suy ra điều cần chứng minh.
Bài toán 2: Chứng minh rằng với mọi số nguyên dương n luôn tồn tại n số
nguyên a1 , a2 ,..., an sao cho ai a j là lũy thừa của một số tự nhiên với số mũ lớn
hơn 1 i, j 1, 2,..., n .
Lời giải:
Ta chọn các số như sau:
a1 1x1 1.2 x2 .3x3 ... 2n x2 n
x
a2 1x1.2 x2 1.3x3 ... 2n 2 n
......
x2 n 1
x1 1 x2 x3
an 1 .2 .3 ... 2n
Khi đó thì:
ai a j 1x1.2 x2 ...i xi 1... 2n
x2 n
1x1.2 x2 ... j
1x1.2 x2 ... i j i j ... 2n
x
1
x j 1
... 2n 2 n 1x1.2 x2 ... 2n 2 n i j
x
x
x2 n
Xét các số nguyên tố p1 , p2 ,..., p2 n phân biệt.
Định lý phần dư Trung Hoa
GVHD: TS. Trần Nam Dũng
Trang 18
Xét các hệ đồng dư tuyến tính
x1 1 mod p1
x1 0 mod pk k 2,3,..., 2n 1, 2n
x2 1 mod p2
x2 0 mod pk k 1,3, 4,..., 2n
xi j 1 mod pi j
xi j 0 mod pk k 1, 2,...,i j 1,i j 1,..., 2n
x2 n 1 mod p2 n
x2 n 0 mod pk k 1, 2,..., 2n 1
Theo định lý phần dư Trung Hoa thì các hệ này chắc chắn có nghiệm
Từ đó suy ra:
x 1
x
x1 x2
, ,..., k
,..., 2 n , k 1, 2 n
p1 p2
pk
p2 n
Khi đó:
ai a j 1 .2 ... i j
x1
x2
xi j 1
... 2n
x2 n
xi j 1
x2 n
x2
x1
1 pi j . 2 pi j .... i j pi j ... 2n pi j
pi j
là lũy thừa của một số tự nhiên. (điều phải chứng minh)
Bài toán 3: Cho p là số nguyên tố. chứng minh rằng tồn tại một bội số của p sao cho
10 chữ số tận cùng của nó đôi một khác nhau.
Lời giải:
Nếu p 2 thì hiển nhiên thì luôn tồn tại 1 số thỏa bài toán
Nếu p 5 thì hiển nhiên thì luôn tồn tại 1 số thỏa bài toán
Xét p 2;5
x ao a1...a9 mod1010
Xét hệ đồng dư tuyến tính
trong đó ai đôi một khác nhau và
x 0 mod p
ai 0,1, 2,....,9
Định lý phần dư Trung Hoa
GVHD: TS. Trần Nam Dũng