Chuyên đề Đồng dư thức

www.VIETMATHS.com

- 1 -

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à ướ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 = m.q1 (với q1 Z) (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).

ThuVienDeThi.com

www.VIETMATHS.com

- 2 -

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ộ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.

+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 theo module 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ều kiện . 6) Nếu a ≡ b (mod m) và d là ước chung của a, b sao cho (d, m) = 1

thì : a : d ≡ b : d (mod m) ( a

d

≡ b

d

(mod m) )

*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

d

= m.q

d

<=> a

d

- b

d

= m.q

d

là số nguyên (vì d là ước của a, b.

Do đó a

d

- b

d

là số nguyên). => mq  d , mà (d, m) = 1 => q  d

Vậy a

d

- b

d

 m hay a

d

≡ b

d

(mod m)

7)Nếu a ≡ b (mod m) và d là số nguyên là ước chung của ba số a, b, m

thì a

d

≡ b

d

(mod m

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

a - b

d

= m.q

d

<=> a

d

- b

d

= m

d

.q => a

d

- b

d

 m

d

hay m

d

là ước của a

d

- b

d

ThuVienDeThi.com