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à ướ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)
 2
ac = bd + bmq2 + dmq1 + m q1q2 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 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
 Giải :
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
 Giải :
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 : Chứng minh rằng các số A = 61000 - 1 và B = 61001 + 1 đều là bội số của 7
 Giải :
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 4 : Tìm số dư trong phép chia 15325 - 1 cho 9
 Giải :
Ta có 1532 ≡ 2 (mod 9) => 15325 ≡ 25 (mod 9) , mà 25 ≡ 5 (mod 9)
=> 15325 ≡ 5 (mod 9) => 15325 - 1 ≡ 4(mod 9)
 Vậy 15325 - 1 chia cho 9 dư là 4.
Bài 5 : Chứng minh rằng A = 7.52n + 12.6n chia hết cho 19
 Giải : 
Ta có A = A = 7.52n + 12.6n = A = 7.25n + 12.6n
Vì 25 ≡ 6 (mod 19) => 25n ≡ 6n (mod 19)
=>7.25n ≡ 7.6n (mod 19) => 7.25n + 12.6n ≡ 7.6n + 12.6n ≡ 19.6n ≡ 0 (mod 19) .
Điều này chứng tỏ A chia hết cho 19.
Bài 6 : Tìm dư trong phép chia 32003 cho 13.
 Giải :
Ta có 33 ≡ 1 (mod 13) mà 2003 = 3.667 + 2 => 32003 = (33)667. 32
 33 ≡ 1 => (33)667 ≡ 1667 => (33)667. 32 ≡ 1.32 (mod 13) (33)667. 32 ≡ 9 Bài 11 : Tìm số dư của A = 32005 + 42005 khi chia cho 11 và khi chia cho 13 ?
 Giải :
+Ta có : 35 ≡ 1 (mod 11) => (35)401 ≡ 1 (mod 11)
 Và 45 ≡ 1 (mod 11) => (45)401 ≡ 1 (mod 11)
=> A = 32005 + 42005 ≡ 2 (mod 11)
=> A chia cho 11 dư 2
+Ta có : 33 ≡ 1 (mod 13) => (33)668. 3 ≡ 1.3 (mod 13) => 32005 ≡ 3 (mod 13)
 Và 43 ≡ -1 (mod 13) =>(43)668 .4≡ 1.4 (mod 13) => 42005 ≡ 4 (mod 13)
=> A = 32005 + 42005 ≡ 7 (mod 13)
=> A chia cho 13 dư 7 .
Bài 12 : Giả sử m là số nguyên dương. Chứng minh rằng : Nếu ac1 ≡ ac2 (mod m) và 
(a, m) = 1 thì c1 ≡ c2 (mod m)
 Giải :
Ta có : ac1 ≡ ac2 (mod m) => m \ ac1 - ac2 => m \a(c1 - c2) 
Vì (a, m) = 1 => m \ c1 - c2 => c1 ≡ c2 (mod m)
Bài 13 :
 Chứng minh rằng : Nếu p là một số nguyên tố và không là ước của số nguyên a 
thì ap - 1 ≡ 1 (mod p)
 Giải :
Xét dãy số 1; 2; 3; ... ; p - 1. Tất cả các số này đôi một không đồng dư với nhau theo 
môđun p. Do đó các số a, 2a, 3a, ... ; (p - 1)a cũng đôi một không đồng dư với nhau 
rtheo môđun p. Bởi vì ngược lại nếu có r1a ≡ r2a (mod p) mà (a, p) = 1 => r1 ≡ r2 (mod 
p) - với r1, r2 là hai số nào đó của dãy số 1, 2, 3, ... , p - 1 (vô lí)
Hơn nửa mõi một số của dãy a, 2a, 3a, ... , (p - 1)a đồng dư với đúng một trong các số 
1, 2, 3, ... , p - 1 theo môđun p
=> a.2a.3a. ... .(p- 1)a ≡ 1.2.3......(p - 1) (mod p) hay (p - 1)!ap - 1 ≡ (p - 1)! (mod p).
Vì (p, (p - 1)!) = 1 => ap - 1 ≡ 1 (mod p)
Bài 14 : Chứng minh rằng : Nếu c là số nguyên dương : a ≡ b (mod m) => ac ≡ bc 
(mod c.m)
Giải :
a ≡ b (mod m) => a - b = m.q => ac - bc = mc.q => ac ≡ bc (mod c.m)
*Định lý nhỏ Fermat : Giả sử p là số nguyên tố bất kỳ, khi đó với mọi số tự nhiên n 
ta có np - n chia hết cho p.
 Giải :
