tailieunhanh - 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 | Chương 6 Hệ thặng dư và định lý Thặng dư Trung Hoa Một số kí hiệu sử dụng trong bài viết 103 Hệ thặng dư 104 Dịnh lí thặng dư Trung Hoa 117 Bài tập đề nghị gợi ý - đáp số 125 Nguyễn Đình Tùng tungc3sp Bài viết này trình bày về Hệ thặng dư và định lý Thặng dư Trung Hoa. Một số kí hiệu sử dụng được phác họa trong Phần . Phần giới thiệu đến bạn đọc một số l ến tiứ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úp giải quyết một số dạng toán được trình bày trong . Phần 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ố. Một so 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 . 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 pi 1 1 Hệ thặng dư Kiến thức cơ bản Hệ thặng dư đầy đủ Định nghĩa Cho tập A a1 a2 . an . Giả sử Ti 0 Vị n 1 lầ số dư khi chia a-icho 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. Nhận xét. Từ định nghĩa dễ thấy . 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 2 Z tồn tại duy nhất ai 2 A sao cho ai m mod n . Với mọi a 2 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 . Hệ thặng dư 105 - Với mọi c 2 Z và c n 1 tập cA cai ca2 . cang 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ụ . Cho hai HDD mod n A ai a2 . an và B bi b2 . bn . a. Chùng minh rằng Nếu