Xemtailieu Tải về Đị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 Tải về bản full