tailieunhanh - Đồng Dư Thức

Đồng Dư Thức nghĩa: Cho số nguyên dương n 1 . Hai số nguyên a, b được gọi là dồng dư theo modulo n nếu chúng cho cùng số dư khi chia cho n . Kí hiệu: a ≡ b (mod n) chất: a)Các tính chất: +Nếu a ≡ a ' (mod n) b ≡ b' (mod n) Thì ta có : a + b ≡ a'+b' (mod n) a − b ≡ a '−b' (mod n) ≡ a'.b' (mod n) a k ≡ b k (mod n) Như vậy ta có thề cộng, trừ, nhân,. | T-k. Ă T-x mi Đông Dư Thức 1. Định nghĩa Cho số nguyên dương n 1. Hai số nguyên a b được gọi là dồng dư theo modulo n nếu chúng cho cùng số dư khi chia cho n . Kí hiệu a b mod n 2. Tính chất a Các tính chất Nếu í a a modn b b modn Thì ta có a b a b mod n a - b a -b mod n a .b mod n ak bk modn Như vậy ta có thề cộng trừ nhân và nâng lên lũy thừa các đồng dư thức theo cùng một modun b Luật giản ước Nếu a .c modn và c n 1 thì a a modn Bây giờ chúng ta sẽ đi vào một số vấn đề đồng dư thức có nhiều ứng dụng trong khi giải các bài toán số học thặng dư đầy đủ Định nghĩa Mỗi tập hợp A nào đó được gọi là một hệ thăng dư đầy đủ mod n nếu vớI bất kì số xe Z tồn tại duy nhất một ae A để x a modn Chẳng hạn A 0 1 2 n -1 là một hệ thặng dư đầy đủ theo mod n Dễ thấy Một tập A a1 a2 an gồm n số sẽ là một hệ thăng dư đầy đủ theo modun n Khi và chỉ khi at aj mod n ta tạm kí hiệu không đồng dư là với i j và i j e 1 2 n Thí dụ 1 Xét dãy Uk Ị 1 k 1 2. .Chứng minh rằng nếu n 2s s 1 thì trong dãy trên có thể chọn được một hệ thăng dư đầy đủ modun n. Giải Xét n số U 2k-1 k 1 2 . n Ta chỉ cần chứng minh với mọi 1 i j n thì U2i-1 @ U2j-1 mod n Giả sử ngược lại 1 i j n mà u2i_1 u2 j_1 mod n 2i _ 1 i 2 j _ 1 j mod n j _ i 2 j 2i _ 1 0 mod n 1 Do n 2 s 1 nên n không có ước lẻ. Từ 1 j i mod n Vô lý Thí dụ 2 Cho 2 hệ thặng dư đầy đủ modun n A a1 a2 an B b1 b .b Chứng minh rằng Nếu n là số chẵn thì tập A B a b1 a2 b2 . an bn không là hệ thặng dư đầy đủ modulo n Giải Nếu A là hệ thặng dư đầy đủ thì . . n n 1 z x a1 a2 . an 1 2 . n 2 modn Vì n chẵn và n n 1 1 nên n n 1 @ 0 mod n Nếu A B là hệ thặng dư đầy đủ vớI n chẵn thì a1 b1 a2 b2 . an bn 0 mod n nhưng a1 b1 a2 b2 . an bn - a1 a 2 . an b1 b2 . bn nỌy Ị nn-2 n 1 0 mod n Đây là điều vô lý. 4. Định lý Fermat Cho số nguyên tố đó với mọi số nguyên a ta đều có ap a mod p Ngoài ra nếu a p -1 thì ap_1 1 mod p Chứng minh Định lý Fermat có khá nhiều cách chứng minh ở đây chúng tôi sẽ giới thiệu đến các bạn cách chứng minh không phải .