Bài 3 Thặng dư Trung Hoa | Đại học Kinh Doanh và Công Nghệ Hà Nội

BÀI 3. THẶNG DƯ TRUNG HOA 1. Lý thuyết 1.1. Định lý Bezout
1.2. Phương trình đồng dư bậc nhất.
1.3. Hệ phương trình đồng dư bậc nhất.
1.4. Thặng dư Trung Hoa mở rộng
x  r (mod m ) 1 1 
x  r (mod m )
+Cho các số nguyên m ,m ,..., m 2 2 1 2
k . Xét hệ ...................... 
x  r (mod m )  k k
+Điều kiện có nghiệm r  r (mod(m , m )) i j i j
+Khi đó, hệ có nghiệm duy nhất mod[m , m ,..., m ] 1 2 k .
2. Một số dạng toán
2.1. Trong các bài toán số học
2.1.1. Bài toán cơ bản:
Trước hết bắt đầu bằng một số bài toán tìm nghiệm để nắm được công thức nghiệm. x 1(mod 2) 
Bài 1. Giải hệ sau : x  2(mod 3) x  3(mod5)  Lời giải
+Ta có: M  2.3.5  30 M M M + 1 M 15, M     1 ; 1 M 10, M    1 ; 1 M 6, M    1 1 1 2 2 2 3 3 3 5
+Nghiệm của hệ x  15  20 18  7(mod 30)
Bài 2. Tìm bội tự nhiên nhỏ nhất của 6 mà khi nó chia cho 5; 7 có số dư tương ứng là 2; 3 Lời giải x  0(mod 2)  x  0(mod 3)
+Số x thỏa mãn là nghiệm của hệ  x  2(mod 5)  x  3(mod7)
+Chọn ra số nhỏ nhất trong lớp đồng dư mod 210 .
Bài 3. Giải phương trình sau: 2 x  1(mod15) 1 Lời giải 2 x 1(mod3) + 2
x  1(mod15)   2 x 1(mod5)
x  1(mod3) x  1(mod 3)
x  1(mod 3) x  1(mod 3) +Ta có 4 hệ đồng dư  ;  ;  ; 
x  1(mod5) x  1
 (mod 5) x 1(mod5) x  1(mod5) +Vậy hệ có 4 nghiệm. Câu hỏi đặt ra: 2 1 x  1(mod m), k
