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

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
Nội dung trích xuất từ tài liệu:
Chương 6: Hệ thặng dư và định lý thặng dư trung hoaChươ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 2Bài vi t này trình bày v H th ng dư và đ nh lý Th ng dư Trung Hoa. oM t s kí hi u s d ng đư c phác h a trong Ph n 6.1. Ph n 6.2 gi ithi u đ n b n đ c m t s ki n th c cơ b n v H th ng dư đ y đ hvà H th ng dư thu g n kèm theo bài t p ng d ng. Đ nh lý Th ng u idư 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 mm 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 đ . 103104 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 n6.26.2.1 H th ng dư Ki n th c cơ b n 4 hH 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 olà 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 iNh 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 c6.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 âmnh 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 nL 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 ...