Bộ 19 Chuyên đề Bồi dưỡng HSG Toán 7 - Chuyên đề 8: Đồng dư thức và bài toán chia hết

 ĐS7. CHUYÊN ĐỀ 8 – ĐỒ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 
 16  2 (mod 7)
Chẳng hạn : 8  1 (mod 7)
 (2, 7) = 1 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
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) 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)
 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) + 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
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 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)
 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 b) Nếu phép chia thứ nhất cho 8 là đúng thì phép chia thứ hai cho 12 có số dư là bao nhiêu ? Hãy 
tìm số bị chia.
 Lời giải
a) Gọi số đó là n ab
Vì n chia cho 8 dư 4, nên n 8p 4
Và n chia cho 12 dư 3, nên n 12q 3
 8p 4 12q 3 (Mà 8p 4 là số chẵn, còn 12q 3là số lẻ). Do vậy bạn Thắng đã làm sai một phép 
chia.
b) Vì a b 14 ab  2(mod 3) 4ab  8(mod12) (1)
Nếu ab  0(mod 4) 3ab  0(mod12) (2)
Từ (1) và (2) ab  8n (mod12) 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
Vậy số cần tìm là 86 hoặc 68. Số bị chia là 68.
Bài 13. Tìm số dư khi chia 9294 cho 15
 Lời giải
Ta thấy 92  2 mod15   9294   294 mod15 (1)
 23
Lại có 24   1 mod15   24 . 22   4 mod15 hay 294   4 mod15 (2)
Từ (1) và (2) suy ra 9294   4 mod15 tức là 9294 chia 15 thì dư 4 .
Bài 14. Tìm số dư của phép chia 123430 cho 2014 .
 Lời giải
 Ta có: 12343  778 mod 2014 (1)
 12349  7783 mod 2014  1500 mod 2014 
 123427  15003 mod 2014  1234 mod 2014 (2)
 Từ (1) và (2) suy ra: 12343.123427  778.1234 mod 2014 
 Hay 123430  1234.778 mod 2014  1388 mod 2014 
 Vì 0 1388 2014 nên r 1388 là số dư của phép chia 123430 cho 2014 . 
Bài 15. Tìm số dư của phép chia 2014200 cho 2016 .
 Lời giải
 Ta có: 20143  2008 mod 2016