Chuyên đề 16: Đồng dư thức - Bồi dưỡng Học sinh giỏi Toán 8

 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à 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)
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 (mod4) 
 a ≡ b (mod m) và c ≡ d (mod m) => 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)
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).
 1 Vậy 3100 chia cho 7 dư 4.
 32
* Cách 2: 3100 34.396 34. 33 
 4
+ 3 81  4 mod 7 (1)
 3
+ 33 27  6 mod 7 mà 6  1 mod 7 3  1 mod 7 
 32 32 32
Do đó, 33  1 mod 7 33 1 mod 7 (2)
 32
Từ (1) và (2) 34. 32  4.1 mod 7 3100  4 mod 7 
Vậy 3100 chia cho 7 dư 4.
Bài 4 : CMR 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 5: Tìm số dư khi chia tổng 3100 3105 cho 13
 Giải
* Tìm số dư khi chia 3100 cho 13: là tìm số tự nhiên nhỏ hơn 13, đồng dư với 3100 
theo modun 13
 32
Ta có: 3100 34.396 34. 33 
+) 34 81 13.6 3 34  3 mod13 (1)
+) 33 27 13.2 1 33 1 mod13 
 3 32 32 3 32
 3 1 mod13 3 1 mod13 (2)
 4 3 32 100
Từ (1) và (2) 3 . 3  3.1 mod13 3  3 mod13 (1)
 35
Mặt khác: 3105 33 
 35 105
Mà 33 27 1 mod13 33 135 mod13 Hay 3 1 mod13 (2)
Từ (1) và (2) 3100 3105  3 1 mod13 3100 3105  4 mod13 
 100 105
Vậy tổng 3 3 chia cho 13 dư 4
Bài 6 : Tìm số dư trong phép chia 15325 - 1 cho 9
 3 => 22225555 + 55552222 ≡ (- 4)5555 + 42222 (mod 7) 
Mà 42222 = (-4)2222 => (- 4)5555 + 42222 = (-4)2222. 43333 + 42222 
 = (-4)2222. 43333 - (- 4)2222 = (-4)2222(43333 - 1) ≡ (43) - 1(mod 7) (1)
Ta lại có : 43 ≡ 1(mod 7) => 43 - 1= 63  7 => 43 - 1 ≡ 0 (mod 7) (2)
 Nên (- 4)5555 + 42222 ≡ 0 (mod 7) 
Từ (1) và (2) => 22225555 + 55552222 chia hết cho 7.
Bài 12 : Tìm dư trong phép chia 570 + 750 cho 12
 Giải :
Ta có 52 ≡ 1(mod 12) => (52)35 ≡ 1 (mod 12) hay 570 ≡ 1(mod 12) (1)
72 ≡ 2 (mod 12) => (72)25 ≡ 1(mod 12) hay 750 ≡ 1(mod 12) (2)
 Từ (1) và (2) => 570 + 750 chia cho 12 dư 2.
Bài 13 : Tìm số dư của A = 776776 + 777777 + 778778 khi chia cho 3 và khi chia 
cho 5?
 Giải :
+Ta có 776 ≡ - 1(mod 3) => 776776 ≡ -1(mod 3) => 776776 ≡ 1 (mod 3)
 777 ≡ 0 (mod 3) => 777777 ≡ 0 (mod 3)
 778 ≡ 1 (mod 3) => 778778≡ 1 (mod 3)
=> 776776 + 777777 + 778778 khi chia cho 3 dư 2.
+Ta có 776 ≡ 1 (mod 5) => 776776 ≡ 1 (mod 5)
 777 ≡ - 3 (mod 5) => 777777 ≡ - 3777 (mod 5)
 778 ≡ 3 (mod 5) => 778778 ≡ 3778 (mod 5)
 => 776776 + 777777 + 778778 ≡ 1 - 3777 + 3778 (mod 5)
 Hay 776776 + 777777 + 778778 ≡ 1 + 3.3777 - 3777 (mod 5)
 776776 + 777777 + 778778 ≡ 1 + 3777(3 - 1) (mod 5)
 776776 + 777777 + 778778 ≡ 1 + 2.3777
Mà 32 ≡ - 1(mod 3) => (32)388.3 ≡ 3 (mod 5)
Vậy A = 776776 + 777777 + 778778 ≡ 1 + 2.3 ≡ 2 (mod 5)
 Vậy A chia cho 5 dư 2.
