Chuyên đề bồi dưỡng học sinh giỏi Toán Lớp 7 - Chuyên đề 7: Đồng dư thức và bài toán chia hết

 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
 ĐS7. CHUYÊN ĐỀ 7 – ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
PHẦN I. TÓM TẮT LÍ THUYẾT.
I. Định nghĩa.
 Nếu a b.q thì ab (a N;,b N;* )
 Nếu hai số nguyên a và b có cùng số dư trong phép chia cho một số tự nhiên m 0 thì ta nói a đồng 
dư với b theo môđun m, và có đồng dư thức: a  b mod m 
 Ví dụ: 7  10 mod 3 , 12  22 mod10 
 + Chú ý: a  b mod m a –b  0 mod m 
II. Một số tính chất.
 A. Tính chất về đồng dư
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 thì a  c mod m 4. Cộng , trừ từng vế: 
 a  b (mod m)
 a c  b d (mod m)
 c  d (mod m)
Hệ quả:
a) a  b mod m a c  b c mod m 
b) a b  c mod m a  c b mod m 
c) a  b mod m a km  b mod m 
 a  b (mod m)
5. Nhân từng vế : ac  bd (mod m)
 c  d (mod m)
Hệ quả:
a ) a  b mod m ac bc mod m (c ¢ )
b) a  b mod m an  bn mod m 
6. Có thể nhân (chia) hai vế và môđun của một đồng dư thức với một số nguyên dương
 a  b mod m ac  bc mod mc 
Chẳng hạn: 11  3 mod 4 22  6 mod 8 
 ac  bc (mod m)
7. a  b (mod m)
 (c, m) = 1 
 Trang 1 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
 16  2 (mod 7)
Chẳng hạn : 8  1 (mod 7)
 (2, 7) = 1 
 8. Định lí Fermat: Cho p là số nguyên tố (a, p) 1 khi đó a p 1  1(mod p)
 B. Tính chất về chia hết
 1. Nếu a chia hết cho cả m và n, trong đó m,n là hai số nguyên tố cùng nhau thì a chia hết cho m.n.
 2. Nếu tích a.b chia hết cho c, trong đó (b,c) 1 thì a chia hết cho c.
 3. Với p là số nguyên tố. Nếu a.b chia hết cho p thì hoặc a chia hết cho p hoặcb chia hết cho p.
 4. Khi chia n 1số nguyên dương liên tiếp cho n n 1 luôn nhận được hai số dư bằng nhau.
 5. Trong n n 1 số nguyên liên tiếp, luôn có duy nhất 1 số chia hết cho n.
 6. Nếu a;b d thì tồn tại hai số nguyên x; y sao cho: ax by d.
 7. Với mọi a;b Z ;a b và n là số tự nhiên: an bn a b.
 8. Trong n số nguyên liên tiếp ( n 1) có một và chỉ một số chia hết cho n.
 9. Lấy n 1 số nguyên bất kì ( n 1) đem chia cho n thì phải có hai số khi chia cho n có cùng số 
 dư; (Theo nguyên lí Đirichlet).
 10. Tìm m chữ số tận cùng của số A là tìm số dư khi chia A cho 10m .
PHẦN II.CÁC DẠNG BÀI.
Dạng 1: Dùng đồng dư chứng minh các bài toán chia hết
I. Phương pháp giải.
Khi số dư trong phép chia acho mlà 0 thì am . Để chứng minh am thì a  0 (mod m)
II. Bài toán.
Bài 1. Chứng minh: A (7.52n 12.6n )19,n N 
Lời giải
 2n
Ta có: 7.5 7.(52)n 7.25n A 7.25n 12.6n
Vì 25  6 (mod 19) 25n  6n (mod 19) 7.25n  7.6n (mod 19)
 7.52n 12.6n  7.6n 12.6n (mod 19) 
 7.52n 12.6n  19.6n  0 (mod 19) A19
 2 n
Bài 2. Chứng minh: A (22 5)7n (n N;n 1) 
Lời giải
Ta có 23  1 (mod 7) Ta đi tìm số dư của 2n khi chia cho 3.
Ta có: 22  1 (mod 3) 22n  1 (mod 3) 22n 3k 1 (k N)
 2 n
 A (22 5) 23k 1 5 2.23k 5 2.8k 5