m  p ... tp
p có bao nhiêu nghiệm? Câu trả lời sẽ có ở phần 1 t tiếp theo.
Với những bài toán chỉ ra sự tồn tại (không cần chỉ ra chính xác nghiệm) thì việc sử
dụng công cụ thặng dư Trung Hoa rất hữu hiệu.
2.1.2. Bài toán chứng minh sự tồn tại.
Bài 1.Với mỗi số nguyên dương n , tồn tại n số nguyên dương liên tiếp
Xét các số liên tiếp a 1, a  2,..., a  n . Việc lựa chọn pi thỏa mãn yêu cầu bài toán tạo
nên đặc thù riêng cho từng bài toán.
1. Tất cả các số đều là hợp số
Phân tích: Chọn số nguyên tố
Để thỏa mãn yêu cầu bài toán ta cần chỉ ra tồn tại a sao cho a  i p  i   1,n i
a  1(mod p ) 1 
a  2(mod p )
Nghĩa là a là nghiệm của hệ đồng dư 2  ....................... 
a  n(mod p )  n
Chỉ cần chọn p , p ,..., p 1 2
n đôi một nguyên tố cùng nhau (thôi tốt nhất chọn số nguyên tố cho đảm bảo dễ dàng).
Lưu ý: Có thể xảy ra tình huống a  i  p ??? i
Lời giải: Các em hãy trình bày lời giải theo sự phân tích ở trên.
2. Mỗi số không là lũy thừa của một số nguyên.
Phân tích: Chọn số bình phương của số nguyên tố
Để thỏa mãn yêu cầu thì chỉ ra tồn tại số nguyên a : s
a  i  k i   1,n
Hay có thể tìm điều kiện dễ thỏa nhất là tồn tại số nguyên tố p : v a  i  i ( ) 1 . i p Cách chọn phụ hợp là 2
a  i  p (mod p ), i 1, n và a  i  p . i i i 2
Lời giải: Các em tự trình bày lời giải theo sự phân tích ở trên.
3. Mỗi số đều có ước dạng 2k 1
Phân tích: Chọn các số Mersen đôi một nguyên tố cùng nhau.
Để thỏa yêu cầu bài toán chỉ ra tồn tại a : a  i có ước dạng 2 ik 1 .
Đến đây ta nghĩ tới việc chọn p  2ki 1 , chọn các số nguyên tố thì sẽ hơi khó khăn nên ta i
nghĩ tới các số Mersen (vì trong định lý thặng dư Trung Hoa chỉ cần các số đôi một nguyên tố cùng nhau)
Lưu ý: ( p , p )  1  (k , k )  1 i j i j
Lời giải: Dành cho các em.
4. Mỗi số đều có ước là lũy thừa bậc s của một số nguyên dương lớn hơn 1 , với s là số nguyên dương cho trước.
Phân tích: Chọn các số lũy thừa bậc s của số Fecmat.
Chỉ ra tồn tại a : s a  i p  i
Vấn đề: Kiểm soát ( s p , s p )  1 n  i j
ta nghĩ tới các số Fecmat 2 F  2 1 n Lưu ý: ( s F , s F )  1 i j
Lời giải: Các em tự trình bày
5. Mỗi số đều chia hết cho n số nguyên tố liên tiếp
Phân tích: Tích của n số nguyên tố liên tiếp
Chỉ ra tồn tại a : a  i p  p ...p ni 1  ni 2ni2
Lời giải: Các em tự trình bày lời giải
6. Mỗi số đều có ít nhất k ước nguyên tố phân biệt , với k là số nguyên dương cho trước.
7. Mỗi số đều có ít nhất một ước là số chính phương.
8. (30-04-2019)Ta gọi e(n) là tổng của các số mũ của tất cả các ước nguyên tố của n
8.1. Chứng minh rằng tồn tại 1000 số nguyên dương liên tiếp mà mỗi số đều có số mũ không nhỏ hơn 10
8.2. Tồn tại 1000 số nguyên dương liên tiếp trong đó có đúng 500 số có số mũ không nhỏ hơn 10
Bài 2.Với mỗi số nguyên dương, tồn tại tập A  {a , a ,..., a } 1 2 n
1. Là một cấp số cộng , số hạng đều là lũy thừa của một số tự nhiên với số mũ lớn hơn 1
Phân tích: Các số nguyên tố p , p ,..., p 1 2 n 3 {1, 2,..., }
n  {a, 2a,..., }
na là cấp số cộng.
Để thỏa mãn thì cần có: k k k k 1  k p 2 k3
a  2 .3 ... kn n và 2 3
ia  2 .3 ... i i ... n
n  (....) i .
Nghĩa là tồn tại k , k ,..., k     2 3
n : k , k , ..., k 1,..., k p i 2, n . 2 3 i n i
+Các số ki tồn tại như thế nào?
Lời giải: Các em tự hoàn thiện
2.Với mọi tập con của Z , tồn tại số nguyên dương m sao cho các phần tử của mA đều là
lũy thừa của một số tự nhiên.
Phân tích: Giống như bài 2.1.
3. Tổng các phần tử của tập con khác rỗng của A là một lũy thừa. Phân tích
Xét tập S  {x ; x ;...; x } n 1 2 n
có 2 1 tập con khác rỗng.
Đặt S , S ,..., S 1 2
là tổng các phần tử của các tập con của S 2n 1 
Theo bài 2.2 tồn tại m : mS , mS ,..., mS 1 2 đều là lũy thừa. 2n 1 
Khi đó tập X  {mx , mx ,..., mx } 1 2 n
thỏa mãn yêu cầu bài toán.
Lời giải: Các em tự hoàn thiện 4. a  a i
j là lũy thừa của số tự nhiên với số mũ lớn hơn 1
Phân tích: Chọn các số nguyên tố p , p ,..., p (k  2n) 1 2 k Chọn x x 1 x 1 x 2
a  1 .2x ... kx
k .i . Khi đó 1 2
a  a  1 .2 ...(i  j) ij ... kx k . i i j Để thỏa mãn: x x 1 x  x p 1 2
a  a  1 .2 ...(i  j) i j ... k
k  (...) ij . i j
+Các số xi tồn tại như thế nào?
5. Là một cấp số cộng có công sai d , mỗi số hạng có ít nhất k ước nguyên tố. Với k, d là
các số nguyên dương cho trước.
6. Luôn tồn tại n số liên tiếp của dãy a  b, a  2b,..., a  ....
nb đều là hợp số . Với a,b là các
số nguyên dương cho trước. Bài 3.
1. Cho ( p, q) 1 . CMR tồn tại số nguyên k sao cho ( 1)n pq
k 1 là hợp số với n     Phân tích Ta thấy : (
1)n  (1)n pq k
k(mod p),(mod q)
Nếu n chẵn thì chọn k  1(mod p), mod(q) 4
Nếu n lẻ thì chọn k  1(mod p),(mod q)
Lời giải: Các em học sinh tự giải
2. Chứng minh rằng tồn tại vô hạn số nguyên dương chẵn k sao cho mọi số nguyên tố p thì 2
p  k là hợp số. Phân tích
+ p  2 luôn đúng với mọi số nguyên dương chẵn + p  3 để 2
k  p  k  9 là hợp số thì chọn k  5(mod 7) + 2
p  3  p  1(mod 3) , chọn k  2(mod 3)
Số nguyên k được chọn thế nào để thỏa mãn yêu cầu bài toán.
Lời giải: Dành cho các em học sinh.
3. Cho số nguyên tố p . Chứng minh 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.
Phân tích : Số cần tìm 10
x  a a ...a (mod10 ); x  0(mod p) 1 2 10 +Xét p {2;5} +Xét p {2;5}
Lời giải: Các em tự trình bày lời giải
4. Cho số nguyên a có ước nguyên tố dạng 4k 1 . Chứng minh rằng tồn tại  2 4 2
b   : b 1| a  a
2.1.3.Bài toán kết hợp với tính chất của số Femat
Bài 1.Chứng minh rằng tồn tại số nguyên dương k sao cho 2 .nk 1 là hợp số với mọi số nguyên dương n
Phân tích: Giả sử 2
n  2 .l  2  (2 m m n
)l  1(mod 2m 1  F ) m
Tìm k : k 1(mod F ) m  m
Lưu ý: F , F , F , F , F F  . p q 0 1 2 3 4 là số nguyên tố và 5 .
Chọn k như thế nào để thỏa mãn.
Bài 2.Cho trước các số nguyên dương ,
n k . Chứng minh rằng tồn tại n số nguyên dương
liên tiếp mà mỗi số đều có ước là lũy thừa bậc k .
Phân tích: Chọn các số lũy thừa bậc s của số Fecmat.
Chỉ ra tồn tại a : k a  i p  i 5
Vấn đề: Kiểm soát ( k p , k p )  1 n  i j
ta nghĩ tới các số Fecmat 2 F  2 1 n Lưu ý: ( k F , k F )  1 i j Bài 3.
1. Tìm tất cả các số n   n  sao cho tồn tại 2
m : 2 1| m  9
2. Tìm tất cả các số tự nhiên n thỏa mãn 2n 1 3
 và tồn tại số nguyên dương m để 2n 1 2 | 4m 1 3
