tailieunhanh - Bồi dưỡng học sinh giỏi môn Toán THCS: Chủ đề 5 - Ứng dụng đồng dư thức trong giải toán số học

Mời các bạn cùng tham khảo tài liệu "Bồi dưỡng học sinh giỏi môn Toán THCS: Chủ đề 5 - Ứng dụng đồng dư thức trong giải toán số học" sau đây để củng cố kiến thức về lý thuyết cũng như nâng cao kỹ năng giải nhanh các bài tập. Thông qua tài liệu này, các em sẽ ôn tập lại chủ đề ứng dụng đồng dư thức trong giải toán số học. Mời các bạn cùng tham khảo. | BỒI DƯỠNG HỌC SINH GIỎI CẤP 2 5 CHỦ ĐỀ ỨNG DỤNG ĐỒNG DƯ THỨC TRONG GIẢI TOÁN SỐ HỌC A. KiÕn thøc cÇn nhí 1. Định nghĩa Cho a b là các số nguyên và n là số nguyên dương. Ta định nghĩa a đồng dư với b theo môđun n và kí hiệu là a b mod n nếu a và b có cùng số dư khi chia cho n . Chú ý a a b mod m là một đồng dư thức với a là vế trái b là vế phải. b a b mod m a b m t Z sao cho a b mt. c Nếu a và b không đồng dư với nhau theo môđun m ta ký hiệu a b mod m . d Nếu a chia cho b dư r thì a r mod b CHUYÊN ĐỀ SỐ HỌC 2. Tính chất 1. Tính chất phản xạ a a mod m . 2. Tính chất đối xứng a b mod m b a mod m . 3. Tính chất bắc cầu a b mod m b c mod m a c mod m . 4. Cộng hay trừ từng vế của đồng dư thức có cùng môđun a b mod m c d mod m a c b d mod m Tổng quát ai bi mod m i 1 2 . k a1 a2 . ak b1 b2 . bk mod m . 5. a Nhân hai vế của đồng dư thức với một số nguyên a b mod m ka kb mod m với k Z b Nhân hai vế và môđun của đồng dư thức với một số nguyên dương a b mod m ka kb mod km với k N 6. Nhân từng vế của nhiều đồng dư thức có cùng môđun a b mod m c d mod m ac bd mod m Tổng quát ai bi mod m i 1 2 . k a1 a2 .a k b1b2 .bk mod m . 7. Nâng hai vế của một đồng dư thức lên cùng một lũy thừa a b mod m ak bk mod m k N .119 CHUYÊN ĐỀ SỐ HỌC CHỦ ĐỀ 5 ỨNG DỤNG ĐỒNG DƯ THỨC TRONG GIẢI TOÁN SỐ HỌC 8. Nếu hai số đồng dư với nhau theo nhiều môđun thì chúng đồng dư với nhau theo môđun là BCNN của các môđun ấy a b mod mi i 1 2 . k a b mod m1 m2 . mk . Đặc biệt nếu mi m j 1 i j 1 2 . k thì a b mod mi a b mod m1 .m2 .mk . 9. Nếu a b mod m thì tập hợp các ước chung của a và m bằng tập hợp các ước chung của b và m. Đặc biệt a b mod m a m b m 10. Chia hai vế và môđun của một đồng dư cho một ước dương chung của chúng a b m a b mod m k UC a b m k gt 0 mod CHINH PHỤC KỲ THI HỌC SINH GIỎI CẤP HAI k k k m Đặc biệt ac bc mod m a b mod c m B. CÁC DẠNG TOÁN THƯỜNG GẶP Dạng 1 Sử dụng đồng dư thức trong các bài toán chứng minh chia hết Cơ sở phương pháp Khi số dư trong phép chia a cho m bằng 0 thì a m. Như vậy để