Chuyên đề bồi dưỡng Toán Lớp 8 - Chuyên đề: Đồng dư thức (Có đáp án)

 ĐỒNG DƯ THỨC
1. Định nghĩa : Cho a,b Z;m N * a được gọi là đồng dư với b theo modunlo m nếu a và b có 
cùng số dư khi chia cho m. Kí hiệu là : a  b(mod m) 
Vậy a  b(mod m)  (a b)m 
2. Tính chất : Cho a,b,c,d,e Z;m,n N * thì :
a. Tính chất phản xạ : a  a(mod m)
b. Tính chất đối xứng : a  b(mod m) b  a(mod m)
c. Tính chất bắc cầu : a  b(mod m);b  c(mod m) a  c(mod m)
 a c  b d(mod m)
 a c  b d(mod m)
 a  b(mod m) 
d.  a.c  b.d(mod m)
 c  d(mod m)
  a e  b e(mod m)
 a.e  b.e(mod m)
e. a  b(mod m) an  bn (mod m)
f. a  b(mod m) a.n  b.n(mod m.n)
 a b
g. a  b(mod m)  (mod m) với e UC(a,b);(e,m) 1 
 e e
h. a  b(mod m);a  b(mod m') a  b(modm,m')
k. ac  bc(mod m);(c,m) 1 a  b(mod m)
3. Định lý Fermat nhỏ: Cho a là số nguyên và p là số nguyên tố, khi đó : a p  a(mod p)
+) Đặc biệt: Nếu (a, p) 1 a p 1 1(mod p)( p P) 
4. Các dạng toán
Dạng 1 : Tìm số dư của phép chia
Bài 1: Tìm số dư
a. 9294 cho 15 b. 19442005 cho 7 
 1 c. A 15325 1 cho 9 d. A 32003 cho 13
e. A 570 750 cho 12 f. A 32005 42005 cho 11 và 13
Lời giải
a. Ta có: 92  2(mod15) 9294  294 (mod15)(1) 
Lại có: 24 1(mod15) (24 )23 123 (mod15) (24 )23.22  4(mod15)  294  4(mod15)(2) 
Từ (1)(2) du : 4
b. Ta có: 1994  2(mod7) 19942005  ( 2)2005 (mod7)
Lại có: ( 2)3  1(mod7) ( 23 )668.( 2)  ( 2)(mod7)  ( 2)2005  2(mod7) 
 19442005 chia cho 7 dư 5
c. Ta có: 
1532  2(mod9) 15325  2 5 (mod9);25  5(mod9) 15325  5(mod9) 15325 1  4(mod9) 
Vậy số dư là : 4
d. Ta có: 33 1(mod13);2003 3.607 2 3203 (33 )667.32 
 33 1(mod13) (33 )667 1667 (33 )667.32  9(mod13) du : 9
e. Ta có: 52 1(mod12) (52 )35 1(mod12) 570 1(mod12)(1) 
 72 1(mod12) (72 )25 125 (mod12) 750 1(mod12)(2)
Từ (1)(2) A 570 750 chia cho 12 dư 2 
f. Ta có: 35 1(mod11) (35 )401 1(mod11);45 1(mod11) (45 )401 1(mod11)
 A 32005 42005  2(mod11) du : 2
+) 33 1(mod13) (33 )668.3 1.3(mod13) 32005  3(mod13);43  1(mod13) (43 )668.4 1.4(mod13)
 42005  4(mod13) A 32005 42005  7(mod13) du : 7 
Bài 2: Chứng minh rằng
a. 22002 4 chia hết cho 31 b. 22225555 55552222 chia hết cho 7 
 2 c. 2014200 256 chia hết cho 2016 
Lời giải
a. 25 1(mod31);2002 5.400 2 22002 (25 )400.22 ;25 1(mod31) (25 )400 1400 (mod31)
 (25 )400.22 1.22 (mod31) 22002  4(mod31) 22002 4 chia hết cho 31 
b. Ta có: 2222  3(mod7) 22225  35 (mod7)  5(mod7) 22225555  51111(mod7)(1) 
Lại có : 5555  4(mod7) 55552  42  2(mod7) 55552222  51111(mod7)(2)
Từ (1)(2) 22225555 55552222  51111 21111(mod7)(3)
Mặt khác : 5  2(mod7) 51111  ( 2)1111  21111(mod7) 51111 21111  0(mod7)(4)
Từ (3)(4) 22225555 55552222 7
c. Ta có: 
 20143  2008(mod 2016);20142  4(mod 2016) 20145  20143.20142  2008.4 1984(mod 2016) 
 201410 (20145 )2 19842 1024(mod 2016) 201430 10243  64(mod 2016)
 2014200 10242  256(mod 2016) 2014200 2562016