2.1.4. Bài toán chia hết
Bài 1.Chứng minh rằng phương trình 2 2
x  34y  1(mod m) có nghiệm với mọi m   Phân tích Nếu 2 2 ( ;
m 3)  1 x  34y  (x  5y)(x  5y)  (3y 1)(3y 1)(mod ) m Nếu 2 2 ( ;
m 5)  1 x  34 y  (x  3y)(x  3y)  (5y 1)(5y 1)(mod ) m
Bài 2. Cho các số nguyên dương thỏa mãn n  | 2021n a n
 n . Tìm a .
Bài 3. Chứng minh rằng với mọi số nguyên dương N  p .p ...p 1 2
2021 là ước của vô số số có
dạng a 1  ( 1)a a a Bài 4.
1. Cho số tự nhiên n không có ước chính phương. CMR: n n 2 a 1 n   a 1 n  2. Tìm n n 2 n  1: a
 : a 1 n   a 1 n 
3. Tìm tất cả các số nguyên dương a sao cho n 2 2  | n a n a  n n   5
2.2. Trong các bài toán đa thức
Bài 1. Tìm số nghiệm của phương trình 2
x  2  3x(mod 360) 3
(x 1)(x  2)  0(mod 2 )  Phân tích: 3 2 2
(x 1)(x  2)  0(mod 2 .3 .5)  (x 1)(x  2)  0(mod3 )
(x 1)(x 2)  0(mod5)  Bài 2. Cho 2020 m  2019
. Có bao nhiêu số tự nhiên n  m sao cho n(2n 1)(5n 1) m 
Phân tích: n(2n 1)(5n 1) m
  10n(10n  5)(10n  2)  0(mod ) m ;( , m 10)  1