Bài 14 : 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) 
 5 Từ (1) và (2) => ab ≡ 8 (mod 12) => n chia cho 12 dư 8
Do n = 8p + 4 là số chẵn mà n = ab => b {0; 2; 4; 6; 8}
Nếu b = 0 => a = 14 (loại - vì a là số có một chữ số khác 0)
 b = 2 => a = 12 (loại)
 b = 4 => a = 10 (loại)
 b = 6 => a = 8
 b = 8 => a = 6
=> Số cần tìm là 86 hoặc 68 => Số bị chia là 68.
Bài 19: Biết rằng ngày 20 / 11/1994 là ngày chủ nhật. Tính xem:
a) Ngày 20 / 11/1996 là ngày thứ mấy?
b) Ngày 20 / 11/2011 là ngày thứ mấy?
 Giải
a) Vì 1996 chia hết cho 4 nên năm 1996 là năm nhuận, có 366 ngày. 
Từ 20 / 11/1994 đến 20 / 11/1996 là 2 năm, có:
 365 . 2 + 1 (nhuận) = 731 (ngày)
Biết rằng cứ mõi tuần lễ có 7 ngày.
Ta có: 731 = 7. 104 + 3 hay 731  3 mod 7 
Như vậy, 731 ngày gồm 104 tuần và lẻ 3 ngày.
Do đó, nếu ngày 20 / 11/1994 là ngày chủ nhật thì 20 / 11/1996 là ngày thứ 4.
b) Từ 20 / 11/1994 đến 20 / 11/2011 là 17 năm có 4 năm nhuận là 1996, 2000, 
 2004, 2008. Vậy Từ 20 / 11/1994 đến 20 / 11/2011 có:
 365 . 17 + 4 (nhuận) = 6209 (ngày)
Biết rằng cứ mõi tuần lễ có 7 ngày.
Ta có: 6209 = 7 . 887 Hay 6209  0 mod 7 
Như vậy, 6209 ngày gồm 887 tuần 
Do đó, nếu ngày 20 / 11/1994 là ngày chủ nhật thì 20 / 11/1996 cũng là ngàychủ 
nhật.
Dạng 2 : Tìm chữ số tận cùng của một số
a)Tìm một chữ số tận cùng của an :
-Nếu a có chữ số tận cùng là 0; 1; 5 hoặc 6 thì an lần lượt có chữ số tận cùng lần 
lượt là 0; 1; 5 hoặc 6.
-Nếu a có chữ số tận cùng là 2, 3 hoặc 7, ta vận dụng nhận xét sau với k Z
 24k ≡ 6 (mod 10)
 34k ≡ 1 (mod 10)
 74k ≡ 1 (mod 10)
 Do đó để tìm chữ số tận cùng của an với a có chữ số tận cùng là 2; 3; 7 ta 
lấy n chia cho 4. Giả sử n = 4k + r với r {0; 1; 2; 3}
 Nếu a ≡ 2 (mod 10) thì an ≡ 2n = 24k + r ≡ 6.2r (mod 10) 
 7 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.
Bài 2: Tìm hai chữ số tận cùng của:
a) 2999
b) 3999
 Giải
 999 1000
a) Ta thấy 2 2 : 2 (1)
 100
mà 21000 = 210 
 100
Ta có: 210 1024  1 mod 25 210  1 100 mod 25 
 21000 1 mod 25 Hay 21000 chia cho 25 dư 1, do đó hai chữ số tận cùng của 
21000 có thể là 01; 26; 51; 75, nhưng 21000 là bội của 4 nên hai chữ số tận cùng 
của nó phải là 76 (2)
Từ (1) và (2) ta thấy số 76 chia 2 thì hai chữ số tận cùng là 38 (= 76:2) hoặc 
88(=186:2) nhưng cũng do 2999 cũng là bội của 4 nên hai chữ số tận cùng của 2999 
là 88.
b) 3999 31000 :3
Ta có: 34 = 81  19 mod100 
 38 192  61 mod100 
 310  61.9  49 mod100 
 3100  4910  01 mod100 
 1000
 3  01 mod100 , nghĩa là hai chữ số tận cùng của 31000 là 01. Số 31000 là 
bội của 3 nên chữ số hang trăm của nó khi chia cho 3 phải dư 2( Chia tiếp thì số 
201 chia hết cho 3, nếu số dư là 0 hay 1 thì số 001, 101 không chia hết cho 3)
Vậy 3999 31000 :3 có hai chữ số tận cùng là 76 (= 201 : 2)
 9