Vì 23  1 (mod 7) (23 )k  1 (mod 7) hay 8k  1 (mod 7)
 2.8k  2.1 (mod 7) 2.8k 5  2.1 5  0 (mod 7) 2.8k 57
 Trang 2 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
Vậy A7
 2004n
Bài 3. Chứng minh rằng: (19242003 1920)124,n n N * 
Lời giải
 2004n
Đặt A 19242003 1920
Ta có 124 4.31và (4,31) 1
Vì 1924  2(mod 31) 1924 4  2 4(mod 31) 1920  2(mod 31)
 2004n 2004n 2004n
 19242003 1920  19242003 ( 2) mod 31 A  19242003 2 mod 31 
 n
Mặt khác 25  1 (mod 31) nên ta đi tìm số dư của 20032004 khi chia cho 5
 n
Ta có 2004n 4k,(k N ) nên 20032004 20034k
Vì 2003  3 mod 5 và 34  1 mod 5 34k  1 mod 5 34k  1 mod 5 
 n n
 20034k  34k  1 mod 5 hay 20032004  1 mod 5 20032004 5m 1
 2004n
 22003 25m 1 2.25m 2(25 )m (1)
do 25  1 (mod 31) (25 )m  1 (mod 31) 2.(25 )m  2.1 (2)
 n
Từ (1) và (2) 20032004  2 (mod 31) (3)
 n n
 20032004 20032004
Vì 1924  2 (mod 31) 1924  2 (mod 31) (4)
 2004n 2004n
Từ (3) và (4) 19242003  2 (mod 31) 19242003 2  0 (mod 31)
 2004n
Vậy A  19242003 2  0 (mod 31) A31 
 2004n
Ta lại có 19244 19242003 4; 19204 A4
Vì A31, A4 và (4,31) 1 A4.31 hay A124
Bài 4: Chứng minh rằng 22008 8 chia hết cho 31
Lời giải
Để chứng minh 22008 8 chia hết cho 31 ta chứng minh 22008 8  0 (mod 31)
 Ta có : 22008 23.22005 23.(25 )401 mà 25 32  1 (mod 31)
 nên ta có (25 )401  1401 (mod 31) 23.22005  23.1 (mod 31)
 22008  8 (mod 31)
 22008 8  8 8 (mod 31)
 Mặt khác 8  8 (mod 31)
 Nên 22008 8  0 (mod 31)
Vậy 22008 8 chia hết cho 31 (đpcm)
Bài 5: Chứng minh rằng với mọi số tự nhiên n thì số 122n 1 11n 2 chia hết cho 133
 Trang 3 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
Lời giải
Ta có: 122n 1 12.122n 12.144n
Vì 144  11 (mod 133) nên 144n  11n (mod 133)
suy ra 12.144n  12.11n (mod 133) (1)
Mặt khác: 11n 2  121.11n
Mà 121  12 (mod 133) nên 121.11n  12.11n (mod 133) (2)
Cộng vế (1) và (2) ta được 122n 1 11n 2  0 (mod 133)
Vậy 122n 1 11n 2 chia hết cho 133 (đpcm)
 2008
Bài 6: Chứng minh 58 2324 
Lời giải
 2008
Ta có 58 254 mà 25  1 (mod 24) nên 254  1 (mod 24) 254  1 (mod 24)
Có 23  23 (mod 24)
 2008
Suy ra 58 23  0 (mod 24) . 
 2008
Vậy 58 2324
Bài 7: Chứng tỏ rằng: 175 244 1321 chia hết cho 10
Lời giải
Ta có: 175  7 (mod 10)
 244  6 (mod 10)
 1321 13.(134 )5  3 (mod 10)
 175 244 1321  7 6 3 (mod 10)