Bài 3.Cho đa thức hệ số nguyên và tập S  {p , p ,..., p } 1 2
2021 gồm 2021 số nguyên tố phân biệt.
Với mỗi số tự nhiên n , đều tồn tại p  S : P(n) p p  S p P n n   i
 i . CMR tồn tại : | ( ),  . 6
Tổng quát: Thay tập S  {a ,a ,..., a } 1 2 2021 gồm các số nguyên.
Bài 4. Cho đa thức P(x)  (2x 1)(5x 1) . Chứng minh rằng với mọi số nguyên dương n
luôn tồn tại số nguyên dương x sao cho P(x) n 
Câu hỏi đặt ra: Liệu có tồn tại đa thức khác thỏa mãn yêu cầu bài toán?
Bài 5. Chứng minh rằng với mỗi số nguyên dương n , tồn tại k ,k ,..., k 1 2
n đôi một nguyên tố cùng nhau (k 1) k k ...k 1 i sao cho 1 2 n
là tích của hai số nguyên liên tiếp.
2.3. Trong các bài toán tổ hợp
Bài 1. Điểm nguyên 2
A  được gọi là nhìn thấy được từ O nếu trong đoạn OA không có
điểm nguyên nào ngoài O, A . Với mỗi số tự nhiên n , luôn tồn tại một hình vuông n n các
đỉnh nguyên và mọi điểm nguyên bên trong và trên biên của hình vuông đều không nhìn thấy được O .
Bài 2.Ta gọi một tập hợp các số nguyên dương C là tốt nếu với mọi số nguyên dương k đều
tồn tại a,b C : (a  k,b  k)  1 . Giả sử ta có một tập C tốt mà tổng các phần tử bằng 2021 .
Chứng minh rằng có thể loại bỏ đi một số phần tử c C mà tập C vẫn tốt.
Bài 3. Ta gọi một hình vuông là tốt , nếu bốn đỉnh nguyên, đồng thời đoạn thẳng nối tâm O
đến tất cả các điểm nguyên trên biên và trong hình vuông đó chứa ít nhất một điểm nguyên
khác hai đầu mút. Chứng minh rằng mọi số nguyên dương n đều tồn tại một hình vuông tốt
dạng n n .
Bài 4. Một số nguyên dương k có tính chất Tm nếu với mọi số nguyên dương a , đều tồn tại
số nguyên dương n sao cho 1k  2k  ... k
 n  a(mod m)