Ta có np - n = n(np - 1 - 1)
Nếu n chia hết cho p => định lý được chứng minh.
 Nếu n không chia hết cho p thì (n, p) = 1, nên np - 1 ≡ 1 (mod p)
 =>(np - 1 - 1) chia hết cho p.
Bài 15: Bạn Thắng học sinh lớp 6A đã viết một số có hai chữ số mà tổng các chữ số 
của nó là 14. Bạn Thắng đem số đó chia cho 8 thì được số dư là 4, nhưng khi chia cho 
12 thì được số dư là 3. d) 22009 = 22008.2 = (24)502.2 = 16502.2 = (  6).2 =  2 có chữ số tận cùng là 2 
Ví dụ 2 : Tìm chữ số tận cùng của các số sau :
a) 421 , b) 3103 , c) 84n + 1 (n  N) d) 1423 + 2323 + 7023
Giải :
a) 430 = 42.15 = (42)15 = 1615 = 6 có chữ số tận cùng là 6
 421 = 420 + 1 = (42)10.4 = 1610.4 = (6).4 =  4 có chữ số tận cùng là 4
 Nhận xét : Số nào có số tận cùng là 4 thì khi nâng lên luỹ thừa với số mũ tự 
nhiên chẵn thì có số tận cùng là 6, khi nâng lên với số mũ tự nhiên lẻ có số tận cùng là 
4)
b) 3103 = 3102.3 = (32)51.3 = 951.3 = ( 9).3 =  7 có chữ số tận cùng là 7
c) 84n + 1 = 84n.8 = (23)4n.8 = 212n.8 = (24)3n.8 = 163n.8 = (6).8 = . 8 có chữ số tận
cùng là 8
d) 1423 = 1422.14 = ( 6).14 = . 4
2323 = 2322.23 = (232)11.23 = (  9).23 = 7
7023 =  0
Vậy : 1423 + 2323 + 7023 =  4 +  7 +  0 =  1 có chữ số tận cùng là 1 
b)Tìm hai số tận cùng của số an :
 Ta có nhận xét sau :
 220 ≡ 76 (mod 100)
 320 ≡ 01 (mod 100)
 65 ≡ 76 (mod 100)
 74 ≡ 01 (mod 100) 
Mà 76n ≡ 76 (mod 100) với n ≥ 1
 5n ≡ 25 (mod 100) với n ≥ 2
Suy ra kết quả sau với k là số tự nhiên khác 0. 
a20k ≡ 00 (mod 100) nếu a ≡ 0 (mod 10)
a20k ≡ 01 (mod 100) nếu a ≡ 1; 3; 7; 9 (mod 10)
a20k ≡ 25 (mod 100) nếu a ≡ 5 (mod 10)
a20k ≡ 76 (mod 100 nếu a ≡ 2; 4; 6; 8 (mod 10)
Vậy để tìm hai chữ số tận cùng của an, ta lấy số mũ n chia cho 20
Bài 1 : Tìm hai chữ số tân cùng của 22003 
Giải :
Ta có : 220 ≡ 76 (mod 100) => 220k ≡ 76 (mod 100)
Do đó : 22003 = 23.(220)100 = 8.(220)100 = (  76).8 = 08
Vậy 22003 có hai chữ số tận cùng là 08.
 9
 99
Bài 2 : Tìm hai chữ số tận cùng của B = 7