Hay 175 244 1321  0 (mod 10)
Vậy 175 244 1321 10
Bài 8 : Chứng minh rằng: 22002 4 chia hết cho 31
Lời giải
Ta có 25  1 (mod 31) , mà 2002 5.400 2 nên 22002 (25 )400 .22 
Vì 25  1 (mod 31) (25 )400  1400 (mod 31) (25 )400 .22  1.22 (mod 31)
 22002 4 mod 31 22002 4 chia hết cho 31
Bài 9: Chứng minh rằng: 22225555 55552222 chia hết cho 7
Lời giải
Cách 1: Ta có 2222 47 2222  4 (mod 7) 22225555  ( 4)5555 (mod 7)
 5555 47 5555  4 (mod 7) 55552222  42222 (mod 7)
 Trang 4 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
 22225555 55552222  ( 4)5555 42222 (mod 7)
 Mà ( 4)2222 42222 ( 4)5555 42222 42222.43333 42222
 4222243333 42222 42222 (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.
Cách 2: Ta có 2222  3(mod 7) 22225555  35555 (mod 7)
Mặt khác: +) 32  12 (mod 7) 35555 35554 1 3.(32 )2777  3.22777 (mod 7)
 +) 23  1(mod 7) 22777 23.925 2 22.(23 )925  22 (mod 7)
 22225555  3.4  5(mod 7) (1)
 +) 5555  4 (mod 7) 55552222  42222 (mod 7)
 +) 43  1(mod 7) 42222 43.740 2 42.(43 )740  42  2 (mod 7) (2)
Từ (1) và (2) 22225555 55552222  5 2  0(mod 7) đpcm
 4 n 1 4 n 1
Bài 10: CMR: 32 23 5(với n N ) chia hết cho 7
Lời giải
Theo định lý Fermat ta có: 
 310  1 (mod 11)
 210  1 (mod 11)
Ta tìm dư trong phép chia là 24n 1 và 34n 1 cho 10
 Có 24n 1 2.16n  2 (mod 10)
 24n 1 10q 2n (q N )
 Có 34n 1 3.81n  3 (mod 10)
 34n 1 10k 3n (k N )
 4 n 1 4 n 1
Ta có: 32 23 5 310q 2 210k 3
 32.310q 2.3.210k 5  1 0 1 (mod 2)
 4 n 1 4 n 1
 32 23 5  0 (mod 2)
mà (2, 11) 1
 4 n 1 4 n 1
Vậy 32 23 522 với n N 
 4 n 1
Bài 11: CMR: 22 711 với n N 
Lời giải
Ta có: 24  6 (mod 10) 24n 1  2(mod10)
 Trang 5 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
 4 n 1
Vì 24n 1 10q 2n (q N ) 22 210q 2 n (q N)
Theo định lý Fermat ta có: 210  1 (mod 11)
 210q  1 (mod11)
 4 n 1
 22 7 210q 2 7  4 7n (mod11)  0n (mod11)
 4 n 1
Vậy 22 711 với n N (đpcm)
Bài 12: CMR: Nếu clà số nguyên dương: a  b (mod m) ac  bc(mod c.m)
Lời giải
 a  b (mod m) a b m.q ac bc mc.q ac  bc(mod c.m) 
Bài 13: Chứng minh định lý Fermat nhỏ: Giả sử p là số nguyên tố bất kỳ, khi đó với mọi số tự nhiên n ta 
có n p n chia hết cho p.
Lời giải
Ta có: n p n n(n p 1 1)
Nếu nchia hết cho p định lý được chứng minh.
Nếu nkhông chia hết cho p thì (n, p) 1, nên n p 1  1(mod p)
 n p 1 1 chia hết cho p .
Dạng 2. Dùng đồng dư để tìm số dư trong phép chia
I. Phương pháp giải.
- Với hai số nguyên a và m,m 0 luôn có duy nhất cặp số nguyên q,r sao cho a mq r,0 r m. 
 a  r(mod m)
Để tìm số dư r trong phép chia a cho m ta cần tìm r sao cho 
 0 r m