Bài 3: Chứng minh rằng : A 7.52n 12.6n chia hết cho 19 với mọi số tự nhiên n
Lời giải
Ta có: A 7.52n 12.6n 7.25n 12.6n
Lại có : 
 25  6(mod19) 25n  6n (mod19) 7.25n  7.6n (mod19) 7.25n 12.6n  7.6n 12.6n (mod19)
 7.25n 12.6n 19.6n  0(mod19) A 7.52n 12.6n 19n N
Bài 4: Chứng minh rằng : A 42n 1 3n 2 13n N 
Lời giải
Ta có: 42  3(mod13) (42 )n  3n (mod13) 4.(42 )n  4.3n (mod13) 42n 1  4.3n (mod13)(1)
Lại có: 
 32  4(mod13) 3n.32  4.3n (mod13) 3n 2  4.3n (mod13)(2) 42n 1 3n  4.3n 4.3n 0(mod13)
 3 A 42n 1 3n 2 13n N
Bài 5: Tìm số dư : A 776776 777777 778778 chia cho 3 và 5 
Lời giải
Ta có: 776  1(mod3) 776776  ( 1)776 (mod3) 776776 1(mod3)
 777  0(mod3) 777777  0(mod3);778 1(mod3) 778778 1(mod3) A chia 3 dư 2
+) Lại có: 776 1(mod5) 776776 1(mod5);777  3(mod5) 777777  ( 3)777 (mod5) 
 778778  3778 (mod5) A 1 3777 3778 (mod5) A 1 3.3777 3777 (mod5) 1 3777 (3 1)(mod5)
 1 2.3777 (mod5);32  1(mod5) (3 2 )338.3  3(mod5) A 1 2.3  2(mod5)
Vậy A chia 5 dư 2
Bài 6: Chứng minh rằng
a. 2015 1 chia hết cho 11 b. 230 320 chia hết cho 30 
c. 555222 222555 chia hết cho 7 d. 123430 1388 chia hết cho 2014 
Lời giải
a. 25  1(mod11);10  1(nod11) 105  1(mod11) 25.105 1(mod11) 205 1(mod11)
 205 1  0(mod11)
b. 26  1(mod13) 230  1(mod13);33 1(mod13) 330 1(mod13)
 230 320  1 1(mod13)  0(mod13)
c. 555  2(mod7) 555222  2222 (mod7);23 1(mod7) (23 )74 1(mod7) 555222 1(mod7)
 222  2(mod7) 222555  ( 2)555 (mod7)
 3 3 185 555
Có: ( 2)  1(mod7) ( 2)  1(mod7) 222  ( 1)(mod7) A 1 1(mod7)  0(mod7)
d. Ta có : 123430  778(mod 2014) 12349  7783 1500(mod 2014) 12347 15003 1234(mod 2014)
 12343.123427  778.1234(mod 2014) 123430 1234.1234.778 1388(mod 2014) (123430 1388)2014
 4 Bài 7: Tìm số dư trong phép chia A (19971998 19981999 19992000 )10 chia cho 111 
Lời giải
Ta có: 1998  0(mod11);1997  1(mod11) 19971998 1(mod11);1999 1(mod11) 19992000 1(mod11)
 A  (1 0 1)10  210 1024  25(mod111) A chia 111 dư 25. 
Bài 8: Sử dụng định lý Fermat nhỏ
 2 3 10
Chứng minh rằng : A 1010 1010 1010 ... 1010 57 
Lời giải
Vì 7 là số nguyên tố nên (10,7) = 1 nên theo định lý Fermat nhỏ ta có :
106 1(mod7) 106k 1k 1(mod7)
 n n n
 Với mọi số tự nhiên n khác 0 thì : 10 2 1000....022,3 (10 2)6 10  4(mod6)
 n 1
 n
Đặt 10n 6k 4(k N) 1010 106k 4 106k.104 1.14 (mod7) 104 (mod7) 1010 104 (mod7)
 2 3 10
1010 104 (mod7);1010 104 (mod7).......;1010 104 (mod7) A 10.104 5  0(mod7) A7
Bài 9: Sử dụng định lý Fermat nhỏ
Chứng minh rằng : A 11331 21331 31331 ... 1331133111 
Lời giải
Vì 11 là số nguyên tố nên theo định lý Fermat nhỏ ta có : a11 11(mod11)a Z
 a121 (a11)11  a11  a(mod11) a1331 (a121)11  a11(mod11)  a(mod11) 
Áp dụng kết quả trên ta được : 
11331 21331 .... 13311331 1 2 .... 1331  886446  0(mod11) A11
Bài 10: Chứng minh rằng : a5  a(mod30)a Z
Lời giải
 30 2.3.5 6.5;a5 a a(a4 1) a(a2 1)(a2 1) a(a 1)(a 1)(a2 1)
Ta có : 
 6
 5 Ta cần chứng minh : a5  a(mod5)
