Chương 6: Hệ thặng dư và định lý thặng dư trung hoa

Chia sẻ: Thanh Tran | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

1.095
lượt xem 49
download

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

Giới thiệu đến bạn đọc một số kiến thức cơ bản về hệ thặng dư đầy đủ và hệ thặng dư thu gọn kèm theo bài tập ứng dựng. Định lý thặng dư trung hoa kèm ứng dụng của nó giải quyết một số dạng toán

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 6: Hệ thặng dư và định lý thặng dư trung hoa

Chương 6 H th ng dư và đ nh lý Th ng dư Trung Hoa 6.1 M t s kí hi u s d ng trong bài 6.2 6.3 6.4 vi t 103 H th ng dư 104 .v Đ nh lí th ng dư Trung Hoa 117 Bài t p đ ngh & g i ý – đáp s n 125 4 h Nguy n Đình Tùng (tungc3sp) c 2 Bài vi t này trình bày v H th ng dư và đ nh lý Th ng dư Trung Hoa. o M t s kí hi u s d ng đư c phác h a trong Ph n 6.1. Ph n 6.2 gi i thi u đ n b n đ c m t s ki n th c cơ b n v H th ng dư đ y đ h và H th ng dư thu g n kèm theo bài t p ng d ng. Đ nh lý Th ng u i dư Trung Hoa kèm ng d ng c a nó giúp gi i quy t m t s d ng toán đư c trình bày trong Ph n 6.3. Ph n 6.4 k t thúc bài vi t bao g m m t s bài t p đ ngh kèm g i ý ho c đáp s . 6.1 V M t s kí hi u s d ng trong bài vi t • [x, y] : b i chung nh nh t c a hai s nguyên dương x, y (n u không nói gì thêm). • (x, y) : ư c chung l n nh t c a hai s nguyên x, y. • x y (mod p): x không đ ng dư v i y theo module p. • HĐĐ: h th ng dư đ y đ . 103
104 6.2. H th ng dư • HTG: h th ng dư thu g n. • P: t p các s nguyên t . • Φ(n): hàm Ơle c a n. • |A|: s ph n t c a t p A. • {x}: ph n l c a s th c x, đư c xác đ nh như sau: {x} = x − [x], trong đó [x] là ph n nguyên c a s th c x (là s nguyên l n nh t • không vư t quá x). n i=1 pi = p1 p2 ...pn .v n 6.2 6.2.1 H th ng dư Ki n th c cơ b n 4 h H th ng dư đ y đ c 2 Đ nh nghĩa 6.1 Cho t p A = {a1 ; a2 ; ...; an }. Gi s ri , 0 ≤ ri ≤ n − 1 o là s dư khi chia ai cho n. N u t p s dư {r1 ; r2 ; ...; rn } trùng v i t p {0; 1; 2; ...; n − 1} thì ta nói A là m t h th ng dư đ y đ (g i t t là HĐĐ) mod n. h u i Nh n xét. T đ nh nghĩa, d th y: V N u A = {a1 ; a2 ; ...; an } l p thành HĐĐ (mod n) n u và ch n u: i = j ⇒ ai = aj (mod n). N u A = {a1 ; a2 ; ...; an } là HĐĐ (mod n) thì t đ nh nghĩa d dàng suy ra: – V i m i m ∈ Z, t n t i duy nh t ai ∈ A sao cho ai ≡ m (mod n). – V i m i a ∈ Z, t p a + A = {a + a1 ; a + a2 ; ...; a + an } là m t HĐĐ (mod n). Di n đàn Toán h c Chuyên đ S h c
6.2. H th ng dư 105 – V i m i c ∈ Z và (c; n) = 1; t p cA = {ca1 ; ca2 ; ...; can } là m t HĐĐ (mod n). Chú ý: t p A∗ = {0; 1; 2; 3; ...; n − 1} là m t HĐĐ (mod n) không âm nh nh t. S ph n t c a t p A là |A| = n. Ví d 6.1. Cho hai HĐĐ (mod n): A = {a1 ; a2 ; ...; an } và B = {b1 ; b2 ; ...; bn }. a. Ch ng minh r ng: N u n ch n thì t p A + B = {a1 + b1 ; a2 + b2 ; ...; an + bn } không h p thành HĐĐ (mod n) b. K t lu n L i gi i. câu a. s th nào n u n là s l .v a. Ta có m t đi u ki n c n sau đây đ i v i HĐĐ (mod n), n h khi n ch n. Gi s C = {c1 ; c2 ; ...; cn } là m t HĐĐ (mod n). Khi đó theo đ nh nghĩa ta có: 2 c1 + c2 + ... + cn ≡ (1 + 2 + ... + (n − 1)) ≡4n(n + 1) (mod n) c 2 Do n ch n nên n = 2k, suy ra: n(n + 1) h o . = k(2k + 1) . ⇒ k(2k + 1) 0 (mod n) .n i 2 ⇒ c1 + c2 + ... + cn 0 (mod n) (6.1) Ta có: V ≡ u A + B = {a1 + b1 ; a2 + b2 ; ...; an + bn } ≡ {(a1 + a2 + ... + an ) + (b1 + b2 + ... + bn )} n(n + 1) n(n + 1) + (mod n) (mod n) 2 2 ≡ [n(n + 1)] (mod n) ⇒A+B ≡0 (mod n) (6.2) ( đây ta cũng s d ng gi thi t A và B là hai HĐĐ mod n). T (6.1) và (6.2) ta suy ra đpcm. Chuyên đ S h c Di n đàn Toán h c
106 6.2. H th ng dư b. Xét khi n l : Lúc này chưa th k t lu n gì v tính ch t c a h A + B. Th t v y, ta xét n = 3; A = {1; 2; 3} ; B = {4; 5; 6}. Khi đó A + B = {5; 7; 9} là m t HĐĐ mod 3. Nhưng, xét h A = {1; 2; 3} , B = {5; 4; 6}. Khi đó A + B = {6; 6; 9} không ph i là m t HĐĐ mod 3. H th ng dư thu g n .v n Đ nh nghĩa 6.2 Cho t p B = {b1 ; b2 ; ...; bk } là m t t p h p g m k s h nguyên và (bi ; n) = 1 v i m i i = 1; 2; ...; k. Gi s : bi = qi n + ri v i 1 ≤ ri < n. Khi đó d th y (ri ; n) = 1. 4 N u t p {r1 ; r2 ; ...; rn } b ng t p K g m t t c các s nguyên dương nh hơn n và nguyên t cùng nhau v i n thì B đư c g i là h th ng dư thu g n mod n, g i t t là HTG (mod n). 2 Nh n xét. Ta có th rút ra hai nh n xét: o c D th y t p B = {b1 ; b2 ; ...; bk } g m k s nguyên l p thành m t HTG khi và ch khi i h u i. (bi ; n) = 1 ii. bi = bj (mod n) v i 1 ≤ i = j ≤ k V iii. |B| = Φ(n) Đi u ki n (iii) tương đương v i (iii ): v i m i x ∈ Z; (x; n) = 1 t n t i duy nh t bi ∈ B sao cho x ≡ bi (mod n). T đ nh nghĩa ta suy ra: cho t p B = {b1 ; b2 ; ...; bk } là HTG mod n và c ∈ Z; (c; n) = 1 thì t p cB = {cb1 ; cb2 ; ...; cbn } cũng là HTG mod n. Di n đàn Toán h c Chuyên đ S h c
6.2. H th ng dư 107 Ví d 6.2. Cho hai s nguyên dương m, n v i (m; n) = 1. Gi s A = {a1 , a2 , ..., ah } ; B = {b1 , b2 , ..., bk } tương ng là các h thu g n mod m và mod n. Xét t p h p C = {ai n + bj m} ; 1 ≤ i ≤ h; 1 ≤ j ≤ k.. Ch ng minh r ng C là m t h thu g n HTG mod mn. L i gi i. + Ta ch ng minh (ai n + bj m, mn) = 1 ∀i = 1, h; j = 1, k (đi u ki n (i)). Gi s t n t i i, j và s nguyên t p là ư c chung c a ai n + bj m và mn. n . . Ta có ai n + bj m. và mn. .p .p. .v . . Do mn. mà (m, n) = 1 nên có th gi s n. suy ra .p .p, . .p . .p . ai n. ⇒ bj m. ⇒ bj . .p 4 h V y p là ư c nguyên t chung c a n và bj . Đi u này mâu thu n 1, h; j = 1, k. c 2 v i gi thi t. Nên đi u gi s là sai. V y (ai n+bj m, mn) = 1 ∀i = o + Ch ng minh đi u ki n (ii). Gi s t n t i a ∈ A; b ∈ B sao cho an + bm ≡ a n + b m (mod mn) i h V u ⇒ an ≡ a n (mod m) ⇒ a ≡ a (đi u này mâu thu n). V y an + bm a n + b m (mod mn). (mod m) (do (m, n) = 1) + Ch ng minh đi u ki n (iii ). Gi s (x, mn) = 1 ⇒ (x, m) = 1; (x, n) = 1. Vì (m, n) = 1 nên t p B = {mb1 , mb2 , ..., mbk } là m t HTG mod n. V y t n t i duy nh t b ∈ B đ x ≡ mb (mod n). Chuyên đ S h c Di n đàn Toán h c
108 6.2. H th ng dư Tương t , t n t i duy nh t a ∈ A đ x ≡ na (mod m). T đó suy ra x ≡ na + mb (mod n) và x ≡ na + mb (mod m). T đó k t h p v i (m, n) = 1 suy ra x ≡ na + mb (mod mn). Nh n xét. T đây, ta có th suy ra công th c tính hàm Ơle Φ(n). 6.2.2 ng d ng Trong các bài toán v đa th c, dãy s Ví d 6.3. [THTT, s 340] Cho p là s (p − 1)xp − x − 1. Ch ng minh r ng t sao cho Q(a) chia h t cho pp . .v n nguyên t l và đa th c Q(x) = n t i vô h n s nguyên dương a L i gi i. Thay cho vi c ch ng minh t sao cho Q(a) chia h t cho pp , ta s ch ng minh t p 4 h n t i vô h n s nguyên dương a 2 H = {Q(1); Q(2); ...; Q(pp )} là m t HĐĐ mod pp . c Ta có nh n xét sau: trong t p s {1; 2; ...; pp } g m pp s , gi s có hai o s u, v khác nhau thì Q(u) Q(v) (mod pp ). h Ta ch ng minh đi u này b ng ph n ch ng. Gi s có Q(u) ≡ Q(v) i (mod pp ) u ⇔ (p − 1)up − u − 1 ≡ (p − 1)v p − v − 1 (mod pp ) ⇔ (p − 1)(up − v p ) − (u − v) ≡ 0 (mod p) (6.3) V Theo đ nh lí Ferma nh thì up ≡ u (mod p) và v p ≡ vp (mod p) v i p là s nguyên t nên up − v p ≡ u − v (mod p). T (6.3) suy ra (p − 2)(u − v) ≡ 0 (mod p) ⇒ u ≡ v (mod p) (6.4) Cũng t (6.3) ta có: (u − v)((p − 1)(up−1 + up−2 v + ... + uv p−2 + v p−1 ) − 1) ≡ 0 (mod pp ) Di n đàn Toán h c Chuyên đ S h c
6.2. H th ng dư 109 K t h p v i (6.4) suy ra (u − v)((p − 1).p.up−1 − 1) ≡ 0 (mod pp ) ⇒ u − v ≡ 0 (mod pp ) Đi u này mâu thu n v i gi s u v (mod pp ). V y nh n xét đư c ch ng minh. • T nh n xét trên suy ra H = {Q(1); Q(2); ...; Q(pp )} là m t HĐĐ mod pp . T đó suy ra trong t p s {1; 2; ...; pp } g m pp s thì t n .v n t i duy nh t m t s a sao cho Q(a) ≡ 0 (mod pp ) hay Q(a). p . . .p • Ta xét dãy s h ng ak = a + k.pp v i k = 0, 1, 2..., d th y r ng: Q(ap ) ≡ Q(a) ≡ 0 4 h (mod pp ). . Nghĩa là t n t i vô h n s ak (k = 0, 1, 2, ...) th a mãn Q(ak ). p . .p c 2 h o Ví d 6.4. Cho đa th c P (x) = x3 − 11x2 − 87x + m. Ch ng minh r ng v i m i s nguyên m, t n t i s nguyên n sao cho P (n) chia h t cho i 191. L i gi i. Ý tư ng cũng tương t Ví d 6.3, ta s s d ng HĐĐ. Trư c u h t ta đưa ra b đ sau: V B đ 6.1– Cho p là s nguyên t , p ≡ 2 (mod 3). Khi đó,v i m i s nguyên x, y mà x3 ≡ y 3 (mod p) ⇒ x ≡ y (mod p) Ch ng minh. Th t v y: • N u x ≡ 0 (mod p) ⇒ y 3 ≡ 0 (mod p) ⇒ y ≡ 0 (mod p) ⇔ x ≡ y(modp) • N u x, y cùng không chia h t cho p, do p ≡ 2(mod3) ⇒ p = 3k + 2(k ∈ Z). Chuyên đ S h c Di n đàn Toán h c
110 6.2. H th ng dư Theo đ nh lí Ferma: xp−1 = x3k+1 ≡ 1 (mod p) y p−1 = y 3k+1 ≡ 1 (mod p) 3k+1 ⇒x ≡ y 3k+1 (mod p) (6.5) Mà theo gi thi t, x3 ≡ y 3 mod p ⇒ x3k ≡ y 3k (mod p). T đó suy ra x ≡ y (mod p). V y b đ đư c ch ng minh. Tr l i bài toán, ta s ch ng minh P (n1 ) ≡ P (n2 ) (mod 191) v i n1 ; n2 ∈ Z thì n1 ≡ n2 (mod 191). Th t v y, vì 3 3 .v n h 27P (n1 ) = (3n1 − 11) − 11.191.n1 + 11 + 27m 27P (n2 ) = (3n2 − 11)3 − 11.191.n2 + 113 + 27m nên P (n1 ) ≡ P (n2 ) 2 (mod 191) 4 ⇔27P (n1 ) ⇔(3n1 − 11)3 ≡ 27P (n2 ) o ≡ (3n2 − 11)3 c(mod 191) (mod 191) h ⇔3n1 − 11 ≡ 3n2 − 11 (mod 191)(suy ra t b đ ) i ⇔n1 ≡ n2 (mod 191) u V i m i n1 , n2 ∈ A = {1; 2; 3; ...; 1991} (A là m t HĐĐ mod 191), n1 = n2 ta có P (n1 ) P (n2 ) (mod 191) ⇒ A∗ = {P (1); P (2); ...; P (191)} là m t HĐĐ mod 191. . V T đó suy ra ∃n ∈ A = {1; 2; 3; ...; 191} sao cho P (n) ≡ 191 . (mod 191) ⇔ P (n). .191 Ví d 6.5. Cho p là m t s nguyên t . Ch ng minh r ng v i m i s m nguyên không âm b t kì, luôn t n t i m t đa th c Q(x) có h s nguyên sao cho pm là ư c chung l n nh t c a các s an = (p + 1)n +Q(n); n = 1, 2, 3... Di n đàn Toán h c Chuyên đ S h c
6.2. H th ng dư 111 L i gi i. Ta có b đ sau: . B đ 6.2– ∀k ∈ N, k < m thì t n t i bk ∈ Z sao cho bk pm + pk . .k! Ch ng minh. Gi s k! = pαk Mk v i (Mk ; p) = 1. Khi e ch y trong t p {0; 1; ...; Mk − 1} thì các s epm−k l p thành m t HĐĐ modMk , thành th t n t i bk ∈ Z sao cho bk pm−k ≡ −1 (mod Mk ) n . ⇔ (bk pm−k + 1). k .M . k .v ⇔ (b pm + pk ). .M k .p k M t khác h ∞ ∞ k k αk <
112 6.2. H th ng dư Ta ch ng minh đa th c Q(x) = R(x)+pm (1−e) là đa th c c n tìm.Th t v y, an = (p + 1)n + Q(n) = (p + 1)n + R(n) + pm (1 − e) . = un + pm (1 − e). m , ∀n = 1, 2, 3... (6.6) .p M t khác . a1 = (p + 1) + Q(1) = p + 1 + R(1) + pm (1 − e) = epm + pm (1 − e). m n .p .v Do đó pm là ƯCLN c a an v i m i n = 1, 2, 3... Ví d 6.6. Cho p ≥ 3 là m t s nguyên t và a1 , a2 , ..., ap−2 là m t dãy h các s nguyên dương sao cho p không là ư c s c a ak và ak k − 1 v i m i k = 1, 2, 3, ..., p − 2. Ch ng minh r ng t n t i m t s ph n t trong dãy a1 , a2 , ..., ap−2 có tích đ ng dư v i 2 module p. L i gi i. Ta có b đ sau: 2 4 c B đ 6.3– V i m i s nguyên k = 1, 2, ..., p − 1 t n t i m t t p các s nguyên {bk,1 , bk,2 , ..., bk,k } th a mãn hai đi u ki n sau: a1 , a2 , ..., ap−2 , h o 1. M i bk,j ho c b ng 1, ho c b ng tích c a m t s ph n t trong dãy 2. bk,i u i bk,j (mod p) v i 1 ≤ i = j ≤ k. Ch ng minh. V i k=2 ch n b21 = 1; b22 = a1 1 (mod p) (do a1 − 1 không chia h t cho p). 1 . V Gi s v i 2 ≤ k ≤ p − 2 ta đã ch n đư c t p {bk,1 , bk,2 , ..., bk,k } th a mãn hai tính ch t trên. Vì ak . nên hai ph n t khác nhau b t kì trong t p .p {ak bk,1 , ak bk,2 , ..., ak bk,k } là phân bi t theo mod p. ak k 1(modp) ⇒ (ak bk,1 )(ak bk,2 )...(ak bk,k ) bk,1 bk,2 ...bk,k (mod p) Di n đàn Toán h c Chuyên đ S h c
6.2. H th ng dư 113 T hai đi u trên suy ra t n t i ch s j(1 ≤ j ≤ k) sao cho ak bk,j ∈ / {bk,1 , bk,2 , ..., bk,k }. Xét t p {bk,1 , bk,2 , ..., bk,k , ak bk,j }. Sau khi đánh s l i các ph n t ta thu đư c t p {bk+1,1 , bk+1,2 , ..., bk+1,k , bk+1,k+1 } . Ta th y t p này có k + 1 ph n t th a mãn hai tính ch t trên nên theo nguyên lí quy n p, b đ đư c ch ng minh. đ ng dư v i 2 mod p. Vì ph n t này khác 1 nên nó ph i đ ng dư v i tích c a m t s ak . Suy ra đpcm. .v n Quay l i bài toán, áp d ng b đ 6.3, xét t p {bp−1,1 , bp−1,2 , ..., bp−1,p−1 }, ta th y t p này là m t HTG mod p nên nó ch a đúng m t ph n t Trong t p con t p s nguyên dương, bài toán s h c chia h t Ví d 6.7. Cho p > 3 là s nguyên t có d ng 3k + 2. 4 h a. Ch ng minh r ng t p A = HTG mod p. c 2 23 − 1; 33 − 1; 43 − 1; ...; p3 − 1 là o p b. Ch ng minh r ng (i2 + i + 3) ≡ 3(modp). h i=1 i L i gi i. a. Ta s ch ng minh t p A th a mãn 3 đi u ki n đã nêu Đ nh nghĩa 6.2. V u • Hi n nhiên m i ph n t c a A đ u không chia h t cho p (th a mãn đi u ki n (i)). • Gi s t n t i 1 ≤ i < j ≤ p − 1 sao cho i3 − 1 ≡ j 3 − 1 (mod p) ⇒ i3 ≡ j 3 (mod p) ⇒ i3k ≡ j 3k (mod p) M t khác, theo đ nh lí Ferma, ta có: i3k+1 ≡ j 3k+1 (mod p) T đó suy ra i ≡ j (mod p) ⇒ i = j (mâu thu n). V y A th a mãn đi u ki n (ii). Chuyên đ S h c Di n đàn Toán h c
114 6.2. H th ng dư • Vì Φ(p) = p − 1 = |A| nên đi u ki n (iii) th a mãn. V y A là m t HTG mod p. b. Vì B = {1; 2; 3; ...; p − 1} là m t HTG mod p. Mà A cũng là m t HTG mod p (theo ph n a.) nên ta có: p (i3 − 1) ≡ (p − 1)! (mod p) i=2 p ⇔ (i2 + i + 1) ≡ 1 (mod p) ⇔ i=2 p i=1 (i2 + i + 1) ≡ 3 (mod p) .v n h Nh n xét. Ta có th m r ng Ví d 6.7 như sau: Ví d 6.8. Cho p là s nguyên t l có d ng mk + 2 (m, k là các s nguyên dương, m > 2). Tìm s dư c a phép chia T = p 2 (tm−1 + tm−2 + ... + t + 1)4 cho p. t=1 o c h Ví d 6.9. Ch ng minh r ng v i m i s nguyên dương n, t n t i s t i nhiên n g m n ch s đ u l và nó chia h t cho 5n. L i gi i. Xét s xn = a1 a2 ...an = 5n .a th a mãn (v i ai ∈ Z+ l v i u m i i = 1, 2, ..., n và a ∈ Z+ ) Ta s ch ng minh bài toán b ng phương pháp quy n p toán h c. V . V i n = 1 ⇒ ∃a = 5. 1 . V y m nh đ đúng v i n = 1. 1 .5 Gi s m nh đ đúng v i n ⇔ xn = a1 a2 ...an = 5n .a, c n ch ng minh m nh đ đúng v i n + 1. Xét 5 s sau đây: a1 = 1a1 a2 ...an = 5n (1.2n + a) a2 = 3a1 a2 ...an = 5n (3.2n + a) a3 = 5a1 a2 ...an = 5n (5.2n + a) a4 = 7a1 a2 ...an = 5n (7.2n + a) a5 = 9a1 a2 ...an = 5n (9.2n + a) Di n đàn Toán h c Chuyên đ S h c
6.2. H th ng dư 115 Do B = {1, 3, 5, 7, 9} là m t HĐĐ mod 5 cho nên B ∗ = {1.2n + 1; 3.2n + a; 5.2n + a; 7.2n + a; 9.2n + a} cũng là HĐĐ mod 5 nên t n t i duy nh t m t s trong B∗ chia h t cho 5. ⇒ Trong 5 s a1 ; a2 ; a3 ; a4 ; a5 có duy nh t m t s chia h t cho 5(n + 1) 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 nguyên dương. V y n v i m i s nguyên dương n, luôn t n t i m t s t nhiên g m n ch s đ u l và chia h t cho 5n. Trong m t s d ng toán S h c khác h Ngoài các ng d ng nêu trên, h th ng dư còn đư c dùng trong nhi u d ng toán s h c khác, đơn bi u như trong các bài toán liên quan t i.v b c nh t). Sau đây xin nêu ra m t s ví d . 2 4 tính t ng, gi i phương trình nghi m nguyên (phương trình Diophant c Ví d 6.10. V i m i c p s nguyên t cùng nhau (p,q), đ t o q 2q (p − 1)q S= + + ... + p p p i a. Ch ng minh r ng: S = h (p − 1)(q − 1) 2 V L i gi i. u b. Xác đ nh giá tr c a p, q đ S là s nguyên t a. Ta có kq p cho p (0 ≤ rk ≤ p − 1). rk = , q đây rk là s dư trong phép chia q Ta có: q 2q (p − 1)q r1 r2 rp−1 S= + + ... + − + + ... + p p p p p p Vì (p, q) = 1 ⇒ rk = 0 ∀ k = 1, 2, ..., p − 1, t đó ta th y t p A = {r1 ; r2 ; ...; rp−1 } chính là m t hoán v c a t p A = {1; 2; ...; p − 1}. Chuyên đ S h c Di n đàn Toán h c
116 6.2. H th ng dư Th t v y, ngư c l i, gi s ∃ i, j ∈ {1; 2; ...; p − 1} , i < j mà ri = rj 1≤j−i≤p−2 ≤j−i≤p−2 ⇒ . ⇔ . (vô lý) (j − i)q . .p j − i. .p Ta có: r1 r2 p + p + ... + rp−1 p = 1 + 2 + ... + p − 1 p ⇒S= = p−1 2 .v (p − 1)(q − 1) 2 n (6.7) 4 h b. T (6.7) suy ra đ S là s nguyên t c n có p, q > 1 và ít nh t 2 m t trong hai s p, q l . c • Trư ng h p 1: p, q cùng l ⇒ p, q ≥ 3, p = q (do (p,q)=1), k t h p v i (6.7) ⇒ S là s ch n l n hơn 2 ⇒ S không ph i là s nguyên t . o h • Trư ng h p 2: p là s ch n, q là s l i u     (p, q) = 1   p−1=1  q−1 V    ∈P S∈P⇔   2   (p, q) = 1  p−1∈P     q−1  =1 2  p=2  q = 2h + 1 (h ∈ P) ⇔ (6.8)  q=3 p = t + 1 (t ∈ P, t 2 (mod 3)) Di n đàn Toán h c Chuyên đ S h c
6.3. Đ nh lí th ng dư Trung Hoa 117 • Trư ng h p 3: q là s ch n, p là s l . Tương t trư ng h p 2, ta có:  p = 2m + 1(m ∈ P)  q=2  (6.9)  p=3 q = n + 1(n ∈ P, n 2 (mod 3)) T (6.8) và (6.9) ta có các c p s p, q c n tìm. Ví d 6.11. Cho a, b, c là các s nguyên dương th a mãn a ≤ b ≤ c .v và (a, b, c) = 1. Ch ng minh r ng n u n > ac + b thì phương trình n = ax + by + cz có nghi m nguyên dương. n h L i gi i. G i (a, c) = d ⇒ (b, d) = 1 ⇒ A = {bi}d là HĐĐ mod d i=1 . ⇒ ∃ y ∈ {1, 2, ..., d} sao cho by ≡ n (modd) ⇔ (n − by). 4 .d. Do (a, c) = d ⇒ a = a1 d; c = c1 d (a1 , c1 ∈ Z + ; (a1 , c2 ) = 1) ⇒ B = 2 {a1 j}c1 là HĐĐ mod c1 . j=1 n − by c ⇒ ∃x ∈ {1, 2, ..., c1 } sao cho a1 x ≡ (mod c1 ) ⇒ ∃z ∈ Z sao cho d n − by o = a1 x + c1 z. d h M t khác, ta có: n − by d > ac + b − by d u i= (d − 1) ca1 − b d + a1 c1 ≥ a1 c1 ≥ a1 x ⇒ z ∈ Z+ T đây suy ra n − by = ax + cz ⇔ n = ax + by + cz. V y n u n > ac+b thì phương trình n = ax+by +cz có nghi m nguyên dương. 6.3 6.3.1 V Đ nh lí th ng dư Trung Hoa Ki n th c cơ b n Đ nh lý 6.1– Cho k s nguyên dương n1 , n2 , ..., nk đôi m t nguên t cùng nhau và k s nguyên b t kì a1 , a2 , ..., ak . Khi đó t n t i s nguyên a th a mãn a ≡ ai (mod ni ), ∀i = 1, k. Chuyên đ S h c Di n đàn Toán h c
118 6.3. Đ nh lí th ng dư Trung Hoa S nguyên b th a mãn b ≡ ai (mod ni ), ∀i = 1, k khi và ch khi b ≡ a (mod n) v i n = n1 n2 ...nk . n L i gi i. • Đ t n = n1 n2 ...nk và đ t Ni = . ni Do (ni , nj ) = 1, ∀i = j nên suy ra (Ni , ni ) = 1 ∀i = 1; k. Do (Ni , ni ) = 1, ∀i = 1; k nên v i m i i(1 ≤ i ≤ k) t n t i bi sao cho Ni bi ≡ 1 (mod ni ) (6.10) Như v y ta có b b1 , b2 , ..., bk . Do Nj ≡ 0 (mod ni ) khi i = j, t đó dĩ nhiên suy ra .v n h Nj bj ≡ 0 (mod ni ) (6.11) 4 k Đ ta= Nj bj aj . 2 j=1 V i m i i (1 ≤ i ≤ k) ta có o c a = Ni bi ai + k Nj bj aj (6.12) h j=1;j=i u i T (6.10),(6.11),(6.12) suy ra a ≡ ai (mod ni ), ∀i = 1, k. • D th y, vì n1 , n2 , ..., nk đôi m t nguyên t cùng nhau nên ta có kêt lu n sau: S nguyên b th a mãn b ≡ ai (mod ni ), ∀i = 1, k Nh n xét. V khi và ch khi b ≡ a (mod n) v i n = n1 n2 ...nk . 1. Ngoài cách ch ng minh trên, ta còn có th s d ng phép quy n p đ ch ng minh đ nh lí th ng dư Trung Hoa. 2. Đ 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 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 Di n đàn Toán h c Chuyên đ S h c
6.3. Đ nh lí th ng dư Trung Hoa 119 đi u ki n quan h , chia h t,..., hay đ m s nghi m c a phương trình đ ng dư. Vi c s d ng h p lý các b và (trong đ nh lý) cho ta r t nhi u k t qu thú v và t đó có th đưa ra nhi u bài toán hay và khó. Ví d 6.12. Cho m1 , m2 , ..., mn là các s nguyên dương, r1 , r2 , ..., rn là các s nguyên b t kì. Ch ng minh r ng đi u ki n c n và đ đ h phương trình đ ng dư x ≡ r1 (mod m1 ) x ≡ r2 (mod m2 ) ... x ≡ rn (mod mn ) .v n 4 h có nghi m là ri ≡ rj (mod GCD (mi , mj )); ∀1 ≤ i < j ≤ n. c 2 N u x0 và x1 là hai nghi m th a mãn h phương trình trên thì x0 ≡ x1 (mod m) v i m = LCM (m1 , m2 , ..., mn ). T c là h phương trình đã cho có nghi m duy nh t theo module m. GCD (mi , mj ) = d, ta có: h o L i gi i. Trư c h t ta gi s h phương trình đã cho có nghi m x0 . Đ t u i xo − ri ≡ 0 (mod mi ) xo − rj ≡ 0 (mod mj ) V Suy ra ri ≡ rj mod (GCD (mi , mj )). Do i, j tùy ch n nên ri ≡ rj (mod GCD(mi , mj )), ∀1 ≤ i < j ≤ n. Đây là đi u ki n c n đ h phương trình có nghi m. Ngư c l i, ta s ch ng minh b ng quy n p theo n r ng n u đi u ki n trên đư c th a mãn thì h phương trình luôn có nghi m duy nh t theo module m v i m = LCM (m1 , m2 , ..., mn ). V i trư ng h p n = 2, đ t GCD (m1 , m2 ) = d ⇒ m1 = dd1 ; m2 = dd2 v i GCD (d1 , d2 ) = 1. Suy ra ri ≡ rj ≡ r (mod d). Đ t r1 = r + k1 d; r2 = r + k2 d. Chuyên đ S h c Di n đàn Toán h c
120 6.3. Đ nh lí th ng dư Trung Hoa Ta có:  . x ≡ r1 (mod m1 ) (x − r) − k1 d. 1 .dd  ⇔ x ≡ r2 (mod m2 )  (x − r) − k d.. 2 .dd2  x−r  ≡ k2 (mod d1 ) ⇔ d (6.13)  x−r ≡k (mod d2 ) 2 d n Do (d1 , d2 ) = 1 nên theo đ nh lí Th ng dư Trung Hoa, t n t i m t s x−r dương x sao cho x ≡ k1 (mod d1 ); x ≡ k2 (mod d2 ). Vì x và .v d x ≡ k1 (mod d1 ) x−r là hai nghi m c a phương trình nên ≡x x ≡ k2 (mod d2 ) d (mod d1 d2 ) hay x ≡ xd + r (mod dd1 d2 ). h Do m = LCM (m1 , m2 ) = dd1 d2 nên theo đ nh lí Th ng dư Trung Hoa, h có nghi m duy nh t module m. 4 2 Gi s đ nh lí đúng đ n n − 1. Ta s ch ng minh đ nh lí đúng đ n n. Đ t m1 = LCM (m1 , m2 , ..., mn−1 ) ; m2 = mn ; r2 = rn . Vì ri ≡ n p, h phương trình o c rj (modGCD (mi , mj )) v i m i 1 ≤ i < j ≤ n nên theo gi thi t quy x ≡ ri (mod mi ) i = 1, n − 1 có duy nh t nghi m x ≡ r1 h (mod m1 ). i M t khác t ri ≡ rj ( mod GCD(mi , mj )) v i m i 1 ≤ i < j ≤ n suy ra r1 ≡ r2 (mod GCD(m1 , m2 )). x ≡ r1 (mod m1 ) x ≡ r2 (mod m2 ) V u Theo ch ng minh trên cho trư ng h p n = 2 ta có h phương trình có nghi m duy nh t theo module m = LCM m1 , m2 = LCM (m1 , m2 , ..., mn ) . Theo nguyên lí quy n p ta có đi u ph i ch ng minh. Nh n xét. Đây chính là đ nh lí Th ng dư Trung Hoa d ng m r ng, nó hoàn toàn ch ng minh d a trên cơ s đ nh lí Th ng dư Trung Hoa. Trong bài vi t này, ta s không đi sâu vào tìm hi u đ nh lí d ng m r ng mà ch đi sâu vào các ng d ng c a đ nh lí Th ng dư Trung Hoa (d ng thư ng). Di n đàn Toán h c Chuyên đ S h c
6.3. Đ nh lí th ng dư Trung Hoa 121 6.3.2 ng d ng Trong Lý thuy t s Ví d 6.13. Ch ng minh r ng v i m i s t nhiên n, t n t i n s t nhiên liên ti p mà m i s trong n s đó đ u là h p s . L i gi i. Ý tư ng: ta s t o ra m t h phương trình đ ng dư g m n phương trình đ ng dư. D a vào đ nh lí th ng dư Trung Hoa, ta k t lu n đư c s t n t i nghi m c a h đó. (mod p2 ), ∀k = 1, 2, ..., n. k k n Gi s p1 , p2 , ..., pn là n s nguyên t khác nhau t ng đôi m t. Xét h phương trình đ ng dư x ≡ −k (mod p2 )(k = 1, 2, ..., n). .v Theo đ nh lí th ng dư Trung Hoa, t n t i x0 ∈ N∗ sao cho x0 ≡ −k h Khi đó các s x0 + 1; x0 + 2, ...; x0 + n đ u là h p s .(đpcm) 4 Ví d 6.14. Ch ng minh r ng v i m i s t nhiên 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 không 2 ph i lũy th a (v i s mũ nguyên dương) c a m t s nguyên t . o c Nh n xét. Bài này cũng g n tương t v i ý tư ng c a bài toán ví d c ng c . Tuy nhiên vi c tìm ra h phương trình đ ng dư khó hơn m t chút. i m t p1 , p2 , ..., pn . h L i gi i. V i m i s t nhiên n, xét n s nguyên t khác nhau t ng đôi u Theo đ nh lí Th ng dư Trung Hoa, t n t i a ∈ N∗ sao cho a ≡ pk − k (mod p2 ) (k = 1, 2, ..., n). k Khi đó d th y r ng các s a + 1, a + 2, ..., a + n đ u không ph i lũy V th a v i s mũ nguyên dương c a m t s nguyên t (đpcm). Ví d 6.15. Cho trư c các s nguyên dương n, s. 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 s c a m t s nguyên dương l n hơn 1. n L i gi i. Xét dãy Fn = 22 + 1, (n = 0, 1, 2, ...). D ch ng minh b đ sau: B đ 6.4– N u n = m thì (Fn , Fm ) = 1. Chuyên đ S h c Di n đàn Toán h c
122 6.3. Đ nh lí th ng dư Trung Hoa Áp d ng đ nh lí Th ng dư Trung Hoa cho n s nguyên t cùng nhau s s s F1 , F2 , ..., Fn và n s ri = −i(i = 1, 2, .., n) ta có t n t i s nguyên c . sao cho c + i. s . .F i V y dãy {c + i}n là n s nguyên dương liên ti p, s h ng th i chia i=1 h t cho Fis . Ví d 6.16. Ch ng minh r ng t n t i m t đ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 n x sao cho P (x) chia h t cho n. .v L i gi i. Ta có th xét đa th c P (x) = (3x + 1)(2x + 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ì GCD(2k , 3) = 1 nên t n t i a sao cho 3a ≡ 1 (mod 2k ). T đó 3x ≡ −1 4 h (mod 2k ) ⇔ x ≡ −a (mod 2k ) 2 Tương t GCD (2, 2m+1) = 1 nên t n t i b sao cho 2b ≡ 1 (mod (2m+ 1)). T đó 2x ≡ −1 c (mod (2m + 1)) ⇔ x ≡ −b (mod (2m + 1)) o h Cu i cùng, do GCD (2k , 2m + 1) = 1 nên theo đ nh lý Th ng dư Trung i Hoa, t n t i s nguyên x là nghi m c a h : V u x ≡ −a (mod 2k ) x ≡ −b (mod (2m + 1)) . Và theo lý lu n trên, P (x) = (3x + 1)(2x + 1). .n. Ví d 6.17. Trong lư i đi m nguyên c a m t ph ng t a đ Oxy, m t đi m A v i t a đ (x0 , y0 ) ∈ Z2 đư c g i là nhìn th y t O n u đo n th ng OA không ch a đi m nguyên nào khác ngoài A, O. Ch ng minh r ng v i m i n nguyên dương l n tùy ý, t n t i hình vuông n × n có các đ nh nguyên, hơn n a t t c các đi m nguyên n m bên trong và trên biên c a hình vuông đ u không nhìn th y đư c t O. Di n đàn Toán h c Chuyên đ S h c