intTypePromotion=1
ADSENSE

Định lý thặng dư Trung Hoa và một số ứng dụng

Chia sẻ: AndromedaShun _AndromedaShun | Ngày: | Loại File: PDF | Số trang:24

18
lượt xem
0
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết trình bày về đị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”. 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. Vận dụng tư tưởng của định lý thặng dư Trung Hoa, chúng ta có thể xây dựng mộ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. Mời các bạn cùng tham khảo!

Chủ đề:
Lưu

Nội dung Text: Định lý thặng dư Trung Hoa và một số ứng dụng

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 2 tiếp sao cho
  15. không có số nào trong 16 số đó có thể biểu diễn được dưới dạng
  16. 7x + 9xy − 5y2
  17. , ( x, y ∈ Z).
  18. 2 2
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2