Xem mẫu
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
ĐỊNH LÝ THẶNG DƯ TRUNG HOA VÀ MỘT SỐ
ỨNG DỤNG
Nguyễn Duy Liên
THPT Chuyên Vĩnh Phúc
1 Mở đầu
Định lý thặng dư Trung Hoa là tên người phương Tây đặt thêm, 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 về quân sự, tục kể 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ư mỗi hàng,
từ đó ông tính chính xác quân số đến từng người. Cách điểm quân số đã được ông thể hiện
qua bài thơ sau:
Tam nhân đồng hành thất thập hy.
Ngũ thụ mai hoa trấp nhất chi
Thất tử đoàn viên chính bán nguyệt
Trừ bách linh ngũ tiện đắc chi.
Dịch.
Ba người cùng đi ít bảy chục
Năm cỗ mai hoa hăm mốt cành
Bảy gã xum vầy vừa nửa tháng
Trừ trăm linh năm biết số thành
(Người dịch: Trình Đại Vỹ đời nhà Minh).
Bản chất của bài toán Hàn Tín điểm binh đấy là việc giải hệ phương trình đồng dư bậc
nhất
x ≡ a1 ( mod m1 )
x ≡ a ( mod m )
2 2
....
x ≡ ak ( mod mk )
Trong đó m1 , m2 , . . . , mk là các số nguyên dương đôi một nguyên tố cùng nhau, với bài
toán của Hàn Tín thì k = 3; m1 = 3; m2 = 5; m3 = 7..
55
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Định lý 1 (Định lý Thặng dư Trung Hoa). Cho ksố nguyên dương đôi một nguyên tố cùng
nhau m1 , m2 , . . . , mk và a1 , a2 , . . . , ak là ksố nguyên tùy ý khi đó hệ phương trình đồng dư
tuyến tính.
x ≡ a1 ( mod m1 )
x ≡ a2 ( mod m2 )
....
x ≡ ak ( mod mk )
có nghiệm duy nhất mô đun m1 m2 . . . mk
Chứng minh định lý.
1. Chứng minh sự duy nhất:
Giả sử hệ có hai nghiệm x, y dẫn đến x ≡ y ( mod mi ) , ∀i = 1; k. Vì m1 , m2 , . . . , mk đôi
một nguyên tố cùng nhau nên x ≡ y ( mod m1 m2 . . . mk ).Tức là y và x cùng thuộc một lớp
thặng dư m1 m2 . . . mk .
2. Chứng minh sự tồn tại:
Ta muốn viết các nghiệm như là một tổ hợp tuyến tính của các số a1 , a2 , . . . , ak .Chẳng hạn
x = A1 a1 + A2 a2 + · · · + A k a k
Với các Ai phải tìm thỏa mãn A j ≡ 0 ( mod mi ) , ∀ j 6= i và Ai ≡ 1 ( mod mi ) .
Đặt N1 = m2 m3 . . . mk ; N2 = m1 m3 . . . mk ; . . . ; Ni = m1 m2 . . . mi−1 mi+1 . . . mk ; . . .
Khi đó ( Ni , mi ) = 1 vì (mi , m1 ) = (mi , m2 ) = · · · = (mi , mi−1 ) = (mi , mi+1 ) = · · · =
(mi , mk ) = 1 và m j | Ni , ∀ j 6= i.Vì ( Ni , mi ) = 1 nên tồn tại Ni−1 sao cho Ni Ni−1 ≡ 1 ( mod mi ).
Đến đây ta đặt Ai = Ni Ni−1 thì Ai ≡ 1 ( mod mi ) ; Ai ≡ 0 mod m j , ∀ j 6=
i v`i Ni ≡ 0 mod m j ⇒ Ai ≡ 0 mod m j .
Khi đó x = A1 a1 + A2 a2 + · · · + Ak ak = N1 N1−1 a1 + N2 N2−1 a2 + · · · + Nk Nk−1 ak sẽ thỏa
mãn x ≡ Ni Ni−1 ai ≡ ai ( mod mi )(vì tất cả các thừa số còn lại đều chia hết cho mi )
Nhận xét 1. Đị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 đồng dư tuyến tính. Do đó có thể sử dụng
định lý để giải quyết những 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 về quan hệ đồng dư, quan hệ chia hết. . . , hay đếm số nghiệm của phương trình
đồng dư, chứng minh cho bài toán số học chia hết. Việc sử dụng hợp lý các bộ m1 , m2 , . . . , mk
và bộ a1 , a2 , . . . , ak trong định lý, cho ta nhiều kết quả khá thú vị và từ đó ta có thể lập được
nhiều bài toán hay và khó. Sau đây tôi đưa ra một số ứng dụng của định lý thặng dư Trung
Hoa giải các bài toán số học mà chúng ta thường gặp.
2 Áp dụng vào giải hệ đồng dư tuyến tính
Vận dụng tư tưởng của định lý thặng dư Trung Hoa, chúng ta có thể xây dựngmột
phương pháp hiệu quả nhất trong việc giải hệ phương trình đồng dư tuyến tính.
56
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Cách giải.
• Bước 1: Đặt m = m1 m2 . . . mn = Ni mi với i = 1, 2, 3, . . . , n
• Bước 2: Tìm các nghiệm Ni−1 của phương trình Ni x ≡ 1 ( mod m)
n
• Bước 3: Tìm được một nghiệm của hệ là: x0 = ∑ Ni Ni−1 ai
i =1
• Bước4: Kết luận nghiệm: x ≡ x0 ( mod m)
Ví dụ 1. Đầu tiên ta đến với bài thơ đố dân gian Việt Nam:
Trung Thu.
Trung thu gió mát trăng trong
Phố phương đông đúc, đền lồng sao sa
Rủ nhau đi đếm đèn hoa
Quẩn quanh, quanh quẩn biết là ai hay
Kết năm chẵn số đèn này
Bảy đèn kết lại còn hai ngọn thừa
Chín đèn thì bốn ngọn dư.
Đèn hoa bao ngọn mà ngẩn ngơ lòng.
(Cho biết số đèn trong khoảng 600 đến 700)
Giải. Sử dụng định lý thặng dư Trung Hoa ta giải như sau. Gọi số đèn là
x, ( x ∈ Z, 600 ≤ x ≤ 700) theo bài thơ ta có hệ phương trình đồng dư như sau:
x ≡ 0 ( mod 5)
x ≡ 2 ( mod 7)
x ≡ 4 ( mod 9)
N1 = 7 · 9 = 63 ≡ 3 ( mod 5) ⇒ N1−1 = 2 N2 = 5 · 9 = 45 ≡ 3 ( mod 7) ⇒ N2−1 = 5,
N3 = 5 · 7 = 35 ≡ 8 ( mod 9) ⇒ N3−1 = 8.
Từ đó ta có x = 2.63.0 + 5.45.2 + 8.35.4 = 1570 ≡ 310 ( mod 315) ⇒ x = 310 + 315k, k ∈
Z.
Do x ∈ Z, 600 ≤ x ≤ 700 từ đó suy ra k = 1 và x = 625. Vậy số đèn là 625.
Hoặc giải theo các cụ thời xưa như sau: Gọi x là số đèn (x là số nguyên dương trong
khoảng 600 đến 700 ),x chia hết cho 5, x chia cho 7 dư 2, x chia cho 9 dư 4. Chú ý rằng số dư
khi chia cho 7 và cho 9 đều ít hơn số chia 5 đơn vị, suy ra x + 5 sẽ chia hết cho cả 5;7;9. Bội
số chung nhỏ nhất của 5;7;9 nằm trong khoảng 600 đến 700 là 315 × 2 = 630.
Vậy số đèn sẽ là 630 − 5 = 625. Lời giải rất trong sáng và đẹp đẽ tiếc rằng tôi chưa chuyển
thể về thơ được thôi.
57
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Ví dụ 2. Giải hệ phương trình đồng dư:
x ≡ 2 ( mod 3)
x ≡ 3 ( mod 5)
x ≡ 5 ( mod 7)
Giải. Ta có N1 = 5 · 7 = 35 ≡ 2 ( mod 3) ⇒ N1−1 = 2 N2 = 3 · 7 = 21 ≡ 1 ( mod 5) ⇒
N2−1 = 1 N3 = 3 · 5 = 15 ≡ 1 ( mod 7) ⇒ N3−1 = 1 Từ đó ta có x = 2.35.2 + 1.21.3 + 1.15.5 =
278 ≡ 68 ( mod 105) là nghiệm hệ phương trình.
Ví dụ 3. Giải hệ phương trình đồng dư:
x ≡ 1 ( mod 3)
x ≡ 4 ( mod 5)
x ≡ 1 ( mod 7)
x ≡ 1 ( mod 8)
Giải. Ta có N1 = 5 · 7 · 8 = 280 ≡ 1 ( mod 3) ⇒ N1−1 = 1 N2 = 3 · 7 · 8 = 168 ≡ 3 ( mod 5) ⇒
N2−1 = 2 N3 = 3 · 5 · 8 = 120 ≡ 1 ( mod 7) ⇒ N3−1 = 1 N4 = 3 · 5 · 7 = 105 ≡ 1 ( mod 8) ⇒
N4−1 = 1 Từ đó có x = 1.280.1 + 2.168.4 + 1.120.1 + 1.105.1 = 1849 ≡ 169 ( mod 840) là
nghiệm hệ phương trình
Ví dụ 4. Giải phương trình đồng dư x2 ≡ 1 ( mod 144) .
Giải. Vì 144 = 16 · 9, v`a (16, 9) = 1. Do đó theo địnhlý thặng dư Trung Hoa thì nghiệm của
bài toán chính là nghiệm của hệ phương trình
(
x2 ≡ 1 ( mod 16)
x2 ≡ 1 ( mod 9)
Phương trình x2 ≡ 1 ( mod 16)có 4 nghiệm x ≡ ±1, ±7 ( mod 16)
Phương trình x2 ≡ 1 ( mod 9) có 2 nghiệm x ≡ ±1 ( mod 9) do đó ta có tất cả 8 hệ sau
( (
x ≡ 1 ( mod 16) x ≡ 1 ( mod 16)
(1) , (2)
x ≡ 1 ( mod 9) x ≡ −1 ( mod 9)
( (
x ≡ −1 ( mod 16) x ≡ −1 ( mod 16)
(3) , (4)
x ≡ 1 ( mod 9) x ≡ −1 ( mod 9)
( (
x ≡ 7 ( mod 16) x ≡ 7 ( mod 16)
(5) (6)
x ≡ 1 ( mod 9) x ≡ −1 ( mod 9)
( (
x ≡ −7 ( mod 16) x ≡ −7 ( mod 16)
(7) , (8)
x ≡ 1 ( mod 9) x ≡ −1 ( mod 9)
Cả 8 hệ đều ứng với k = 2 và N1 = 9 ≡ 9 ( mod 16) ⇒ N1−1 = 9 nên N1 N1−1 = 81.
58
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
N2 = 16 ≡ 7 ( mod 9) ⇒ N2−1 = 4 nên N2 N2−1 = 28.
Do đó phương trình ban đầu có tất cả 8 nghiệm sau
(1) : x = 1.81 + 1.64 = 145 ≡ 1 ( mod 144)
(2) : x = 1.81 + (−1) .64 = 17 ≡ 17 ( mod 144)
(3) : x = (−1) .81 + 1.64 = −17 ≡ −17 ( mod 144)
(4) : x = (−1) .81 + (−1) .64 = −145 ≡ −1 ( mod 144)
(5) : x = 7.81 + 1.64 = 631 ≡ 55 ( mod 144)
(6) : x = 7.81 + (−1) .64 = 503 ≡ 71 ( mod 144)
(7) : x = (−7) .81 + 1.64 = −503 ≡ −71 ( mod 144)
(8) : x = (−7) .81 + (−1) .64 = −631 ≡ −55 ( mod 144)
Nhận xét 2. Như vậy dựa vào định lý thặng dư Trung Hoa ta có thể đếm được số nghiệm
của một phương trình đồng dư. Chúng ta hãycụ thể hóa ý tưởng này thông qua các ví dụ 5,
ví dụ 6 sau đây
Ví dụ 5. Cho m là một số nguyên dương, tìm số nghiệm của phương trình: x2 ≡ x ( mod m).
Giải. Giả sử m = p1α1 p2α2 . . . pk k ( pi ∈ ℘, αi ∈ N). Ta có x2 ≡ x ( mod m) khi và chỉ khi x2 ≡
α
α α
x mod pi i (∀i = 1, 2, . . . , k) ⇔ x ( x − 1) ≡ 0 mod pi i (∀i = 1, 2, . . . , k )
α α
Vì ( x, x − 1) = 1 ⇒ pt : x ( x − 1) ≡ 0 mod pi i có hai nghiệm modulo pi i là x ≡
α α
0 mod pi i và x ≡ 1 mod pi i .Theo định lí thặng dư Trung Hoa, với mỗi bộ a1 , a2 , . . . , ak .
Hệ phương trình (
α
x ≡ ai mod pi i
i = 1, 2, . . . , k
α
luôn có nghiệm duy nhất modulo m. Do mỗi phương trình. x ( x − 1) ≡ 0 mod pi i đều có
hai nghiệm modulo pi i nên phương trình đã cho có 2k nghiệm.
α
Ví dụ 6 (VMO 2008). Cho m = 20072008 .Hỏi có bao nhiêu số nguyên dương n ≤ mthoả mãn
.
điều kiện: n (2n + 1) (5n + 2) ..m.
Giải. Ta có m = 92008 .2232008 = 34016 .2232008 = n1 .n2 .
.
Do (10, m) = 1 suy ra n (2n + 1) (5n + 2) ..m ⇔ m|10.5.2n. (2n + 1) (5n + 2) =
10n (10n + 5) (10n + 4) ⇔ m| x ( x + 5) ( x + 4)trong đó x = 10n.
Ta có: m| x ( x + 5) ( x + 4) ⇔ hệ phương trình đồng dư sau
x ≡ 0 ( mod 10)
x ( x + 5) ( x + 4) ≡ 0 ( mod n1 )
x ( x + 5) ( x + 4) ≡ 0 ( mod n2 )
Vì 3 không là ước chung của x, x + 4, x + 5 nên x ( x + 5) ( x + 4) ≡ 0 ( mod n1 ) khi và chỉ
khi x ≡ r1 ( mod n1 ) ở đó r1 ∈ {0, −4, −5}.
Tương tự x ( x + 5) ( x + 4) ≡ 0 ( mod n2 ) khi và chỉ khi x ≡ r2 ( mod n2 ) ở đó r1 ∈
{0, −4, −5}.
59
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Vậy m|n (2n + 5) (5n + 4) ⇔ x ≡ 0 ( mod 10) ; x ≡ r1 ( mod n1 ) ; x ≡ r2 ( mod n2 ).(1)
Vậy các số n ≤ m thoả mãn điều kiện bằng số các số x ≤ 10n1 .n2 thoả mãn (1).Với mỗi
cách chọn r1 ∈ {0, −4, −5} & r2 ∈ {0, −4, −5}theo định lí Trung Hoa ta có duy nhất một
số x ≤ 10n1 .n2 thoả mãn (1).Vậy có 9 số thoả mãn điều kiện bài ra.
Bài toán mở rộng 1. Cho m = p1α1 p2α2 . . . pk k ( pi ∈ ℘, αi ∈ N)và f ( x )là một đa thức với hệ số
α
nguyên. Khi đó phương trình đồng dư f ( x ) ≡ 0 ( mod m)có nghiệm khi và chỉ khi tất cả
αi
các phương trình đồng dư f ( x ) ≡ 0 mod pi , i = 1, kcó nghiệm. Nếu gọi số nghiệm của
α
phương trình f ( x ) ≡ 0 mod pi i , i = 1, k là ni thì phương trình f ( x ) ≡ 0 ( mod m)có đúng
n1 n2 . . . nk nghiệm (mod m).
3 Áp dụng giải các toán số học về chứng minh sự tồn tại
Ví dụ 7. Cho p, q ∈ N∗ \ {1} , ( p, q) = 1. Chứng minh rằng tồn tại k ∈ Z sao cho ta có số
( pq − 1)n k + 1 là hợp số với mọi n ∈ N∗ .
Giải. Do ( p, q) = 1 theo định lí thặng dư Trung Hoa ∃k ∈ N∗ thoả mãn hệ phương trình
đồng dư
(
k ≡ 1 ( mod p)
k ≡ −1 ( mod q)
.
Nếu n..2 ⇒ ( pq − 1)n ≡ 1 ( mod q) ⇒ ( pq − 1)n k ≡ −1 ( mod q) ⇔ ( pq − 1)n k + 1 ≡
0 ( mod q)
Nếu n2 ⇒ ( pq − 1)n ≡ −1 ( mod p) ⇒ ( pq − 1)n k ≡ −1 ( mod p) ⇔ ( pq − 1)n k + 1 ≡
0 ( mod p) Vậy ( pq − 1)n k + 1là hợp số với mọi n ∈ N∗ .
Nhận xét 3. Chứng minh trên thật gọn gàng nhờ vào việc sử dụng định lý thặng dư Trung
Hoa. Mấu chốt của bài toán là chúng ta thấy được để ( pq − 1)n k + 1 là hợp số ta cần chỉ ra
rằng khi nào ( pq − 1)n k + 1 chia hết cho p hoặc q(qua việc xét tính chẵn lẻ của n) từ đó ta
xây dựng được một hệ phương trình đồng dư:
(
k ≡ 1 ( mod p)
k ≡ −1 ( mod q)
Ví dụ 8 (IMO 1989). Chứng minh rằng với mọi n ∈ N∗ tồn tại nsố tự nhiên liên tiếp sao cho
bất kì số nào trong các số ấy cũng đều không phải là luỹ thừa (với số mũ nguyên dương)
của số nguyên tố.
Giải. Cách 1. Mỗi n ∈ N∗ xét nsố nguyên tố phân biệt p1 , p2 , . . . , pn .
Xét hệ phương trình
60
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
x ≡ p1 − 1 mod p21
x ≡ p2 − 1 mod p22
...............................
x ≡ pn − 1 mod p2n
Theo định lý thặng dư Trung Hoa thì hệ phương trình trên có nghiệm ⇔ ∃ a ∈ Z : a ≡
pi − 1 mod p2i ∀i = 1, n. Từ đó suy ra các số a + 1, a + 2, . . . , a + n đều không phải là luỹ
thừa với số mũ nguyên dương của một số nguyên tố.
Cách 2. Mỗi n ∈ N∗ xét 2nsố nguyên tố phân biệt p1 , p2 , . . . , pn , q1 , q2 , . . . , qn .Xét hệ
phương trình
x ≡ −1 ( mod p1 q1 )
x ≡ −2 ( mod p q )
2 2
...............................
x ≡ −n ( mod pn qn )
Theo định lý thặng dư Trung Hoa thì hệ phương trình trên có nghiệm
⇔ ∃ a ∈ Z : a ≡ −i ( mod pi qi ) ∀i = 1, n. Từ đó suy ra các số a + 1, a + 2, . . . , a + n, đều
không phải là luỹ thừa với số mũ nguyên dương của một số nguyên tố.
Nhận xét 4. qua sự chọn khéo léo bộ m1 , m2 , . . . , mk cho ta một dãy nsố hạng thỏa mãn yêu
cầu
Tư tưởng giống như trên cho các ví dụ 4,5,6,10 dưới đây.
Ví dụ 9 (Nordic 1998). Tìm số nguyên dương n sao cho tồn tại dãy { x1 , x2 , . . . , xn }=
.
{1, 2, . . . , n} thoả mãn: x1 + x2 + · · · + xk ..k với mọi k = 1, 2, . . . , n 2/ Tồn tại hay không một
.
dãy vô hạn { x1 , x2 , . . . }= {1, 2, . . . } sao cho xi 6= x j ∀i 6= j và thoả mãn: x1 + x2 + · · · + xk ..k
với mọi k = 1, 2, . . . , n?
Giải.
1/ n = 1 thoả mãn,n = 3 thoả mãn với dãy tương ứng là 1, 3, 2.
n n
n ( n +1) .
Giả sử n ∈ N∗ thoả mãn đề bài khi đó ta có: ∑ xi = ∑ i = 2 ..n ⇒ nlà số lẻ .
i =1 i =1
n −1 n −1 .
Giả sử n ≥ 5, đặt m = n +1
2 . Theo gt ∑ xi = ∑ i = mn − xn ..n − 1 nên suy ra
i =1 i =1
xn ≡ mn ≡ m ( mod n − 1) , 1 ≤ xn ≤ n ⇒ xn−1 = n − 1. Tương tự ta có
n −2 n −2 .
∑ xi = ∑ i = m (n − 1) − xn−1 ..n − 2 suy ra
i =1 i =1
xn−1 ≡ m (n − 1) ≡ m ( mod n − 2) , 1 ≤ xn−1 ≤ n ⇒ xn−1 = m = xn , vô lý.
Vậy chỉ có n = 1, n = 3 thoả mãn điều kiện đề bài.
∞
2/ Ta sẽ xây dựng một dãy ( xn )+
n=1 thoả mãn điều kiện đề bài.
Lấy x1 = 1, x2 = 3, x3 = 2.Giả sử x1 , x2 , x3 , . . . , x N là một dãy thoả mãn điều kiện
61
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
.
x1 + x2 + · · · + xk ..k với mọi k = 1, 2, . . . , N.Đặt x1 + x2 + x3 + · · · + x N = s
Gọi n là số nguyên dương bé nhất không nằm trong dãy x1 , x2 , x3 , . . . , x N .
Do ( N + 1, N + 2) = 1 nên theo định lí thặng dư Trung Hoa tồn tại một số nguyên
m > x1 , x2 , x3 , . . . , x N thoả mãn
(
m ≡ −s ( mod N + 1)
m ≡ −s − n ( mod N + 2)
Đặt x N +1 = m, x N +2 = n, ta có dãy x1 , x2 , x3 , . . . , x N , x N +1 , x N +2 thoả mãn các điều kiện
của bài toán vì
.
+ x1 + x2 + x3 + · · · + x N + x N +1 = s + m..N + 1;x1 + x2 + x3 + · · · + x N +1 + x N +2 =
.
s + m + n..N + 2
.
và x1 + x2 + · · · + xk ..k với mọi k = 1, 2, . . . , N.
. ∞
Do đó x1 + x2 + · · · + xk ..k với mọi k = 1, 2, . . . , N + 2 hiển nhiên dãy ( xn )+ n=1 xây dựng
như trên thoả mãn điều kiện đề bài.
Nhận xét 5. Trong bài toán này ta cần chú ý đến dãy { xn }là một hoán vị của tập N,nếu
không có giả thiết này bài toán trở thành tầm thường, trong phần 2 ta cần quy nạp như sau,
mỗi bộ
.
x , x , . . . , xn thỏa mãn ta luôn tìm được x
1 2 sao cho x + x + · · · + x .. n + 1. Do vậy
n +1 1 2 n +1
ta cần phải xây dựng dãy { xn } sao cho dãy { xn }quyét hết tập N, đây là yêu cầu chính của
bài toán
Ví dụ 10. Chứng minh rằng nếu p1 , p2 , . . . , pn là các số nguyên tố phân biệt thì phương trình
p p p n −1 pn
x1 1 + x2 2 + · · · + x n − 1 = xn có vô số nghiệm nguyên dương ( x1 , x2 , . . . , xn ).
Giải. Ta có đẳng thức (n − 1)k + (n − 1)k + · · · + (n − 1)k = (n − 1)k+1 .
| {z }
n −1
k k k k +1
Khi đó ta chọn x1 = (n − 1) , x2 = (n − 1) p2 , . . . , xn−1 = (n − 1) pn−1 , xn = (n − 1) pn .
p1
p p p n −1 pn
Thì ta thu được ngay phương trình x1 1 + x2 2 + · · · + xn− 1 = xn . 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 đ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 pn−1 )
k ≡ −1 mod p
( n)
Điều này luôn đúng theo định lý thặng dư Trung Hoa, vì p1 , p2 , . . . , pn là các số nguyên
tố phân biệt.
62
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Ví dụ 11. 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 với mọi i, j ∈ {1, 2, . . . , n}
Giải. Ta chọn các số sau a1 = 1x1 +1 .2x2 .3x3 . . . .(2n) x2n ,
a1 = 1x1 .2x2 +1 .3x3 . . . .(2n) x2n ,. . . ,
an = 1x1 .2x2 .3x3 . . . n xn +1 . . . (2n) x2n , xi ∈ N
ai + a j = 1x1 .2x2 .3x3 . . . i xi +1 . . . (2n) x2n + 1x1 .2x2 .3x3 . . . j x j +1 . . . (2n) x2n
= 1x1 .2x2 .3x3 . . . (2n) x2n (i + j)
ai + a j = 1x1 .2x2 .3x3 . . . (i + j) xi+ j+1 . . . (2n) x2n
Xét các số nguyên tố phân biệt p1 , p2 , . . . , p2n .
Xét các hệ phương trình đồng dư tuyến tính.
(
x1 ≡ −1 ( mod p1 )
x1 ≡ 0 ( mod pk ) , ∀k ∈ {2, 3, . . . , 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, 3, . . . i + j − 1, i + j + 1, . . . , 2n}
(
x2n ≡ −1 ( mod p2n )
x2n ≡ 0 ( mod pk ) , k = 1, 2n − 1
Theo định lý thặng dư Trung Hoa thì các hệ này chắc chắn có nghiệm. Từ đó suy ra
x1 x2 x i + j +1 x2n
pi + j ; pi + j ; · · · ; pi + j ; · · · ; pi + j · các số này đều là số nguyên.
Khi đó ai + a j = 1x1 .2x2 .3x3 . . . (i + j) xi+ j +1 . . . (2n) x2n
" x +1
# pi + j
x1 x2 i+ j x2n
pi + j pi + j pi + j pi + j
= 1 ·2 · · · (i + j ) · · · (2n) là lũy thừa của một số nguyên dương đây
là điều phải chứng minh
Ví dụ 12 (Balkan 2000). Cho A là một tập hợp khác rỗng các số nguyên dương. Chứng minh
rằng tồn tại số nguyên dương m sao cho mọi phần tử của tập mA đều là lũy thừa của một số
tự nhiên với số mũ lớn hơn 1.
Giải. Giả sử A = { a1 , a2 , . . . , ak }. Gọi p1 , p2 , . . . , p N là tất cả các ước số nguyên tố của số
k N αi,j
∏ ai . Với mỗi i = 1, 2, . . . , k tồn tại các số nguyên không âm αi,j sao cho ai = ∏ p j . Gọi
i =1 j =1
q1 , q2 , . . . , qk là các số nguyên tố phân biệt. Theo định lý thặng dư Trung Hoa, với j = 1, N
Tồn tại β j ≡ −αi,j ( mod qi )với mọi i = 1, 2, . . . , k.
" αi,j + β j # qi
N βj N αi,j + β j N qi
Đặt m = ∏ p j . Khi đó với i = 1, 2, . . . , k thì mai = ∏ p j = ∏ pj là số lũy
j =1 j =1 j =1
thừa
63
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Ta có điều phải chứng minh.
Ví dụ 13. Chứng minh rằng tồn tại vô hạn số k nguyên dương chẵn, sao cho với mọi số
nguyên tố p thì số p2 + k là hợp số.
Giải.
+ Nếu p = 2 ⇒ p2 + k là hợp số với mọi số k chẵn.
+ Nếu p > 3 ⇒ p2 ≡ 1 ( mod 3) suy ra mọi k chẵn và k ≡ 2 ( mod 3) thì p2 + k là hợp số
(bội của 3 )
+ Nếu p = 3 ⇒ p2 + k = 9 + k ≡ 0 ( mod 5) Nếu k ≡ 1 ( mod 5).
Vậy k thỏa mãn điều kiện bài toán ⇔ k là nghiệm nguyên dương của hệ phương trình
đồng dư (
k ≡ 0 ( mod 2)
k ≡ 1 ( mod 5)
theo định lý thặng dư Trung Hoa thì hệ phương trình trên có nghiệm: k ≡ 26 ( mod 30)
⇔ k = 30h + 26, (h ∈ N),p2 + k = p2 + 30h + 26 ≥ 40 cho nên p2 + k là hợp số. Vậy có vô số
k nguyên dương chẵn, sao cho với mọi số nguyên tố p thì số p2 + k là hợp số.
Nhận xét 6. Chứng minh trên thật ấn tượng nhờ vào việc sử dụng định lý thặng dư Trung
Hoa. Mấu chốt của bài toán là chúng ta thấy được để p2 + k là hợp số.ta cần chỉ ra rằng khi
nào p2 + k chia hết cho 2,3 hoặc 5 (qua việc xét các dạng của p) từ đó ta xây dựng được một
hệ phương trình đồng dư:
k ≡ 0 ( mod 2)
k ≡ 2 ( mod 3)
k ≡ 1 ( mod 5)
Từ đó tìm được tất cả giá trị của k.
Ví dụ 14. (mathlink.ro) Chứng minh rằng tồn tại đa thức P ( x ) ∈ Z [ x ], không có nghiệm
.
nguyên sao cho với mọi số nguyên dương n, tồn tại số nguyên dương x sao cho P ( x ) ..n.
Giải. Xét đa thức P ( x ) = (2x + 1) (3x + 1).Với mỗi số nguyên dương n, ta biểu diễn n dưới
dạng n = 2k (2m + 1). • Vì 2k , 3 = 1 nên tồn tại a sao cho 3a ≡ 1 mod 2k . Từ đó
3x ≡ −1 mod 2k thì ta cần chọn x ≡ − a mod 2k .
• Vì (2, 2m + 1) = 1 nên tồn tại b sao cho 2b ≡ 1 ( mod 2m + 1). Từ đó 2x ≡
−1 ( mod 2m + 1) thì ta cần chọn x ≡ −b ( mod 2m + 1)
• Nhưng do 2k , 2m + 1 = 1. Nên theo định lí thặng dư Trung Hoa, tồn tại số nguyên x
là nghiệm của hệ phương trình đồng dư sau:
(
x ≡ − a mod 2k
x ≡ −b ( mod 2m + 1)
.
theo lập luận trên P ( x ) = (2x + 1) (3x + 1)..n.
64
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Ví dụ 15. Cho tập A = {2, 7, 11, 13} và đa thức P ( x ) ∈ Z [ x ] có tính chất với mỗi n ∈ Z tồn
tại p ∈ A sao cho p | P (n) . Chứng minh rằng tồn tại p ∈ A sao cho p | P (n) với mọi n ∈ Z.
Giải.
Bổ đề 1. x, y ∈ Z sao cho x ≡ y ( mod p) ⇔ P ( x ) ≡ P (y) ( mod p) (tự chứng minh)
Áp dụng: Giả sử không tồn tại p ∈ A sao cho p | P (n) với mọi n ∈ Z suy ra ∃ a, b, c, d ∈ Z
phân biệt sao cho
. . .
P ( a) ≡ a0 ( mod 2) ⇒ a0 6 .. 2 P (b) ≡ b0 ( mod 7) ⇒ b0 6 .. 7 P (c) ≡ c0 ( mod 11) ⇒ c0 6 .. 11
.
P (d) ≡ d0 ( mod 13) ⇒ d0 6 .. 13
Xét hệ phương trình đồng dư:
x ≡ a ( mod 2)
x ≡ b ( mod 7)
(∗) .
x ≡ c ( mod 11)
x ≡ d ( mod 13)
Theo định lý thặng dư Trung Hoa hệ phương trình (∗) có nghiệm x0 . Kết hợp với bổ đề
ta có
P ( a) ≡ a0 ( mod 2)
P ( xo ) ≡
P (b) ≡ b0 ( mod 7)
P ( xo ) ≡
(∗∗)
P ( xo ) ≡ P (c) ≡ c0 ( mod 11)
P ( xo ) ≡ P (d) ≡ d0 ( mod 13)
mâu thuẫn với điều giả sử trên. Vậy điều giả sử là sai từ đó ta có điều phải chứng minh.
Bài toán mở rộng 2. Cho P ( x ) là đa thức với hệ số nguyên. Giả sử rằng có một một tập
hữu hạn các số nguyên tố A = { p1 , p2 , . . . , pn }, sao cho với mọi số nguyên aluôn tồn tại số
.
pi ∈ A, i = 1, n sao cho P ( a) ..pi . Chứng minh rằng tồn tại số nguyên tố p sao cho P ( x )
chia hết cho p với mọi số nguyên x
Nhận xét 7. Qua việc giải hai ví dụ 8 và 9 việc kết hợp giữa định lý thặng dư Trung Hoa với
các tính chất của đa thức nguyên cho ta một kết quả thú vị
Ví dụ 16. Cho n, h ∈ N∗ . Chứng minh rằng tồn tại n số tự nhiên liên tiếp thỏa mãn mỗi số
đều có ít nhất h ước số nguyên tố phân biệt.
Giải. Do tập hợp các số nguyên tố là vô hạn nên ta có thể chọn nh số nguyên tố phân biệt
p1 < p2 < · · · < ph < · · · < pnh
Theo định lý thặng dư Trung Hoa thì tồn tại k ∈ N∗ là nghiệm của hệ phương trình
65
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
k ≡ −1 ( mod p1 p2 . . . ph )
k ≡ −2 ( mod ph+1 ph+2 . . . p2h )
···
k ≡ −i mod p(i−1)h+1 p(i−1)h+2 . . . pih
···
k ≡ −n mod p(n−1)h+1 p(n−1)h+ 2 . . . pn h
,i = 1, n
Từ đó ta có n số tự nhiên liên tiếp là: k + 1; k + 2; · · · ; k + n thỏa mãn mỗi số đều có ít
nhất h ước số nguyên tố phân biệt.
Ví dụ(17. Chứng minh rằng với mọi m, n nguyên dương thì tồn tại x nguyên dương thoả
2x ≡ 1999 ( mod 3m )
mãn:
2x ≡ 2009 ( mod 5n )
Giải.
m n
( đề 2. 2 là căn nguyên( thuỷ của mod 5 , mod 3 . Từ đó tồn tại x1 , x2
Bổ :
2x1 ≡ 1999 ( mod 3m ) 2x1 ≡ 1 ( mod 3)
do vì x1 , x2 chẵn
2x2 ≡ 2009 ( mod 5n ) 2x2 ≡ 4 ( mod 5)
Theo định lý thặng dư Trung Hoa thì hệ phương trình đồng dư sau có nghiệm
t ≡ x21 m −1
(
mod 3
x2 n −1
t≡ 2 mod 4.5
mod ϕ (3m ) = 2.3m−1
(
2t ≡ x1 2x ≡ 1999 ( mod 3m )
Chọn x = 2t thì ⇒
2t ≡ x2 mod ϕ (5n ) = 4.5n−1 2x ≡ 2009 ( mod 5n )
(đpcm)
Nhận xét 8. Bài toán cần vận dụng kết hợp kiến thức giữa căn nguyên thủy và định lý thặng
dư Trung Hoa cho ta một lời giải thật chặt chẽ và ngắn gọn
Ví dụ 18 (diendantoanhoc.net 2014). Choplà 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.
Giải.
Nếu p = 2 thì hiển nhiên luôn tồn tại một số thỏa mãn đề bài ví dụ: 1234567899876543210
Nếup = 5 thì cũng luôn tồn tại một số thỏa mãn đề bài ví dụ: 1234567899876432105
Nếu p 6 ∈ {2, 5}. Xét hệ phương trình đồng dư tuyến tính.
(
x ≡ a0 a1 a2 . . . a9 mod 1010
x ≡ 0 ( mod p)
66
- Hội thảo khoa học, Hưng Yên 25-26/02/2017
Trong đó ai ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} , ai 6= a j , ∀0 ≤ i 6= j ≤ 9
10
Vì p ∈ ℘, p 6 ∈ {2, 5} suy ra gcd p, 10 = 1. Do đó theo định lý thặng dư Trung Hoa
thì hệ này chắc chắn có nghiệm, nghiệm của hệ chính là số thỏa mãn (điều phải chứng minh
)
Nhận xét 9. Từ các trường hợp cơ sở cho các số nguyên tố 2 và 5, xây dựng nên hệ phương
trình Đồng dư tuyến tính tối ưu cho số nguyên tố bất kỳ khác 2 và 5.
Ví dụ 19 (HSG Trại hè Hùng Vương 2014). Chứng minh rằng tồn tại 16 số nguyên dương
liên
- 2 tiếp sao cho
- không có số nào trong 16 số đó có thể biểu diễn được dưới dạng
- 7x + 9xy − 5y2
- , ( x, y ∈ Z).
-
-
- 2 2
nguon tai.lieu . vn
