tailieunhanh - Chuyên đề : ĐỒNG DƯ THỨC

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à bội của 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) | Chuyên đề ĐỒNG DƯ THỨC tắt các kiến thức cơ bản I Đị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à bội của 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 II Các tính chất cơ bản 1 Với mọi số nguyên a ta có a - a mod m 2 a - b mod m b - a mod m 3 a - b mod m và b - c mod m a - c mod m Chứng minh Ta có a - b mod m a - b m m a - b và b - c mod m b - c m m b - c Vì a - c a - b b - c a - c m tính chất chia hết của tổng hay a - c mod m . 4 a - b mod m và c - d mod m a c - b d mod m Chứng minh Ta có a - b mod m a - b m a - b với q1 e Z 1 - 1 - c d mod m c - d m c - d với q2 e Z 2 Cộng 1 và 2 vế theo vế ta được a - b c - d m. qi q2 a c - b d m. q1 q2 a c - b d m Hay a c b d mod m Hệ quả a1 b1 mod m a2 b2 mod m . an bn mod m a1 a2 a3 . an b1 b2 b3 . bn mod m 5 a b mod m và c d mod m mod m Chứng minh Ta có a - b a b với q1e Z 1 c - d c d với q2 e Z 2 Nhân 1 và 2 vế theo vế ta được b d ac bd bmq2 dmq1 m2q1q2 ac - bd m bq2 dq1 mq1q2 ac - bd m ac bd mod m . Hệ quả a a1 b1 mod m a2 b2 mod m . an bn mod m mod m b a b mod m an bn mod m - với mọi n e N Nhận xét a a 1 mod 2 và b 1 mod 2 a b 2 mod 2 Mà 2 0 mod 2 a b 0 mod 2 a 1 mod 2 và b 1 mod 2 1 mod 2 Điều này có nghĩa Tổng của hai số lẻ là một số chẵn tích của hai số lẻ là một số lẻ. b a 3 mod 7 a2 9 mod 7 2 mod 2 Điều này có nghĩa Nếu một số chia 7 dư 3 thì bình phương số đó chia 7 dư 2. - 2 - Chú ý a Không được chia hai vế của một đồng dư thức . Ví dụ 2 12 mod 10 nhưng 1 6 mod 10 . b a 0 mod m và b 0 mod m nhưng có thể đồng dư với 0 theo module m. Ví dụ 2 0 mod 10 và 5 0 mod 10 nhưng 10 10 mod 10 . Như vậy để phép chia hai vế của đồng thức đòi hỏi phải kèm theo một số điều kiện . 6