Chuyên đề 26: Đồng dư thức - Bồi dưỡng HSG Đại số 8

 Chuyên đề 26. ĐỒNG DƯ THỨC
A. Kiến thức cần nhớ
I. Định nghĩa: Cho số nguyên m 0 . Nếu hai số nguyên a và b khi chia cho m có cùng số dư thì ta nói a 
đồng dư với b theo môđun m và ký hiệu: a  b (mod m).
Chú ý: a) a  b (mod m) là một đồng dư thức với a là vế trái, b là vế phải.
 b) a  b (mod m) a bm t z sao cho a b mt 
 c) Nếu a và b không đồng dư với nhau theo môđun m ta ký hiệu: a b (mod m).
II.Tính chất:
1. Tính chất phản xạ: a  a (mod m)
2. Tính chất đối xứng: a  b (mod m) b  a (mod m)
3. Tính chất bắc cầu: a  b (mod m); b  c (mod m) a  c (mod m).
4. Cộng hay trừ từng vế của đồng dư thức có cùng môđun:
a  b (mod m); c  d (mod m) a c  b d (mod m)
Tổng quát: ai  bi (mod m), i 1;2;...;k a1 a2 ... ak  b1 b2 ... bk (mod m)
5. a) Nhân hai vế của đồng dư thức với một số nguyên: 
a  b (mod m) ka  kb (mod m) với k Z .
b) Nhân hai vế và môđun của đồng dư thức với một số nguyên dương:
a  b (mod m) ka  kb (mod m) với k N* 
6. Nhân từng vế của nhiều đồng dư thức có cùng môđun:
a  b (mod m); c  d (mod m) ac  bd (mod m)
Tổng quát ai  bi (mod m), i 1;2;...;k a1 a2 ...ak  b1 b2 ...bk (mod m)
7. Nâng hai vế của một đồng dư thức lên cùng một lũy thừa:
a  b (mod m) ak  bk (mod m) (k N* ) 
8. Nếu hai số đồng dư với nhau theo nhiều môđun thì chúng đồng dư với nhau theo môđun là BCNN của các 
môđun ấy:
a  b (mod mi) i 1;2;...;k a  b (mod [m1; m2;;mk])
Đặc biệt nếu (mi; mj) = 1 (i; j = 1; 2; ; k) thì a  b (mod mi) a  b (mod m1; m2;;mk)
9. Nếu a  b (mod m) thì tập hợp các ước chung của a và m bằng tập hợp các ước chung của b và m.
Đặc biệt: a  b (mod m) (a,m) (b,m) 
10. Chia hai vế và môđun của một đồng dư cho một ước dương chung của chúng:
 a b m 
a  b (mod m), k UC(a,b,m),k 0  mod 
 k k k 
 m 
Đặc biệt: ac  bc (mod m) a  b mod 
 (c,m) 
III. Một số định lý (ta thừa nhận không chứng minh) b) Hãy tìm hai chữ số tận cùng của 31000. 
 Giải
a) Tìm chữ số tận cùng của một số là tìm dư trong phép chia số đó cho 10.
Vì 92n 1 9.81n  9(mod 10). 
 10
Do 910 là số nên số 99 có chữ số tận cùng là 9.
b) Tìm hai chữ số tận cùng của một số là tìm dư trong phép chia số đó cho 100.
Ta có 34  81  19(mod100) 38  ( 19)2 (mod 100) 
Mà ( 19)2 361  61(mod100) Vậy 38  61(mod100) 
310  61.9 549  49(mod100) 
320  492  01(mod100) (do 492 2401 24.100 1) 
Do đó 31000  01(mod100) nghĩa là hai chữ số sau cùng của 31000 là 01.
2. Dạng toán chứng minh sự chia hết:
Khi số dư trong phép chia a cho m bằng 0 thì am . Như vậy để chứng tỏ am ta chứng minh 
a  0(mod m). 
Ví dụ 4: Chứng minh 42018 79 
 Giải
Ta có 43 64  1(mod 9) 42016 (43 )672  1(mod 9) 
Mặt khác 42 16  7(mod 9) 42018 42016.42  1.7(mod 9) 
Vậy 42018 7  0(mod 9) hay 42018 79 
Ví dụ 5: Chứng minh rằng 122n 1 11n 2 133(n N) 
 Giải