- Tìm số dư của phép chia tổng an bk cho m:
 ❖ Phương pháp : Tìm số dư của A B cho m: 
 + Tìm số dư r1 của phép chia A cho m.
 + Tìm số dư r2 của phép chia B cho m.
 + Tìm số dư r của phép chia r1 r2 cho m:
 + r là số dư của phép chia tổng A B cho m.
 ❖ Giải thích :
 + Khi A chia cho m dư r1 , ta viết: A mk1 r1, k1 ¥ .
 + Khi B chia cho m dư r2 , ta viết: B mk2 r2 , k2 ¥ .
 + Khi đó: A B m k1 k2 r1 r2 .
Vậy số dư của phép chia A B cho m chính là số dư của phép chia tổng r1 r2 cho m.
- Tìm số dư của phép chia hiệu an bk , an bk cho m :
 ❖ Phương pháp: Tìm số dư của A B cho m A B : 
 + Tìm số dư r1 của phép chia A cho m.
 + Tìm số dư r2 của phép chia B cho m.
 Trang 6 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
 + Tìm số dư r của phép chia r1 r2 cho m:
 ▪ Nếu r1 r2 thì số dư cần tìm là r r1 r2 .
 ▪ Nếu r1 r2 thì số dư cần tìm là r r1 r2 m .
 ▪ Nếu r1 r2 , thì hiệu A B chia hết cho m.Tức là r 0 .
 ❖ Giải thích:
 + Khi A chia cho m dư r1 , ta viết: A mk1 r1, k1 ¥ .
 + Khi B chia cho m dư r2 , ta viết: B mk2 r2 , k2 ¥ .
 + Khi đó: A B m k1 k2 r1 r2 .
Vậy số dư của phép chia A B cho m cũng chính là số dư của phép chia hiệu r1 r2 cho m.
- Tìm số dư của phép chia tích an .bk cho m :
 ❖ Phương pháp: Tìm số dư của A.B cho m : 
 + Tìm số dư r1 của phép chia A cho m.
 + Tìm số dư r2 của phép chia B cho m.
 + Tìm số dư r của phép chia r1.r2 cho m.
 + r là số dư của phép chia tích A.B cho m.
 ❖ Giải thích :
 + Khi A chia cho m dư r1 , ta viết: A mk1 r1 , k1 ¥ .
 + Khi B chia cho m dư r2 , ta viết: B mk2 r2 , k2 ¥ .
 + Khi đó: A.B mk1 r1 . mk2 r2 mk r1.r2 , k ¥ .
Vậy số dư của phép chia A.B cho m cũng chính là số dư của phép chia tích r1.r2 cho m.
II. Bài toán.
Bài 1 : Tìm số dư của 3100 cho 13 
 Lời giải
Ta có 3100 3.399 3.(33 )33
Vì 33 27 13.2 1, nên 33  1(mod 13) do đó (33 )33  133 (mod 13)
 hay 399  1(mod13)
 3.399  3.1(mod13)
 và 3  3(mod13)
 nên 3100  3(mod13) . 
Vậy 3100 chia cho 13 có số dư là 3
Bài 2 : Tìm số dư của 20042004 chia 11 
 Lời giải
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
 Lời giải
 Trang 7 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
Ta có 200211 2004 211 2004  2(mod11)
 20042004  22004 (mod11) , mà 210  1(mod11) (vì 1024 111)
 20042004 24.22000 24.(210 )200  24  5(mod11)
 Vậy 20042004 chia 11 dư 5.
Bài 3 : Tìm số dư khi chia A 19442005 cho 7.
 Lời 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 A 19442005 chia 7 dư 5.
Bài 4 : Chứng minh rằng các số A 61000 1và B 61001 1đều là bội số của 7
 Lời 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ư trong phép chia 15325 1cho 9
 Lời giải
Ta có: 1532  2(mod 9) 15325  25 (mod 9) , mà 25  5(mod 9)
 15325  5n (mod 9) 15325 1  4n (mod 9)
Vậy 15325 1chia cho 9 dư là 4.
Bài 6 : Tìm dư trong phép chia 32003 cho 13.
 Lời giải
Ta có 33  1(mod13) mà 2003 3.667 2 32003 (33 )667 .32 
 (33 )667  1667 (33 )667 .32  1.32 (mod13) (33 )667.32  9(mod13)
 32003  9(mod13) .
