Nội dung text CĐ16. Đồng dư thức.Image.Marked.pdf
Chúc các em chăm ngoan – học giỏi !! Trang 1 CHUYÊN ĐỀ: ĐỒNG DƯ THỨC I.Lí Thuyết 1.Định nghĩa : Cho m là số nguyên dương. Hai số nguyên a và b được gọi đồng với nhau theo module m, nếu a - b chia hết cho m ( a - b )| m hay m\(a - b) Ký hiệu : a ≡ b (mod m) được gọi là một đồng dư thức. Ví dụ : 3 ≡ - 1 (mod 4) 5 ≡ 17 (mod 6) 18 ≡ 0 (mod 6) Điều kiện a ≡ 0 (mod m) có nghĩa là a là bội của m, k/h: a m (a | m) hay m là ước của a ( m \ a) . Nếu a - b không chia hết cho m, ta viết a ≡ b (mod m) 2. Các tính chất cơ bản : Cho thì : * a,b,c,d,e Z;m,n N a. Tính chất phản xạ : a a(modm) b. Tính chất đối xứng : a b(modm) b a(modm) c. Tính chất bắc cầu : a b(modm);b c(modm) a c(modm) d. (mod ) (mod ) (mod ) . . (mod ) (mod ) (mod ) . . (mod ) a c b d m a c b d m a b m a c b d m c d m a e b e m a e b e m e. (mod ) (mod ) n n a b m a b m f. a b(modm) a.n b.n(modm.n) g. (mod ) (mod ) với a b a b m m e e eUC(a,b);(e,m) 1 h. a b(modm);a b(modm') a b(modm,m')
Chúc các em chăm ngoan – học giỏi !! Trang 2 k. ac bc(modm);(c,m) 1 a b(modm) 3. Định lý Fermat nhỏ: Cho a là số nguyên và p là số nguyên tố, khi đó : (mod ) p a a p Đặc biệt: Nếu 1 ( , ) 1 1(mod )( ) p a p a p p P II. Các dạng bài tập Dạng 1 : Tìm số dư của phép chia Bài 1 : Tìm số dư trong phép chia 20042004 cho 11 Sử dụng dấu hiệu chia hết cho 11 : Một số được gọi là chia hết cho 11 khi và chỉ khi hiệu giữa các tổng chữ số ở hàng lẻ và tổng các chữ số hàng chẵn kể từ trái sang phải chia hết cho 11. Ví dụ : Xét xem số 5016 có chia hết cho 11 ? Ta có (5 + 1) - (0 + 6) = 0. Vì 0 11 = > 5016 11 HD: Ta có 2002 11 => 2004 - 2 11 => 2004 ≡ 2 (mod 11) => 20042004 ≡ 22004 (mod 11) , mà 210 ≡ 1 (mod 11) (vì 1024 - 1 11) => 20042004 = 24 .22000 = 24 .(210) 200 ≡ 24 ≡ 5 (mod 11) Vậy 20042004 chia 11 dư 5. Bài 2 : Tìm số dư khi chia A = 19442005 cho 7 HD: Ta có : 1944 ≡ -2 (mod 7) => 19442005 ≡ (-2)2005 (mod 7) Mà (-2)3 ≡ - 1 (mod 7) => (-23 ) 668 ≡ 1668 (mod 7) hay (-23 ) 668 ≡ 1 (mod 7) => (-23 ) 668.(-2) ≡ - 2 (mod 7) hay (-2)2005 ≡ - 2 (mod 7) Vậy 19442005 cho 7 dư 5. Bài 3: Tìm số dư khi chia cho 7 100 3 HD: Ta có: 16 100 4 96 4 6 3 3 .3 3 . 3 Ta thấy: (1) 4 4 3 81 7.11 4 3 4 mod 7
Chúc các em chăm ngoan – học giỏi !! Trang 3 (2) 6 6 16 16 6 6 6 3 729 7.104 1 3 1 mod 7 3 1 mod 7 3 1 mod 7 Từ (1) và (2) 16 4 6 100 3 . 3 4.1 mod 7 3 4 mod 7 Vậy chia cho 7 dư 4. 100 3 Cách 2: 32 100 4 96 4 3 3 3 .3 3 . 3 (1) 4 3 81 4 mod 7 mà 3 3 27 6 mod 7 6 1mod 7 3 3 1 mod 7 Do đó, (2) 32 32 32 3 3 3 1 mod 7 3 1 mod 7 Từ (1) và (2) 32 4 2 100 3 . 3 4.1 mod 7 3 4 mod 7 Vậy chia cho 7 dư 4. 100 3 Bài 4 : CMR các số A = 61000 - 1 và B = 61001 + 1 đều là bội số của 7 HD: Ta có 6 ≡ - 1 (mod 7) => 61000 ≡ 1 (mod 7) => 61000 - 1 7 Vậy A là bội của 7 Từ 61000 ≡ 1 (mod 7) => 61001 ≡ 6 (mod 7) , mà 6 ≡ - 1 (mod 7) => 61001 ≡ -1 (mod 7) => 61001 + 1 7 Vậy B là bội của 7 Bài 5: Tìm số dư khi chia tổng cho 13 100 105 3 3 HD: Tìm số dư khi chia cho 13: là tìm số tự nhiên nhỏ hơn 13, đồng dư với theo 100 3 100 3 modun 13 Ta có: 32 100 4 96 4 3 3 3 .3 3 . 3 (1) 4 4 3 81 13.6 3 3 3 mod13