+) Nếu a  0(mod5) a5  0  a(mod5)
+) Nếu a  1(mod5) a5  ( 1)5  a(mod5)
+) Nếu a  2(mod5) a5  ( 2)5  32  2  a(mod5)
Vậy a5  a(mod5) a p  a(mod p)
 22
Bài 11: Chứng minh rằng : A (2222 22)3234
Lời giải
Ta có : 3234 3.22.72
+) Có : A  0(mod 22)
+) 22 1(m0d3) 2222 1(mod3)
+) 22 1(m0d7) 2222 122 1(mod7) 2222 7k 1
 7k 1 7k k 7 k k 6 k 5 k
 A 22 22 22(22 1) 22 (22 ) 1 22.(22 1) (22 ) (22 ) ... 22 1 
+) 22 1(m0d7) 22k 1k 1(mod7)
 k 6 k 5 k
Đặt B (22 ) (22 ) .... 22 1 B 1 ... 1  7  0(mod7) A  0(mod 49)
 7.chu.so.1
Vậy A  0(mod3.22.49) dpcm
 ....7
Bài 12: Chứng minh rằng : A (77 77)20 ( Có 100 chữ số 7 )
Lời giải
Ta có : 20 = 4. 5
 ...7
Đặt B 77 (997.chu.so.7) A: le
 A 7B 77  ( 1)B 1  1 1  0(mod 4)(1)
Ta có : B  ( 1)(mod 4) B 4k 3(k N * );7B  2B  24k 3 16k.8 1k.3  3(mod5)
 A  3 77  80  0(mod5)(2) A  0(mod 20)(vì:(4,5)=1)
 6 Bài 13: Chứng minh rằng : A 1n 2n 3n 4n 5  n/ 4(n N * )
Lời giải
+) n 4k A 1 16k 81k ( 1)4k
+) n 4k 1 A 1 16k.2 81k.3 ( 1)4k .4 1 2 3 4 10  0(mod5)
+) n 4k 2 A 1 16k.22 81k.32 ( 1)4k .42 1 4 9 16  30  0(mod5)
+) n 4k 3 A 1 16k.23 81k.33 ( 1)4k .43 13 43 22 32  0(mod5)
Vậy A luôn chia hết cho 5 khi n không chia hết cho 4
Bài 14: Chứng minh rằng : A (25n 3 3n 2.5n )17n N *
Lời giải
 A 32n.8 9.3 n.5n 15n.8 9.15n 17.5n  0(mod17)
Bài 15: Chứng minh rằng : A nn n2 n 1B (n 1)2 n N,n 1
Lời giải
 A nn n2 n 1 n2 (nn 2 1) (n 1)
+) Với n = 2 luôn đúng
+) Xét với n > 2
 A n2 (n 1)(nn 3 nn 4 ... n 1) (n 1)
 A (n 1) n2 (nn 3 nn 4 .... n 1) 1 
   
 C
 n 1(mod n 1) nk 1k (mod n 1)k N
Ta có nhận xét sau : n2.(nn 3 nn 4 ... n 1) 1.(1 .... 1)(mod n 1)  n 2(mod n 1)
 
 C 1
 C  n 1(mod n 1) C(n 1) A(n 1)2 n 2
 11969 69220 220119
Bài 16: Chứng minh rằng : A 220 119 69102 
 le
Lời giải
 7 Ta có : A2
 69 220
+) 220 1(mod3);119  1(mod3);69  0(mod3) A 1119 ( 1)69  0(mod3); A3
 69 119
+) 220  1(mod17);119  0(mod17);69 1(mod17) A  ( 1)119 1220  0(mod17) A17
Vậy A2.3.17 102(dpcm)
 100
Bài 17: Giả sử a1,a2 ,....a100 là các số tự nhiên thỏa mãn : a1 a2 a3 ... a100 5 
 5 5 5
Tìm số dư khi chia A a1 a2 ... a100 cho 30
Lời giải
 5 5 5 5 100
Ta có : a  a(mod30)a Z A a1 a2 ... a100 a1 a2 ... a100  5 (mod30)
Có : 5  1(mod6) 5100 1(mod6) 5100  25(mod6)
Mặt khác : 5100  25(mod5);(5,6) 1 5100  25(mod30)
Vậy số dư là 25
Dạng 2: Tìm chữ số tận cùng của một sô
Bài 1: Tìm chữ số tận cùng của
 14 7
 2010 14 5 6
a. 167 b. 14 c. (4 ) 
Lời giải
a. Ta có : 167  7(mod10) 1672010  72010 (mod10)
Lại có : 72010  491005  ( 1)1005  1(mod10)
Vậy 72010 có tận cùng là 9
 14 2 2
b. 1414  414.14 (mod10);414  (16)14.7 (mod10) 414  698 (mod10) 414.14  6(mod10)
Vậy tận cùng là 6
 5.6.7 3.5.7 5.3.7 5.6.7 5.6.7
c. 4 16 6 (mod10) 4  6(mod10) 4 có tận cùng là 6
 8