Vậy 32003 chia cho 13 dư 9 .
Bài 7: Tìm dư trong phép chia 570 750 cho 12
 Lời giải
Ta có 52  1(mod12) (52 )35  1(mod12) hay 570  1(mod12) (1)
 72  1(mod12) (72 )25  1(mod12) hay 750  1(mod12) (2)
 Trang 8 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
Từ (1) và (2) 570 750 chia cho 12 dư 2.
Bài 8 : Tìm số dư của A 776776 777777 778778 khi chia cho 3 và khi chia cho 5?
 Lời giải
* Số dư của A 776776 777777 778778 khi chia cho 3
Cách 1: Ta có 776  1(mod 3) 776776  ( 1)776 (mod 3) 776776  1(mod 3)
 777  0(mod 3) 777777  0(mod 3)
 778  1(mod 3) 778778  1(mod 3)
Vậy A khi chia cho 3 dư 2.
Cách 2: Ta thấy: 776  2(mod 3) 776776  2776 (mod 3)
 vì 22  1(mod 3) 2776  1(mod 3) 776776  1(mod 3)
 777  0 (mod 3) 777777  0 (mod 3) 
 778  1(mod 3) 778778  1(mod 3)778  1 (mod 3)
Vậy A  1 0 1  2(mod 3)
Vậy A khi chia cho 3 dư 2.
* Số dư của A 776776 777777 778778 khi chia cho 5
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 (mod 5)
Mà 32  1(mod 5) (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 9: Tìm số dư của A 32005 42005 khi chia cho 11 và khi chia cho 13 .
 Lời giải
Ta có : 35  1(mod11) (35 )401  1(mod11)
 Và 45  1(mod11) (45 )401  1(mod11)
 A 32005 42005  2(mod11)
 A chia cho 11 dư 2
Ta có : 33  1(mod13) (33 )668 .3  1.3(mod13) 32005  3(mod13)
 Trang 9 CHUYÊN ĐỀ 7. ĐỒNG DƯ THỨC VÀ BÀI TOÁN CHIA HẾT 
 Và 43  1(mod13) (43 )668  1.4(mod13) 42005  4(mod13)
 A 32005 42005  7(mod13)
 A chia cho 13 dư 7 .
Bài 10: Cho A 22004
a) Tìm số dư của A khi chia cho 100
b) Tìm số dư của A khi chia cho 1000
 Lời giải
a) Ta có: 100 4.25 22.52
Trước hết ta đi tìm số dư của A khi chia cho 25. 
Ta có A 22004 24.(210 )200
Vì 210 1024  1(mod 25) (210 )200  ( 1)200 (mod 25)
 24.(210 )200  24.( 1)200 (mod 25) hay A  16(mod 25)
Vậy A có thể viết dưới dạng: A 25k 16n (k N)
Mặt khác A 22004 22.22002 4.22002 A4 25k4
 k4 k 4mn (m N)
 A 25.4m 16 100m 16  16(mod100)
Vậy A chia cho 100 dư 16.
b) Ta có: 1000 8.125 23.53 và A 24.22000 24.(250 )4 16.(250 )4
Trước hết ta tìm số dư khi chia A cho 53 125
Từ hằng đẳng thức: (a b)5 a5 5a4b 10a3b2 10a2b3 5ab4 b5 ta thấy nếu a25 thì 
 (a b)5  b5 (mod125)
Vì 210  1(mod125) 210 25n 1,(n N )
 250 (210 )5 (25n 1)5  ( 1)5 (mod125)
 (250 )4  ( 1)4 (mod125) (250 )4  1(mod125)
Vậy A 16.(250 )4  16.1(mod125) A 125k 16n (k N )
Vì A 22004 23.22001 A8 125k8 k8 k 8mn (m N )
Vậy A có dạng: A 125.8m 16 1000m 16  16(mod1000)
Vậy A chia cho 1000 dư 16.
Bài 11: Tìm số dư khi chia 301293 1cho 13
 Lời giải
Ta có: 3012 13.231 9
 3012  9(mod 13) 30123  93 (mod 13) mà 93  1(mod 13) 
 Trang 10