Chuyên đề bồi dưỡng học sinh giỏi Toán Lớp 8 - Chuyên đề 16: Đồng dư thức

Nội dung text: Chuyên đề bồi dưỡng học sinh giỏi Toán Lớp 8 - Chuyên đề 16: Đồng dư thức

1. CHUYÊN ĐỀ: ĐỒNG DƯ THỨC I.Lí Thuyết 1.Đị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) 2. Các tính chất cơ bản : 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') Chúc các em chăm ngoan – học giỏi !! Trang 1
2. 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) II. Các dạng bài tập Dạng 1 : Tìm số dư của phép chia Bài 1 : Tìm số dư trong phép chia 20042004 cho 11 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 HD: Ta có 2002  11 => 2004 - 2  11 => 2004 ≡ 2 (mod 11) => 20042004 ≡ 22004 (mod 11) , mà 210 ≡ 1 (mod 11) (vì 1024 - 1  11) => 20042004 = 24.22000 = 24.(210)200 ≡ 24 ≡ 5 (mod 11) Vậy 20042004 chia 11 dư 5. Bài 2 : Tìm số dư khi chia A = 19442005 cho 7 HD: 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 19442005 cho 7 dư 5. Bài 3: Tìm số dư khi chia 3100 cho 7 HD: 16 Ta có: 3100 34.396 34. 36 4 4 Ta thấy: 3 81 7.11 4 3  4 mod 7 (1) Chúc các em chăm ngoan – học giỏi !! Trang 2
3. 36 729 7.104 1 36 1 mod 7 16 16 (2) 36 16 mod 7 36 1 mod 7 4 6 16 100 Từ (1) và (2) 3 . 3  4.1 mod 7 3  4 mod 7 Vậy 3100 chia cho 7 dư 4. 32 Cách 2: 3100 34.396 34. 33 34 81  4 mod 7 (1) 33 27  6 mod 7 mà 6  1 mod 7 33  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 HD: 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 HD: 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) Chúc các em chăm ngoan – học giỏi !! Trang 3
4. 33 27 13.2 1 33 1 mod13 32 32 33 132 mod13 33 1 mod13 (2) 32 Từ (1) và (2) 34. 33  3.1 mod13 3100  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 Vậy tổng 3100 3105 chia cho 13 dư 4 Bài 6 : Tìm số dư trong phép chia 15325 - 1 cho 9 HD: Ta có 1532 ≡ 2 (mod 9) => 15325 ≡ 25 (mod 9) , mà 25 ≡ 5 (mod 9) => 15325 ≡ 5 (mod 9) => 15325 - 1 ≡ 4(mod 9) Vậy 15325 - 1 chia cho 9 dư là 4. Bài 7: Chứng minh rằng: 301293 1chia hết cho 13 HD: Ta có: 3012 = 13 . 231 + 9 Do đó: 3012  9 mod13 30123  93 mod13 Mà 93 729 1 mod13 31 Nên 30123 1 mod13 30123 1 mod13 Hay 301293 1 mod13 Vậy 301293 1 1 1 mod13 301293 1  0 mod13 Hay 301293 1chia hết cho 13 Bài 8 : Chứng minh rằng A = 7.52n + 12.6n chia hết cho 19 HD: Ta có A = A = 7.52n + 12.6n = A = 7.25n + 12.6n Vì 25 ≡ 6 (mod 19) => 25n ≡ 6n (mod 19) Chúc các em chăm ngoan – học giỏi !! Trang 4
5. =>7.25n ≡ 7.6n (mod 19) => 7.25n + 12.6n ≡ 7.6n + 12.6n ≡ 19.6n ≡ 0 (mod 19) . Điều này chứng tỏ A chia hết cho 19. Bài 9: Tìm dư trong phép chia 32003 cho 13. HD: Ta có 33 ≡ 1 (mod 13) mà 2003 = 3.667 + 2 => 32003 = (33)667. 32 33 ≡ 1 => (33)667 ≡ 1667 => (33)667. 32 ≡ 1.32 (mod 13) (33)667. 32 ≡ 9 => 32003 ≡ 9 (mod 13). Vậy 32003 chia cho 13 dư 9 . Bai 10 : Chứng minh rằng 22002 - 4 chia hết cho 31 HD: 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 11 : Chứng minh rằng : 22225555 + 55552222 chia hết cho 7 HD: 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) => 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 HD: 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) Chúc các em chăm ngoan – học giỏi !! Trang 5
6. 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? HD: 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 ? HD: 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) => A chia cho 13 dư 7 . Chúc các em chăm ngoan – học giỏi !! Trang 6
7. Bài 15 : Giả sử m là số nguyên dương. Chứng minh rằng : Nếu ac 1 ≡ ac2 (mod m) và (a, m) = 1 thì c1 ≡ c2 (mod m) HD: Ta có : ac1 ≡ ac2 (mod m) => m \ ac1 - ac2 => m \a(c1 - c2) Vì (a, m) = 1 => m \ c1 - c2 => c1 ≡ c2 (mod m) Bài 16 :Chứng minh rằng : Nếu p là một số nguyên tố và không là ước của số nguyên a thì ap - 1 ≡ 1 (mod p) HD: Xét dãy số 1; 2; 3; ; p - 1. Tất cả các số này đôi một không đồng dư với nhau theo môđun p. Do đó các số a, 2a, 3a, ; (p - 1)a cũng đôi một không đồng dư với nhau rtheo môđun p. Bởi vì ngược lại nếu có r1a ≡ r2a (mod p) mà (a, p) = 1 => r1 ≡ r2 (mod p) - với r1, r2 là hai số nào đó của dãy số 1, 2, 3, , p - 1 (vô lí) Hơn nửa mõi một số của dãy a, 2a, 3a, , (p - 1)a đồng dư với đúng một trong các số 1, 2, 3, , p - 1 theo môđun p => a.2a.3a. .(p- 1)a ≡ 1.2.3. (p - 1) (mod p) hay (p - 1)!ap - 1 ≡ (p - 1)! (mod p). Vì (p, (p - 1)!) = 1 => ap - 1 ≡ 1 (mod p) Bài 17 : CMR : Nếu c là số nguyên dương : a ≡ b (mod m) => ac ≡ bc (mod c.m) HD: a ≡ b (mod m) => a - b = m.q => ac - bc = mc.q => ac ≡ bc (mod c.m) Bài 18 : Bạn Thắng học sinh lớp 6A đã viết một số có hai chữ số mà tổng các chữ số của nó là 14. Bạn Thắng đem số đó chia cho 8 thì được số dư là 4, nhưng khi chia cho 12 thì được số dư là 3. a)Chứng minh rằng bạn Thắng đã làm sai ít nhất một phép tính chia. b)Nếu phép chia thứ nhất cho 8 là đúng thì phép chia thứ hai cho 12 có ó dư là bao nhiêu ? Hãy Tìm số bị chia. HD: 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 + 3 là số lẻ). Do vậy bạn Thắng đã làm sai một phép chia. Chúc các em chăm ngoan – học giỏi !! Trang 7
8. b)Vì a + b = 14 => ab ≡ 2 (mod 3) => 4ab ≡ 8 (mod 12) (1) Nếu ab ≡ 0 (mod 4) => 3ab ≡ 0 (mod 12) (2) 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? HD: 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 Chúc các em chăm ngoan – học giỏi !! Trang 8
9. 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. Bài 20: Tìm số dư a. 9294 cho 15 b. 19442005 cho 7 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 HD: 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 21: Chứng minh rằng Chúc các em chăm ngoan – học giỏi !! Trang 9
10. a. 22002 4 chia hết cho 31 b. 22225555 55552222 chia hết cho 7 c. 2014200 256 chia hết cho 2016 HD: 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 22: Chứng minh rằng : A 7.52n 12.6n chia hết cho 19 với mọi số tự nhiên n HD: 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 23: Chứng minh rằng : A 42n 1 3n 2 13n N HD: 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) Chúc các em chăm ngoan – học giỏi !! Trang 10
11. A 42n 1 3n 2 13n N Bài 24: Tìm số dư : A 776776 777777 778778 chia cho 3 và 5 HD: 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 25: 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 HD: 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) Có: 3 3 185 555 ( 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 Bài 26: Tìm số dư trong phép chia A (19971998 19981999 19992000 )10 chia cho 111 Chúc các em chăm ngoan – học giỏi !! Trang 11
12. HD: 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. 2 3 10 Bài 27: Sử dụng định lý Fermat nhỏ. Chứng minh rằng : A 1010 1010 1010 1010 57 HD: 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 28: Sử dụng định lý Fermat nhỏ : Chứng minh rằng : A 11331 21331 31331 1331133111 HD: 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 29: Chứng minh rằng : a5  a(mod30)a Z HD: 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 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) Chúc các em chăm ngoan – học giỏi !! Trang 12
13. Vậy a5  a(mod5) a p  a(mod p) 22 Bài 30: Chứng minh rằng : A (2222 22)3234 HD: 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 31: Chứng minh rằng : A (77 77)20 ( Có 100 chữ số 7 ) HD: 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) Bài 32: Chứng minh rằng : A 1n 2n 3n 4n 5  n/ 4(n N * ) HD: +) 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) Chúc các em chăm ngoan – học giỏi !! Trang 13
14. Vậy A luôn chia hết cho 5 khi n không chia hết cho 4 Bài 33: Chứng minh rằng : A (25n 3 3n 2.5n )17n N * HD: A 32n.8 9.3 n.5n 15n.8 9.15n 17.5n  0(mod17) Bài 34: Chứng minh rằng : A nn n2 n 1B (n 1)2 n N,n 1 HD: 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 35: Chứng minh rằng : A 220 119 69102 le HD: 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 36: 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 HD: 5 5 5 5 100 Ta có : a  a(mod30)a Z A a1 a2 a100 a1 a2 a100  5 (mod30) Chúc các em chăm ngoan – học giỏi !! Trang 14
15. 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ố 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 a n 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) Nếu a ≡ 3 (mod 10) hoặc a ≡ 7 (mod 10) thì an ≡ a4k + r ≡ ar (mod 10) Bài 1 : Tìm chữ số tận cùng của các số : a) 62009 , b) 92008 , c) 32009 , d) 22009 HD: a) 62009 có chữ số tận cùng là 6 (vì 6 khi nâng lên luỹ thừa với số mũ tự nhiên khác 0 vẫn bằng chính số 6) b) 92008 = (92)1004 = 811004 = 1 có chữ số tận cùng là 1 91991 = 91990.9 = (92)995.9 = 81995.9 = ( 1).9 = 9 có chữ số tận cùng là 9 Nhận xét : Số có chữ số tận cùng là 9 khi nâng lên luỹ thừa với số mũ tự nhiên chẵn khác 0 nào thì chữ số tận cùng là 1, khi nâng lên luỹ thừa với số mũ tự nhiên lẻ thì có số tận cùng là 9. c) 32009 = (34)502.3 = 81502.3 = ( 1).3 = 3 có chữ số tận cùng là 3. d) 22009 = 22008.2 = (24)502.2 = 16502.2 = ( 6).2 = 2 có chữ số tận cùng là 2 Bài 2 : Tìm chữ số tận cùng của các số sau : a) 421 , b) 3103 , c) 84n + 1 (n N) d) 1423 + 2323 + 7023 Chúc các em chăm ngoan – học giỏi !! Trang 15
16. HD: a) 430 = 42.15 = (42)15 = 1615 = 6 có chữ số tận cùng là 6 421 = 420 + 1 = (42)10.4 = 1610.4 = ( 6).4 = 4 có chữ số tận cùng là 4 Nhận xét : Số nào có số tận cùng là 4 thì khi nâng lên luỹ thừa với số mũ tự nhiên chẵn thì có số tận cùng là 6, khi nâng lên với số mũ tự nhiên lẻ có số tận cùng là 4) b) 3103 = 3102.3 = (32)51.3 = 951.3 = ( 9).3 = 7 có chữ số tận cùng là 7 c) 84n + 1 = 84n.8 = (23)4n.8 = 212n.8 = (24)3n.8 = 163n.8 = ( 6).8 = 8 có chữ số tận cùng là 8 d) 1423 = 1422.14 = ( 6).14 = . 4 2323 = 2322.23 = (232)11.23 = ( 9).23 = 7 7023 = 0 Vậy : 1423 + 2323 + 7023 = 4 + 7 + 0 = 1 có chữ số tận cùng là 1 Tìm hai số tận cùng của số an : Ta có nhận xét sau : 220 ≡ 76 (mod 100) 320 ≡ 01 (mod 100) 65 ≡ 76 (mod 100) 74 ≡ 01 (mod 100) Mà 76n ≡ 76 (mod 100) với n ≥ 1 5n ≡ 25 (mod 100) với n ≥ 2 Suy ra kết quả sau với k là số tự nhiên khác 0. a20k ≡ 00 (mod 100) nếu a ≡ 0 (mod 10) a20k ≡ 01 (mod 100) nếu a ≡ 1; 3; 7; 9 (mod 10) a20k ≡ 25 (mod 100) nếu a ≡ 5 (mod 10) 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 HD: Ta có : 220 ≡ 76 (mod 100) => 220k ≡ 76 (mod 100) Chúc các em chăm ngoan – học giỏi !! Trang 16
17. 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 HD: a) Ta thấy 2999 21000 : 2 (1) 1000 10 100 Mà 2 = 2 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 2 1000 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 31000  01 mod100 , nghĩa là hai chữ số tận cùng của 3 1000 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) Bài 3: Tìm chữ số tận cùng của 14 7 2010 14 5 6 a. 167 b. 14 c. (4 ) HD: a. Ta có : 167  7(mod10) 1672010  72010 (mod10) Lại có : 72010  491005  ( 1)1005  1(mod10) Chúc các em chăm ngoan – học giỏi !! Trang 17
18. 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 Chúc các em chăm ngoan – học giỏi !! Trang 18