Tham khảo tài liệu 'phương pháp đồng dư trong toán', tài liệu phổ thông, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | ĐỒNG DƯ 1. Định nghĩa. Cho a b m là các số nguyên m 0. Nếu a - b chia hết cho m thì a được gọi là đồng dư với b modulo m ký hiệu a s b mod m. 2. Tính chất Cho a b c d là các số nguyên . Nếu a s b mod m thì b s a mod m . Nếu a s b mod m và b s c mod m thì a s c mod m . Nếu a s b mod m và c s d mod m thì a c s b d mod m . Nếu a s b mod m và c s d mod m thì ac s bd mod m . Nếu a s b mod m k nguyên dương thì ak s bk mod m . Nếu a s b mod m và d m thì a s b mod d . Nếu a s b mod m thì ac s bc mod cm với mọi c khác 0. . Nếu ab s ac mod m và a m 1 thì b s c mod m . a s b mod m i 1 2 . n Ö a s b mod m1 m2 . mn 3. Định lý Fermat nhỏ Giả sử p nguyên tố a p 1. Khi đó ap 1 s 1 mod p Chứng minh. Xét p - 1 số a 2a 3a . p - 1 a. Ta chứng minh rằng không tồn tại 2 số đồng dư trong phép chi a cho p. Giả sử ka s la mod p với k l e 1 2 . p - 1 và k l a k - l ỉ p k - l ỉ p k l mâu thuẩn Vậy khi chia p - 1 số trên cho p ta nhận được p - 1 số dư khác nhau từ 1 2 . p - 1 Suy ra a. 2a. . p - 1 a s . p - 1 mod p Ö p - 1 . ap-1 s p - 1 mod p Vì p - 1 p 1 nên ap 1 s 1 mod p. Từ định lý ta có ap s a mod p với p nguyên tố a p 1 4. Hệ thặng dư đầy đủ. . Tập hợp x1 x2 . xn gọi là một hệ thặng dư đầy đủ modulo m nếu với mỗi số nguyên y tồn tại duy nhất một xi sao cho y s xi mod m. . Tập 1 2 . m - 1 m là một hệ thặng dư đầy đủ modulo m . Mọi hệ thặng dư đầy đủ modulo m đều có đúng m phần tử . Một tập gồm m phần tử là một hệ thặng dư đầy đủ modulo m nếu và chỉ nếu hai phần tử khác nhau bất kỳ của nó không đồng dư với nhau modulo m. . Cho số nguyên a và m 0. Tập hợp tất cả các số nguyên x thỏa mãn x s a mod m được gọi là một lớp đồng dư modulo m ký hiệu a a mt 1 e Z . Có m lớp đồng dư phân biệt modulo m thu được bằng cách lấy lần lượt a 1 2 . m. 1 . Một tập hợp ĩi r2 . . rn được gọi là một hệ thặng dư thu gọn modulo m nếu ĩi m 1 ri rj Vi j 1 i j n và với mọi số nguyên x nguyên tố cùng nhau với m thì tồn tại ri sao cho ri x mod m. . Số các phần tử .