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)
Nội dung trích xuất từ tài liệu:
Chuyên đề : ĐỒNG DƯ THỨC Chuyên đề : ĐỒNG DƯ THỨC A.Tóm 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à ướccủ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 = m.q1 (với q1 Z) (1) -1- c ≡ d (mod m) => c - d  m => c - d = m.q2 (với q2  Z) (2)Cộng (1) và (2) vế theo vế ta được : (a - b) + (c - d) = m.(q1 + 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) => a.c ≡ b.d (mod m) *Chứng minh : Ta có : a - b = m.q1 = > a = b + m.q1 (với q1 Z) (1) c - d = m.q2 => c = d + m.q2 (với q2  Z) (2)Nhân (1) và (2) vế theo vế ta được : a.c = (b + m.q1)(d + m.q2)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) => a1.a2.a3. ... .an ≡ b1.b2.b3. ... .bn(mod m)b) a ≡ b (mod m) => an ≡ bn (mod m) - với mọi n  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) => a.b ≡ 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ộtsố 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 a.b có thể đồng dư với 0 theomodule m. Ví dụ : 2 ≡ 0 (mod 10) và 5 ≡ 0 (mod 10), nhưng 2.5 = 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ềukiện .6) Nếu a ≡ b (mod m) và d là ước chung của a, b sao cho (d, m) = 1 a b thì : a : d ≡ b : d (mod m) ( ≡ (mod m) ) d d *Chứng minh :Ta có a ≡ b (mod m) => a - b  m => a - b = mq (1)Chia hai vế của (1) cho d ( vì d là ước chung của a, b => d ≠ 0) a-b m.q a b m.q = - = là số nguyên (vì d là ước của a, b. d d dd d abDo đó - là số nguyên). => mq d , mà (d, m) = 1 => q  d  dd ab a b Vậy - m hay ≡ (mod m)  dd d d7)Nếu a ≡ b (mod m) và d là số nguyên là ước chung của ba số a, b, m ab m thì ≡ (mod ) dd d *Chứng minh :Vì Nếu a ≡ b (mod m) => a - b  m => a - b = mq (1)Và d là ước chung của a, b, m => d ≠ 0. Chia cả hai về (1) cho d -3-a-b m.q ab m ab m m ab = - = . q => - hay là ước của -  d d dd d dd d d dd ab m Vậy : ≡ (mod ) dd d8)Nếu a ≡ r (mod m) với 0 ≤ r < m , thì r chính là số dư trong phép chia a chom.Chứng minh : Ta có a ≡ r (mod m) => a - r = m.q => a = m.q + r (với 0 ≤ r < m)B/Áp dụng : I.Các ví dụ : Dạng 1 : Tìm số dư của phép chiaBà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 11khi và chỉ khi hiệu giữa các tổng chữ số ở hàng lẻ và tổng các chữ số hàngchẵn kể từ trái sang phải chia hết cho 11. ...