Cách 1: Ta có 122 144  11(mod133); 112 121  12(mod 133) 
Do đó 122n 1 12.(122 )n  12.11n (mod133) 
11n 2 112.11n  12.11n (mod133) 
Do đó 122n 1 11n 2  12.11n 12.11n  0(mod133) 
Vậy với n N thì 122n 1 11n 2 133 
Cách 2: Ta có 122 144  11(mod133) 122n  11n (mod133) (1)
Mà 12  112 (mod133) (2) Nhân vế với vế của (1) và (2) ta có:
122n.12  11n.( 112 )(mod 133) 122n 1  11n 2 (mod133) 
122n 1 11n 2  0(mod133) hay 122n 1 11n 2 133 
3. Dạng toán xác định dấu hiệu chia hết
Ví dụ 6: Cho số a anan 1...a1a0 (1 an 9; 0 ai 9; i 0;1;...;n 1) Theo tính chất nếu hai số đồng dư với nhau theo nhiều môđun thì chúng đồng dư với nhau theo môđun là 
BCNN của các môđun ấy.
Do đó a5  a(mod 2.3.5) hay a5  a(mod30) a5 a  0(mod30) 
 5 5 5 5
Nghĩa là a1 a2 a3 ... a2016 a1 a2 ... a2016  0(mod30) 
 5 5 5 5
Vậy a1 a2 ... a2016 30 a1 a2 a3 ... a2016 30 
Ví dụ 9: Chứng minh rằng trong các số tự nhiên thế nào cũng có số k sao cho 1983k 1 chia hết cho 105 
 (Đề thi học sinh giỏi toán cấp 2 toàn quốc năm 1983).
 Giải
Vì 1983 không chia hết cho 2 và không chia hết cho 5 mà 105 25.55 nên (1983;105 ) 1. Áp dụng định lý 
Euler ta có:
 5
1983 (10 )  1(mod105 ) 
 5 5 1 1 4 4.104 5
Ta có (10 ) 10 1 1 4.10 . Nghĩa là 1983 110 
 2 5 
Vậy k 4.104. 
5. Dạng toán khác
Ví dụ 10: Chứng minh rằng 14k 24k 34k 44k không chia hết cho 5.
 Giải
Do 5 là số nguyên tố nên theo Định lý Fermat bé ta có: với a = 1; 2; 3; 4 ta có:
a5  a(mod 5) a4  1(mod 5) a4k  1(mod 5). 
Do đó 14k 24k 34k 44k  1 1 1 1  4(mod 5) 
Chứng tỏ 14k 24k 34k 44k 5 
Ví dụ 11: Chứng minh rằng với mỗi số nguyên tố p tồn tại vô số số có dạng 2n n,(n N) chia hết cho p. 
 (Thi vô địch Canada năm 1983).
 Giải
* Nếu p 2 thì 2n n2,n 2k (k N) 
* Nếu p 2 do (2; p) 1 nên theo định lý Fermat bé ta có:
 2 k
2 p 1  1(mod p) 2 p 1 1  0(mod p) 2( p 1) 1  0(mod p) 
 2 k
Hay là 2( p 1) 1 p (k N;k 2) 
Mặt khác (p 1)2k  ( 1)2k  1(mod p) 
 ( p 1)2 k 2k ( p 1)2 k 2k
 2 (p 1) 2 1 (p 1) 1  p 
   
 p p
Vậy tồn tại vô số số tự nhiên n có dạng n (p 1)2k ,(k N;k 2) sao cho 2n n p Hướng dẫn giải – đáp số
a) Ta có 352 1225 425.3 50  50(mod 425) 
353 352.35  50.35  1750  50(mod 425)
354 (352 )2  ( 50)2  2500  50(mod 425)
Tương tự với 358;3516 ;3532. Từ đó có A  100(mod 425) 
Hay số dư trong phép chia A cho 425 là 325
b) Ta có 105 7.14285 5  5(mod 7); 106 5.10  1(mod 7) 
 n n
10 4 99...96  0(mod 2) và 99...96  0(mod3) 10 4  0(mod6) 
 n 1 sè 9 n 1sè 9
 10n  4(mod 6) và 10n 6k 4(k,n N * ) 
 n
Do đó 1010 106k 4 (106 )k .104 104 (mod 7)
Vậy B 104 104 104 ... 104 10.104 105  5(mod 7) 
 2
26.4. a) Tìm chữ số tận cùng của 43 
b) Tìm hai chữ số tận cùng của 3999 
c) Tìm ba chữ số tận cùng của số 2512 
 Hướng dẫn giải – đáp số