1. Tìm các số nguyên dương k có tính chất T20
2. Tìm số nguyên dương k nhỏ nhất có tính chất T 15 . 20
Bài 5. Với mỗi số tự nhiên n , luôn tồn tại một tậ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.
Bài 6. Một cấp số cộng có ít nhất 3 số nguyên dương được gọi là chuẩn nếu tích các số hạng
của nó là ước số của số có dạng 2 n 1
1. Chứng minh rằng tồn tại một cấp số cộng chuẩn với công sai bằng 12
2. Hỏi cấp số cộng chuẩn có công sai bằng 12 có nhiều nhất bao nhiêu số hạng.
3. Bài tập tự luyện 7
Bài 1. Ta gọi một số là lũy thừa đúng nếu nó có dạng m
a với a,m nguyên lớn hơn 1. Tìm
tất cả các số nguyên dương n lớn hơn 1 sao cho tồn tại các số nguyên dương b ,b ,...,b 1 2 n
không đồng thời bằng nhau để với mọi k nguyên dương thì  b  k b  k ... b  k 1   2   n  là lũy thừa đúng?
Bài 2. Cho số nguyên dương n . Chứng minh rằng tồn tại vô hạn cặp số nguyên dương
 a,b với a,b  n sao cho n  n n
a  i | b b  2020 ;  a  i | b;  a  i |  b  2020 . i 1  i 1  i 1 
Bài 3. Cho dãy b  b  b  ... 1 2 3
là dãy các số tự nhiên mà mỗi số hạng là tổng của hai số
chính phương. Chứng minh rằng tồn tại vô hạn m sao cho b  b  2021 m 1  m .
Bài 4. Chứng minh rằng với mỗi k nguyên dương, k  2, luôn tồn tại một cấp số cộng a a a 1 2 ,
,..., n các số hữu tỷ, trong đó a ,b 
 , a b  và các số i i  ,i i  1 b b b 1 2 n
a ,b ,a ,b ,...,a ,b 1 1 2 2 n n đều phân biệt.
Bài 5. Tồn tại hay không tập hợp X thoả mãn đồng thời hai điều kiện sau:
i) Tập X gồm 2020 số tự nhiên phân biệt.
ii) Tổng của một số phần tử bất kì trong X đều có dạng luỹ thừa bậc lớn hơn 1 của một số nguyên dương.
Bài 6. Cho tập S   a ,a ,...,a P x  x 1 2
n gồm các số nguyên dương và đa thức     . Biết
rằng với mọi số nguyên dương k đều tồn tại một chỉ số i 1,2,..., 
n sao cho a | P k i   .
Chứng minh rằng tồn tại một chỉ số i a | P k 0 sao cho i
  với mọi số nguyên dương k. 0
Bài 7. Cho tập S   a ,a ,...,a 1 2
n gồm các số nguyên. Chứng minh rằng tồn tại số nguyên b
sao cho tập bS   ba ,ba ,...,ba 1 2
n chứa toàn những lũy thừa bậc lớn hơn 1 của một số nguyên nào đó.
Bài 8. Một số nguyên n được gọi là số “tốt” nếu | n | không phải là số chính phương. Xác
định tất cả các số nguyên m có thể biểu diễn bằng vô hạn cách là tổng của 3 số tốt khác
nhau và tích của chúng là một số chính phương lẻ. 8
Bài 9. Chứng minh rằng tồn tại một dãy tăng {a }
n các số tự nhiên sao cho với mọi k  0 thì dãy {k  a }
n chỉ chứa hữu hạn số nguyên tố.
Bài 10. Chứng minh rằng phương trình 1p p2 p 1 x  x  ... n n p  x
 x có vô số nghiệm (x ; x ;...; x ) 1 2 n 1  n 1 2 n
. Trong đó p , p ,..., p 1 2
n là các số nguyên tố phân biệt. 9