a) Ta tìm dư trong phép chia số đó cho10.
 2
Vì 42  6(mod10) nên 43 49 (42 )4.4  6.4  4(mod10) chữ số tận cùng là 4
b) Ta tìm dư trong phép chia số đó cho 100. Theo ví dụ 3 chuyên đề 26 ta đã có 31000  01(mod100) nghĩa là 
hai chữ số sau cùng của 31000 là 01. Số 31000 là bội số của 3 nên chữ số hàng trăm của nó khi chia cho 3 phải 
có số dư là 2 để chia tiếp thì 201 chia hết cho 3 (nếu số dư là 0 hay 1 thì 001; 101 đều không chia hết cho 3). 
Vậy số 3999 31000 :3 có hai chữ số tận cùng bằng 201 : 3 =67.
c) Ta tìm dư trong phép chia đó cho 1000. Do 1000 = 125.8 trước hết ta tìm số dư của 2512 cho 125. Từ hằng 
đẳng thức:
 a b 5 a5 5a4b 10a3b2 10a2b3 5ab4 b5 ta có nhận xét nếu a25 thì a b 5  b5 (mod125) 
Vì 210 1024  1(mod 25) nên 210 25k 1(k N).
Từ nhận xét trên ta có 250 (210 )5 (25k 1)5  1(mod125) 
Vì vậy 2512 (250 )10.212  ( 1)10.212  212 (mod125) 
Do 212 210.22 1024.4  24.4  96(mod125) 
Vậy 2512  96(mod125) 
Hay 2512 125m 96, m N 
Do 2512 8,968 nên m8 m 8n(n N) Hay 43333 1  0(mod 7). Do đó 55552222 22225555  0(mod 7)
 và 155541111 (2.7777)1111 21111.77771111  0(mod 7) đpcm
b) Ta có 102 2.3.17. Ta có (220 119 69)102  0(mod102) 
* 220  0(mod 2); 119  1(mod 2); 69 1(mod 2) M  0(mod 2) 
* 220 1(mod3); 119  1(mod3); 69  0(mod3) M  0(mod3)
* 220  1(mod17); 119  0(mod17); 69 1(mod17) M  0(mod17) 
(Để ý 11969 và 69220 là các số lẻ); M  0(mod 2.3.17). Hay M 102 
26.8. Chứng minh rằng 52n 12n 1 22n 13n 1 38 (n N* ) 
 Hướng dẫn giải – đáp số
Đặt A 52n 12n 1 22n 13n 1. Ta có A2,n N *; 
Ta có A 2n (52n 12 2n 13n 1) 2n (25n 110 6n 19)
Do 25  6(mod19) A  2n (6n 110 6n 19)  2n6n 119  0(mod19) 
Hay A19. Mà (2;9) 1 A19.2 A38 
Dạng toán xác định dấu hiệu chia hết
26.9. Cho số a anan 1...aiao (1 an 9; 0 ai 9; i 0;1;...;n 1) 
Hãy xác định dấu hiệu chia hết:
a) Cho 9. b) Cho 25. c) Cho 11. d) Cho 8.
 Hướng dẫn giải – đáp số
 n n 1
Ta có : a anan 1...a1ao an .10 an 110 ... a110 ao 
 i
a) Ta có 10 1(mod9) do đó ai10  ai (mod9),i 1;2;3;...;n 
do đó a  an an 1 ... a1 ao (mod9). Vậy
a9 an an 1 ... a1 ao  0(mod9) an an 1 ... a1 ao 9 
 2 i
b) Ta có 10 100  0(mod 25) ai10  0(mod 25),i 2;3;...;n 
 a  (a110 ao )(mod 25) 
Vậy a25 a110 ao  0(mod 25) a1ao 25 
 i i
c) Do 10  1(mod11) ai .10  ai ( 1) (mod11) 
a  (ao a2 a4 ...) (a1 a3 a5 ...)(mod11) 
Do đó a11 (ao a2 a4 ...) (a1 a3 a5 ...)  0(mod11) 
Tức là hiệu của tổng các chữ số ở vị trí lẻ và tổng các chữ số ở vị trí chẵn bằng 0.
 3 i
d) Ta có 10 1000  0(mod8) ai10  0(mod8),i 3;4;...;n 
 2
 a  (a210 a110 ao )(mod8)