Bồi dưỡng học sinh giỏi môn Toán theo các chuyên đề

các phương pháp giải bài toán chia hết Phần I: Tóm tắt lý thuyết I. Định nghĩa phép chia Cho 2 số nguyên a và b trong đó b ạ 0 ta luôn tìm được hai số nguyên q và r duy nhất sao cho: a = bq + r Với 0 Ê r Ê |b| Trong đó: a là số bị chia, b là số chia, q là thương, r là số dư. Khi a chia cho b có thể xẩy ra | b| số dư r ẻ {0; 1; 2; ; | b|} Đặc biệt: r = 0 thì a = bq, khi đó ta nói a chia hết cho b hay b chia hết a. Ký hiệu: aMb hay b\ a Vậy: a M b Û Có số nguyên q sao cho a = bq II. Các tính chất Với " a ạ 0 ị a M a Nếu a M b và b M c ị a M c Với " a ạ 0 ị 0 M a Nếu a, b > 0 và a M b ; b M a ị a = b Nếu a M b và c bất kỳ ị ac M b Nếu a M b ị (±a) M (±b) Với " a ị a M (±1) Nếu a M b và c M b ị a ± c M b Nếu a M b và cMb ị a ± c M b Nếu a + b M c và a M c ị b M c Nếu a M b và n > 0 ị an M bn Nếu ac M b và (a, b) =1 ị c M b Nếu a M b, c M b và m, n bất kỳ am + cn M b Nếu a M b và c M d ị ac M bd Tích n số nguyên liên tiếp chia hết cho n! III. Một số dấu hiệu chia hết Gọi N = 1. Dấu hiệu chia hết cho 2: Một số chia hết cho 2chữ số tận cùng của nó là chữ số chẵn. N M 2 Û a0 M 2 Û a0ẻ{0; 2; 4; 6; 8} 2. Dấu hiệu chia hết cho 5: Một số chia hết cho 5 chữ số tận cùng của nó là 0 hoặc 5. N M 5 Û a0 M 5 Û a0ẻ{0; 5} 3. Dấu hiệu chia hết cho 4 và 25: Một số chia hết cho 4 (hoặc 25)số tạo bởi 2 chữ số tận cùng của nó chia hết cho 4 hoặc 25. N M 4 (hoặc 25) Û M 4 (hoặc 25) 4. Dấu hiệu chia hết cho 8 và 125: Một số chia hết cho 8 (hoặc 125) số tạo bởi 3 chữ số tận cùng của nó chia hết cho 8 hoặc 125. N M 8 (hoặc 125) Û M 8 (hoặc 125) 5. Dấu hiệu chia hết cho 3 và 9: Một số chia hết cho 3 (hoặc 9) tổng các chữ số của nó chia hết cho 3 (hoặc 9). N M 3 (hoặc 9) Û a0+a1++an M 3 (hoặc 9) * Chú ý: một số chia hết cho 3 (hoặc 9) dư bao nhiêu thì tổng các chữ số của nó chia cho 3 (hoặc 9) cũng dư bấy nhiêu. 6. Dấu hiệu chia hết cho 11: Một số chia hết cho 11 hiệu giữa tổng các chữ số ở hàng lẻ và tổng các chữ số ở hàng chẵn tính từ trái sang phải chia hết cho N M 11 Û [(a0+a1+) - (a1+a3+)] M 11 7. Một số dấu hiệu khác: N M 101 Û [(++) - (++)]M101 N M 7 (hoặc 13) Û [( + +) - [( + +) M11 (hoặc 13) N M 37 Û ( + +) M 37 N M 19 Û ( a0+2an-1+22an-2++ 2na0) M 19 IV. Đồng dư thức a. Định nghĩa: Cho m là số nguyên dương. Nếu hai số nguyên a và b cho cùng số dư khi chia cho m thì ta nói a đồng dư với b theo modun m. Ký hiệu: a º b (modun) Vậy: a º b (modun) Û a - b M m b. Các tính chất Với " a ị a º a (modun) Nếu a º b (modun) ị b º a (modun) Nếu a º b (modun), b º c (modun) ị a º c (modun) Nếu a º b (modun) và c º d (modun) ị a+c º b+d (modun) Nếu a º b (modun) và c º d (modun) ị ac º bd (modun) Nếu a º b (modun), d ẻ Uc (a, b) và (d, m) =1 ị (modun) Nếu a º b (modun), d > 0 và d ẻ Uc (a, b, m) ị (modun ) V. Một số định lý 1. Định lý Euler Nếu m là 1 số nguyên dương j(m) là số các số nguyên dương nhỏ hơn m và nguyên tố cùng nhau với m, (a, m) = 1 Thì aj(m) º 1 (modun) Công thức tính j(m) Phân tích m ra thừa số nguyên tố m = p1a1 p2a2 pkak với pi ẻ p; ai ẻ N* Thì j(m) = m(1 - )(1 - ) (1 - ) 2. Định lý Fermat Nếu t là số nguyên tố và a không chia hết cho p thì ap-1 º 1 (modp) 3. Định lý Wilson Nếu p là số nguyên tố thì ( P - 1)! + 1 º 0 (modp) phần II: các phương pháp giải bài toán chia hết 1. Phương pháp 1: Sử dụng dấu hiệu chia hết Ví dụ 1: Tìm các chữ số a, b sao cho M 45 Giải: Ta thấy 45 = 5.9 mà (5 ; 9) = 1 để M 45 Û M 5 và 9 Xét M 5 Û b ẻ {0 ; 5} Nếu b = 0 ta có số M 9 Û a + 5 + 6 + 0 M 9 ị a + 11 M 9 ị a = 7 Nếu b = 5 ta có số M 9 Û a + 5 + 6 + 0 M 9 ị a + 16 M 9 ị a = 2 Vậy: a = 7 và b = 0 ta có số 7560 a = 2 và b = 5 ta có số 2560 Ví dụ 2: Biết tổng các chữ số của 1 số là không đổi khi nhân số đó với 5. CMR số đó chia hết cho 9. Giải: Gọi số đã cho là a Ta có: a và 5a khi chia cho 9 cùng có 1 số dư ị 5a - a M 9 ị 4a M 9 mà (4 ; 9) = 1 ị a M 9 (Đpcm) Ví dụ 3: CMR số M 81 Giải: Ta thấy: 111111111 M 9 Có = 111111111(1072 + 1063 + + 109 + 1) Mà tổng 1072 + 1063 + + 109 + 1 có tổng các chữ số bằng 9 M 9 ị 1072 + 1063 + + 109 + 1 M 9 Vậy: M 81 (Đpcm) Bài tập tương tự Bài 1: Tìm các chữ số x, y sao cho a. M 4 và 9 b. M 17 Bài 2: Cho số N = CMR a. N M 4 Û (a + 2b) M 4 b. N M 16 Û (a + 2b + 4c + 8d) M 16 với b chẵn c. N M 29 Û (d + 2c + 9b + 27a) M 29 Bài 3: Tìm tất cả các số có 2 chữ số sao cho mỗi số gấp 2 lần tích các chữ số của số đó. Bài 4: Viết liên tiếp tất cả các số có 2 chữ số từ 19 đến 80 ta được số A = 1920217980. Hỏi số A có chia hết cho 1980 không ? Vì sao? Bài 5: Tổng của 46 số tự nhiên liên tiếp có chia hết cho 46 không? Vì sao? Bài 6: Chứng tỏ rằng số là tích của 2 số tự nhiên liên tiếp. Hướng dẫn - Đáp số Bài 1: a. x = và y = 2 x = và y = 6 b. = 17 (122 + 6x) + 2(2-x)M17 Û x = 2 Bài 2: a. NM4 Û M4 Û 10b + aM4 Û 8b + (2b + a) M4 ị a + 2bM4 b. NM16 Û 1000d + 100c + 10b + aM16 Û (992d + 96c + 8b) + (8d + 4c + 2b + a) M16 ị a + 2b + 4c + 8dM16 với b chẵn c. Có 100(d + 3c + 9b + 27a) - M29 Mà (1000, 29) =1 ị M29 ị (d + 3c + 9b + 27a) M29 Bài 3: Gọi là số có 2 chữ số Theo bài ra ta có: = 10a + b = 2ab (1) M2 ị b ẻ{0; 2; 4; 6; 8} thay vào (1) a = 3; b = 6 Bài 4: Có 1980 = 22.32.5.11 Vì 2 chữ số tận cùng của a là 80 M 4 và 5 ị AM 4 và 5 Tổng các số hàng lẻ 1+(2+3++7).10+8 = 279 Tổng các số hàng chẵn 9+(0+1++9).6+0 = 279 Có 279 + 279 = 558 M 9 ị A M 9 279 - 279 = 0 M 11 ị A M 11 Bài 5: Tổng 2 số tự nhiên liên tiếp là 1 số lẻ nên không chia hết cho 2. Có 46 số tự nhiên liên tiếp ị có 23 cặp số mỗi cặp có tổng là 1 số lẻ ị tổng 23 cặp không chia hết cho 2. Vậy tổng của 46 số tự nhiên liên tiếp không chia hết cho 46. Bài 6: Có = Mà = 3. ị = (Đpcm) 2. Phương pháp 2: Sử dụng tính chất chia hết * Chú ý: Trong n số nguyên liên tiếp có 1 và chỉ 1 số chia hết cho n. CMR: Gọi n là số nguyên liên tiếp m + 1; m + 2; m + n với m ẻ Z, n ẻ N* Lấy n số nguyên liên tiếp trên chia cho n thì ta được tập hợp số dư là: {0; 1; 2; n - 1} * Nếu tồn tại 1 số dư là 0: giả sử m + i = nqi ; i = ị m + i M n * Nếu không tồn tại số dư là 0 ị không có số nguyên nào trong dãy chia hết cho n ị phải có ít nhất 2 số dư trùng nhau. Giả sử: ị i - j = n(qi - qj) M n ị i - j M n mà ẵi - jẵ< n ị i - j = 0 ị i = j ị m + i = m + j Vậy trong n số đó có 1 số và chỉ 1 số đó chia hết cho n Ví dụ 1: CMR: a. Tích của 2 số nguyên liên tiếp chia hết cho 2. b. Tích của 3 số nguyên liên tiếp chia hết cho 6. Giải: a. Trong 2 số nguyên liên tiếp bao giờ cũng có 1 số chẵn ị Số chẵn đó chia hết cho 2. Vậy tích của 2 số nguyên liên tiếp luôn chia hết cho 2. Tích 2 số nguyên liên tiếp luôn chia hết cho 2 nên tích của 3 số nguyên liên tiếp luôn chia hết cho 2 b. Trong 3 sô nguyên liên tiếp bao giơ cũng có 1 số chia hết cho 3. ị Tích 3 số đó chia hết cho 3 mà (1; 3) = 1. Vậy tích của 3 số nguyên liên tiếp luôn chia hết cho 6. Ví dụ 2: CMR: Tổng lập phương của 3 số nguyên liên tiếp luôn chia hết cho 9. Giải: Gọi 3 số nguyên liên tiếp lần lượt là: n - 1 , n , n+1 Ta có: A = (n - 1)3 + n3 + (n + 1)3 = 3n3 - 3n + 18n + 9n2 + 9 = 3(n - 1)n (n+1) + 9(n2 + 1) + 18n Ta thấy (n - 1)n (n + 1) M 3 (CM Ví dụ 1) ị 3(n - 1)n (n + 1) M 9 mà ị A M 9 (ĐPCM) Ví dụ 3: CMR: n4 - 4n3 - 4n2 +16n M 384 với " n chẵn, n³4 Giải: Vì n chẵn, n³4 ta đặt n = 2k, k³2 Ta có n4 - 4n3 - 4n2 + 16n = 16k4 - 32k3 - 16k2 + 32k = 16k(k3 - 2k2 - k + 2) = 16k(k - 2) (k - 1)(k + 1) Với k ³ 2 nên k - 2, k - 1, k + 1, k là 4 số tự nhiên liên tiếp nên trong 4 số đó có 1 số chia hết cho 2 và 1 số chia hết cho 4. ị (k - 2)(k - 1)(k + 1)k M 8 Mà (k - 2) (k - 1)k M 3 ; (3,8)=1 ị (k - 2) (k - 1) (k + 1)k M 24 ị 16(k - 2) (k - 1) (k + 1)k M (16,24) Vậy n4 - 4n3 - 4n2 +16n M 384 với " n chẵn, n ³ 4 Bài tập tương tự Bài 1: CMR: a. n(n + 1) (2n + 1) M 6 b. n5 - 5n3 + 4n M 120 Với " n ẻ N Bài 2: CMR: n4 + 6n3 + 11n2 + 6n M 24 Với " n ẻ Z Bài 3: CMR: Với " n lẻ thì n2 + 4n + 3 M 8 n3 + 3n2 - n - 3 M 48 n12 - n8 - n4 + 1 M 512 Bài 4: Với p là số nguyên tố p > 3 CMR : p2 - 1 M 24 Bài 5: CMR: Trong 1900 số tự nhiên liên tiếp có 1 số có tổng các chữ số chia hết cho 27. Hướng dẫn - Đáp số Bài 1: a. n(n + 1)(2n + 1) = n(n + 1) [(n + 1) + (n + 2)] = n(n + 1) (n - 1) + n(n + 1) (n + 2) M 6 b. n5 - 5n3 + 4n = (n4 - 5n2 + 4)n = n(n2 - 1) (n2 - 4) = n(n + 1) (n - 1) (n + 2) (n - 2) M 120 Bài 2: n4 + 6n3 + 6n + 11n2 = n(n3 + 6n2 + 6 + 11n) = n(n + 1) (n + 2) (n + 3) M 24 Bài 3: a. n2 + 4n + 3 = (n + 1) (n + 3) M 8 b. n3 + 3n2 - n - 3 = n2(n + 3) - (n + 3) = (n2 - 1) (n + 3) = (n + 1) (n - 1) (n + 3) = (2k + 4) (2k + 2) (2k với n = 2k + 1, k ẻ N) = 8k(k + 1) (k +2) M 48 c. n12 - n8 - n4 + 1 = n8 (n4 - 1) - (n4 - 1) = (n4 - 1) (n8 - 1) = (n4 - 1)2 (n4 + 1) = (n2 - 1)2 (n2 - 1)2 (n4 + 1) = 16[k(k + 1)2 (n2 + 1)2 (n4 + 1) Với n = 2k + 1 ị n2 + 1 và n4 + 1 là những số chẵn ị (n2 + 1)2 M 2 ; n4 + 1 M 2 ị n12 - n8 - n4 + 1 M (24.22. 22. 1 . 21) Vậy n12 - n8 - n4 + 1 M 512 Bài 4: Có p2 - 1 = (p - 1) (p + 1) vì p là số nguyên tố p > 3 ị p M 3 ta có: (p - 1) (p + 1) M 8 và p = 3k + 1 hoặc p = 3k + 2 (k ẻ N) ị (p - 1) (p + 1) M 3 Vậy p2 - 1 M 24 Bài 5: Giả sử 1900 số tự nhiên liên tiếp là n, n +1; n + 2; ; n + 1989 (1) trong 1000 tự nhiên liên tiếp n, n + 1; n + 2; ; n + 999 có 1 số chia hết cho 1000 giả sử n0, khi đó n0 có tận cùng là 3 chữ số 0 giả sử tổng các chữ số của n0 là s khi đó 27 số n0, n0 + 9; n0 + 19; n0 + 29; n0 + 39; ; n0 + 99; n0 + 199; n0 + 899 (2) Có tổng các chữ số lần lượt là: s; s + 1 ; s + 26 Có 1 số chia hết cho 27 (ĐPCM) * Chú ý: n + 899 Ê n + 999 + 899 < n + 1989 ị Các số ở (2) nằm trong dãy (1) 3. Phương pháp 3: xét tập hợp số dư trong phép chia Ví dụ 1: CMR: Với " n ẻ N Thì A(n) = n(2n + 7) (7n + 7) chia hết cho 6 Giải: Ta thấy 1 trong 2 thừa số n và 7n + 1 là số chẵn. Với " n ẻ N ị A(n) M 2 Ta chứng minh A(n) M 3 Lấy n chia cho 3 ta được n = 3k + 1 (k ẻ N) Với r ẻ {0; 1; 2} Với r = 0 ị n = 3k ị n M 3 ị A(n) M 3 Với r = 1 ị n = 3k + 1 ị 2n + 7 = 6k + 9 M 3 ị A(n) M 3 Với r = 2 ị n = 3k + 2 ị 7n + 1 = 21k + 15 M 3 ị A(n) M 3 ị A(n) M 3 với " n mà (2, 3) = 1 Vậy A(n) M 6 với " n ẻ N Ví dụ 2: CMR: Nếu n M 3 thì A(n) = 32n + 3n + 1 M 13 Với " n ẻ N Giải: Vì n M 3 ị n = 3k + r (k ẻ N); r ẻ {1; 2; 3} ị A(n) = 32(3k + r) + 33k+r + 1 = 32r(36k - 1) + 3r (33k - 1) + 32r + 3r + 1 ta thấy 36k - 1 = (33)2k - 1 = (33 - 1)M = 26M M 13 33k - 1 = (33 - 1)N = 26N M 13 với r = 1 ị 32n + 3n + 1 = 32 + 3 +1 = 13 M 13 ị 32n + 3n + 1 M 13 với r = 2 ị 32n + 3n + 1 = 34 + 32 + 1 = 91 M 13 ị 32n + 3n + 1 Vậy với n M 3 thì A(n) = 32n + 3n + 1 M 13 Với " n ẻ N Ví dụ 3: Tìm tất cả các số tự nhiên n để 2n - 1 M 7 Giải: Lấy n chia cho 3 ta có n = 3k + 1 (k ẻ N); r ẻ {0; 1; 2} Với r = 0 ị n = 3k ta có 2n - 1 = 23k - 1 = 8k - 1 = (8 - 1)M = 7M M 7 với r =1 ị n = 3k + 1 ta có: 2n - 1 = 28k +1 - 1 = 2.23k - 1 = 2(23k - 1) + 1 mà 23k - 1 M 7 ị 2n - 1 chia cho 7 dư 1 với r = 2 ị n = 3k + 2 ta có : 2n - 1 = 23k + 2 - 1 = 4(23k - 1) + 3 mà 23k - 1 M 7 ị 2n - 1 chia cho 7 dư 3 Vậy 23k - 1 M 7 Û n = 3k (k ẻ N) Bài tập tương tự Bài 1: CMR: An = n(n2 + 1)(n2 + 4) M 5 Với " n ẻ Z Bài 2: Cho A = a1 + a2 + + an B = a51 + a52 + + a5n Bài 3: CMR: Nếu (n, 6) =1 thì n2 - 1 M 24 Với " n ẻ Z Bài 4: Tìm số tự nhiên n để 22n + 2n + 1 M 7 Bài 5: Cho 2 số tự nhiên m, n để thoả mãn 24m4 + 1 = n2. CMR: mn M 55 Hướng dẫn - Đáp số Bài 1: + A(n) M 6 + Lấy n chia cho 5 ị n = 5q + r r ẻ {0; 1; 2; 3; 4} r = 0 ị n M 5 ị A(n) M 5 r = 1, 4 ị n2 + 4 M 5 ị A(n) M 5 r = 2; 3 ị n2 + 1 M 5 ị A(n) M 5 ị A(n) M 5 ị A(n) M 30 Bài 2: Xét hiệu B - A = (a51 - a1) + + (a5n - an) Chỉ chứng minh: a5i - ai M 30 là đủ Bài 3: Vì (n, 6) =1 ị n = 6k + 1 (k ẻ N) Với r ẻ {±1} r = ±1ị n2 - 1 M 24 Bài 4: Xét n = 3k + r (k ẻ N) Với r ẻ {0; 1; 2} Ta có: 22n + 2n + 1 = 22r(26k - 1) + 2r(23k - 1) + 22n + 2n + 1 Làm tương tự VD3 Bài 5: Có 24m4 + 1 = n2 = 25m4 - (m4 - 1) Khi m M 5 ị mn M 5 Khi m M 5 thì (m, 5) = 1 ị m4 - 1 M 5 (Vì m5 - m M 5 ị (m4 - 1) M 5 ị m4 - 1 M 5) ị n2 M 5 ị ni5. Vậy mn M 5 4. Phương pháp 4: sử dụng phương pháp phân tích thành nhân tử Giả sử chứng minh an M k Ta có thể phân tích an chứa thừa số k hoặc phân tích thành các thừa số mà các thừa số đó chia hết cho các thừa số của k. Ví dụ 1: CMR: 36n - 26n M 35 Với " n ẻ N Giải: Ta có 36n - 26n = (36)n - (26)n = (36 - 26)M = (33 + 23) (33 - 23)M = 35.19M M 35 Vậy 36n - 26n M 35 Với " n ẻ N Ví dụ 2: CMR: Với " n là số tự nhiên chăn thì biểu thức A = 20n + 16n - 3n - 1 M 232 Giải: Ta thấy 232 = 17.19 mà (17;19) = 1 ta chứng minh A M 17 và A M 19 ta có A = (20n - 3n) + (16n - 1) có 20n - 3n = (20 - 3)M M 17M 16n - 1 = (16 + 1)M = 17N M 17 (n chẵn) ị A M 17 (1) ta có: A = (20n - 1) + (16n - 3n) có 20n - 1 = (20 - 1)p = 19p M 19 có 16n - 3n = (16 + 3)Q = 19Q M 19 (n chẵn) ị A M 19 (2) Từ (1) và (2) ị A M 232 Ví dụ 3: CMR: nn - n2 + n - 1 M (n - 1)2 Với " n >1 Giải: Với n = 2 ị nn - n2 + n - 1 = 1 và (n - 1)2 = (2 - 1)2 = 1 ị nn - n2 + n - 1M (n - 1)2 với n > 2 đặt A = nn - n2 + n - 1 ta có A = (nn - n2) + (n - 1) = n2(nn-2 - 1) + (n - 1) = n2(n - 1) (nn-3 + nn-4 + + 1) + (n - 1) = (n - 1) (nn-1 + nn-2 + + n2 +1) = (n - 1) [(nn-1 - 1) + +( n2 - 1) + (n - 1)] = (n - 1)2M M (n - 1)2 Vậy A M (n - 1)2 (ĐPCM) Bài tập tương tự Bài 1: CMR: a. 32n +1 + 22n +2 M 7 b. mn(m4 - n4) M 30 Bài 2: CMR: A(n) = 3n + 63 M 72 với n chẵn n ẻ N, n ³ 2 Bài 3: Cho a và b là 2 số chính phương lẻ liên tiếp. CMR: a. (a - 1) (b - 1) M 192 Bài 4: CMR: Với p là 1 số nguyên tố p > 5 thì p4 - 1 M 240 Bài 5: Cho 3 số nguyên dương a, b, c và thoả mãn a2 = b2 + c2. CMR: abc M 60 Hướng dẫn - Đáp số Bài 1: a. 32n +1 + 22n +2 = 3.32n + 2.2n = 3.9n + 4.2n = 3(7 + 2)n + 4.2n = 7M + 7.2n M 7 b. mn(m4 - n4) = mn(m2 - 1)(m2 + 1) - mn(n2 - 1) (n2 + 1) M 30 Bài 3: Có 72 = 9.8 mà (8, 9) = 1 và n = 2k (k ẻ N) có 3n + 63 = 32k + 63 = (32k - 1) + 64 ị A(n) M 8 Bài 4: Đặt a = (2k - 1)2; b = (2k - 1)2 (k ẻ N) Ta có (a - 1)(b - 1) = 16k(k + 1)(k - 1) M 64 và 3 Bài 5: Có 60 = 3.4.5 Đặt M = abc Nếu a, b, c đều không chia hết cho 3 ị a2, b2 và c2 chia hết cho 3 đều dư 1 ị a2 ạ b2 + c2. Do đó có ít nhất 1 số chia hết cho 3. Vậy M M 3 Nếu a, b, c đều không chia hết cho 5 ị a2, b2 và c2 chia 5 dư 1 hoặc 4 ị b2 + c2 chia 5 thì dư 2; 0 hoặc 3. ị a2 ạ b2 + c2. Do đó có ít nhất 1 số chia hết cho 5. Vậy M M 5 Nếu a, b, c là các số lẻ ị b2 và c2 chia hết cho 4 dư 1. ị b2 + c2 º (mod 4) ị a2 ạ b2 + c2 Do đó 1 trong 2 số a, b phải là số chẵn. Giả sử b là số chẵn Nếu C là số chẵn ị M M 4 Nếu C là số lẻ mà a2 = b2 + c2 ị a là số lẻ ị b2 = (a - c) (a + b) ị ị chẵn ị b M 4 ị m M 4 Vậy M = abc M 3.4.5 = 60 5. Phương pháp 5: biến đổi biểu thức cần chứng minh về dạng tổng Giả sử chứng minh A(n) M k ta biến đổi A(n) về dạng tổng của nhiều hạng tử và chứng minh mọi hạng tử đều chia hết cho k. Ví dụ 1: CMR: n3 + 11n M 6 với " n ẻ z. Giải: Ta có n3 + 11n = n3 - n + 12n = n(n2 - 1) + 12n = n(n + 1) (n - 1) + 12n Vì n, n - 1; n + 1 là 3 số nguyên liên tiếp ị n (n + 1) (n - 1) M 6 và 12n M 6 Vậy n3 + 11n M 6 Ví dụ 2: Cho a, b ẻ z thoả mãn (16a +17b) (17a +16b) M 11 CMR: (16a +17b) (17a +16b) M 121 Giải: Có 11 số nguyên tố mà (16a +17b) (17a +16b) M 11 ị (1) Có 16a +17b + 17a +16b = 33(a + b) M 11 (2) Từ (1) và (2) ị Vậy (16a +17b) (17a +16b) M 121 Ví dụ 3: Tìm n ẻ N sao cho P = (n + 5)(n + 6) M 6n. Giải : Ta có P = (n + 5)(n + 6) = n2 + 11n + 30 = 12n + n2 - n + 30 Vì 12n M 6n nên để P M 6n Û n2 - n + 30 M 6n Û Từ (1) ị n = 3k hoặc n = 3k + 1 (k ẻ N) Từ (2) ị n ẻ {1; 2; 3; 5; 6; 10; 15; 30} Vậy từ (1); (2) ị n ẻ {1; 3; 6; 10; 15; 30} Thay các giá trị của n vào P ta có n ẻ {1; 3; 10; 30} là thoả mãn Vậy n ẻ {1; 3; 10; 15; 30} thì P = (n + 5)(n + 6) M 6n. Bài tập tương tự Bài 1: CMR: 13 + 33 + 53 + 73 M 23 Bài 2: CMR: 36n2 + 60n + 24 M 24 Bài 3: CMR: a. 5n+2 + 26.5n + 8 2n+1 M 59 b. 9 2n + 14 M 5 Bài 4: Tìm n ẻ N sao cho n3 - 8n2 + 2n M n2 + 1 Hướng dẫn - Đáp số Bài 1: 13 + 33 + 53 + 73 = (13 + 73) + (33 + 53) = 8m + 8N M 23 Bài 2: 362 + 60n + 24 = 12n(3n + 5) + 24 Ta thấy n và 3n + 5 không đồng thời cùng chẵn hoặc cùng lẻ ị n(3n + 5) M 2 ị ĐPCM Bài 3: a. 5n+2 + 26.5n + 8 2n+1 = 5n(25 + 26) + 8 2n+1 = 5n(59 - 8) + 8.64 n = 5n.59 + 8.59m M 59 b. 9 2n + 14 = 9 2n - 1 + 15 = (81n - 1) + 15 = 80m + 15 M 5 Bài 4: Có n3 - 8n2 + 2n = (n2 + 1)(n - 8) + n + 8 M (n2 + 1) Û n + 8 M n2 + 1 Nếu n + 8 = 0 ị n = -8 (thoả mãn) Nếu n + 8 ạ 0 ị ẵn + 8ẵ³ n2 + 1 ị ị n ẻ {-2; 0; 2} thử lại. Vậy n ẻ {-8; 0; 2} 6. Phương pháp 6: Dùng quy nạp toán học Giả sử CM A(n) M P với n ³ a (1) Bước 1: Ta CM (1) đúng với n = a tức là CM A(n) M P Bước 2: Giả sử (1) đúng với n = k tức là CM A(k) M P với k ³ a Ta CM (1) đúng với n = k + 1 tức là phải CM A(k+1) M P Bước 3: Kết luận A(n) M P với n ³ a Ví dụ 1: Chứng minh A(n) = 16n - 15n - 1 M 225 với " n ẻ N* Giải: Với n = 1 ị A(n) = 225 M 225 vậy n = 1 đúng Giả sử n = k ³ 1 nghĩa là A(k) = 16k - 15k - 1 M 225 Ta phải CM A(k+1) = 16 k+1 - 15(k + 1) - 1 M 225 Thật vậy: A(k+1) = 16 k+1 - 15(k + 1) - 1 = 16.16k - 15k - 16 = (16k - 15k - 1) + 15.16k - 15 = 16k - 15k - 1 + 15.15m = A(k) + 225 mà A(k) M 225 (giả thiết quy nạp) 225mM 225 Vậy A(n) M 225 Ví dụ 2: CMR: với " n ẻ N* và n là số tự nhiên lẻ ta có Giải: Với n = 1 ị m2 - 1 = (m + 1)(m - 1) M 8 (vì m + 1; m - 1 là 2 số chẵn liên tiếp nên tích của chúng chia hết cho 8) Giả sử với n = k ta có ta phải chứng minh Thật vậy ị ị có = Vậy với " n ³ 1 Bài tập tương tự Bài 1: CMR: 33n+3 - 26n - 27 M 29 với " n ³ 1 Bài 2: CMR: 42n+2 - 1 M 15 Bài 3: CMR số được thành lập bởi 3n chữ số giống nhau thì chia hết cho 3n với n là số nguyên dương. Hướng dẫn - Đáp số Bài 1: Tương tự ví dụ 1. Bài 2: Tương tự ví dụ 1. Bài 3: Ta cần CM M 3n (1) Với n = 1 ta có Giả sử (1) đúng với n = k tức là M 3k Ta chứng minh (1) đúng với n = k + 1 tức là phải chứng minh M 3k+1 ta có 3k+1 = 3.3k = 3k + 3k +3k Có 7. Phương pháp 7: sử dụng đồng dư thức Giải bài toán dựa vào đồng dư thức chủ yếu là sử dụng định lý Euler và định lý Fermat Ví dụ 1: CMR: 22225555 + 55552222 M 7 Giải: Có 2222 º - 4 (mod 7) ị 22225555 + 55552222 º (- 4)5555 + 45555 (mod 7) Lại có: (- 4)5555 + 42222 = - 45555 + 42222 = - 42222 (43333 - 1) = Vì 43 = 64 º (mod 7) (mod 7) ị 22225555 + 55552222 º 0 (mod 7) Vậy 22225555 + 55552222 M 7 Ví dụ 2: CMR: với " n ẻ N 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 + 2 (q ẻ N) Có 34n+1 = 3.81n º 3 (mod 10) ị 34n+1 = 10k + 3 (k ẻ N) Ta có: = 32.310q + 23.210k + 5 º 1+0+1 (mod 2) º 0 (mod 2) mà (2, 11) = 1 Vậy với " n ẻ N Ví dụ 3: CMR: với n ẻ N Giải : Ta có: 24 º 6 (mod) ị 24n+1 º 2 (mod 10) ị 24n+1 = 10q + 2 (q ẻ N) ị Theo định lý Fermat ta có: 210 º 1 (mod 11) ị 210q º 1 (mod 11) º 4+7 (mod 11) º 0 (mod 11) Vậy với n ẻ N (ĐPCM) Bài tập tương tự Bài 1: CMR với n ẻ N Bài 2: CMR với " n ³ 1 ta có 52n-1. 22n-15n+1 + 3n+1 .22n-1 M 38 Bài 3: Cho số p > 3, p ẻ (P). CMR 3p - 2p - 1 M 42p Bài 4: CMR với mọi số nguyên tố p đều có dạng 2n - n (n ẻ N) chia hết cho p. Hướng dẫn - Đáp số Bài 1: Làm tương tự như VD3 Bài 2: Ta thấy 52n-1. 22n-15n+1 + 3n+1 .22n-1 M 2 Mặt khác 52n-1. 22n-15n+1 + 3n+1 .22n-1 = 2n(52n-1.10 + 9. 6n-1) Vì 25 º 6 (mod 19) ị 5n-1 º 6n-1 (mod 19) ị 25n-1.10 + 9. 6n-1 º 6n-1.19 (mod 19) º 0 (mod 19) Bài 3: Đặt A = 3p - 2p - 1 (p lẻ) Dễ dàng CM A M 2 và A M 3 ị A M 6 Nếu p = 7 ị A = 37 - 27 - 1 M 49 ị A M 7p Nếu p ạ 7 ị (p, 7) = 1 Theo định lý Fermat ta có: A = (3p - 3) - (2p - 2) M p Đặt p = 3q + r (q ẻ N; r = 1, 2) ị A = (33q+1 - 3) - (23q+r - 2) = 3r.27q - 2r.8q - 1 = 7k + 3r(-1)q - 2r - 1 (k ẻ N) với r = 1, q phải chẵn (vì p lẻ) ị A = 7k - 9 - 4 - 1 = 7k - 14 Vậy A M 7 mà A M p, (p, 7) = 1 ị A M 7p Mà (7, 6) = 1; A M 6 ị A M 42p. Bài 4: Nếu P = 2 ị 22 - 2 = 2 M 2 Nếu n > 2 Theo định lý Fermat ta có: 2p-1 º 1 (mod p) ị 2m(p-1) º 1 (mod p) (m ẻ N) Xét A = 2m(p-1) + m - mp A M p ị m = kq - 1 Như vậy nếu p > 2 ị p có dạng 2n - n trong đó N = (kp - 1)(p - 1), k ẻ N đều chia hết cho p 8. Phương pháp 8: sử dụng nguyên lý Đirichlet Nếu đem n + 1 con thỏ nhốt vào n lồng thì có ít nhất 1 lồng chứa từ 2 con trở lên. Ví dụ 1: CMR: Trong n + 1 số nguyên bất kỳ có 2 số có hiệu chia hết cho n. Giải: Lấy n + 1 số nguyên đã cho chia cho n thì được n + 1 số dư nhận 1 trong các số sau: 0; 1; 2;; n - 1 ị có ít nhất 2 số dư có cùng số dư khi chia cho n. Giả sử ai = nq1 + r 0 Ê r < n aj = nq2 + r a1; q2 ẻ N ị aj - aj = n(q1 - q2) M n Vậy trong n +1 số nguyên bất kỳ có 2 số có hiệu chia hết cho n. Nếu không có 1 tổng nào trong các tổng trên chia hết cho n như vậy số dư khi chia mỗi tổng trên cho n ta được n số dư là 1; 2; ; n - 1 Vậy theo nguyên lý Đirichlet sẽ tồn tại ít nhất 2 tổng mà chi cho n có cùng số dư ị (theo VD1) hiệu cùadr tổng này chia hết cho n (ĐPCM). Bài tập tương tự Bài 1: CMR: Tồn tại n ẻ N sao cho 17n - 1 M 25 Bài 2: CMR: Tồn tại 1 bội của số 1993 chỉ chứa toàn số 1. Bài 3: CMR: Với 17 số nguyên bất kỳ bao giờ cũng tồn tại 1 tổng 5 số chia hết cho 5. Bài 4: Có hay không 1 số có dạng: 19931993 1993000 00 M 1994 Hướng dẫn - Đáp số Bài 1: Xét dãy số 17, 172, , 1725 (tương tự VD2) Bài 2: Ta có 1994 số nguyên chứa toàn bộ số 1 là: 1 11 111 Khi chia cho 1993 thì có 1993 số dư ị theo nguyên lý Đirichlet có ít nhất 2 số có cùng số dư. Giả sử đó là ai = 1993q + r 0 Ê r < 1993 aj = 1993k + r i > j; q, k ẻ N ị aj - aj = 1993(q - k) mà (10j, 1993) = 1 M 1993 (ĐPCM) Bài 3: Xét dãy số gồm 17 số nguyên bất kỳ là a1, a2, , a17 Chia các số cho 5 ta được 17 số dư ắt phải có 5 số dư thuộc tập hợp{0; 1; 2; 3; 4} Nếu trong 17 số trên có 5 số khi chia cho 5 có cùng số dư thì tổng của chúng sẽ chia hết cho 5. Nếu trong 17 số trên không có số nào có cùng số dư khi chia cho 5 ị tồn tại 5 số có số dư khác nhau ị tổng các số dư là: 0 + 1 + 2 + 3 + 4 = 10 M 10 Vậy tổng của 5 số này chia hết cho 5. Bài 4: Xét dãy số a1 = 1993, a2 = 19931993, a1994 = đem chia cho 1994 ị có 1994 số dư thuộc tập {1; 2; ; 1993} theo nguyên lý Đirichlet có ít nhất 2 số hạng có cùng số dư. Giả sử: ai = 1993 1993 (i số 1993) aj = 1993 1993 (j số 1993) ị aj - aj M 1994 1 Ê i < j Ê 1994 ị 9. Phương pháp 9: phương pháp phản chứng Để CM A(n) M p (hoặc A(n) M p ) + Giả sử: A(n) M p (hoặc A(n) M p ) + CM trên giả sử là sai + Kết luận: A(n) M p (hoặc A(n) M p ) Ví dụ 1: CMR n2 + 3n + 5 M 121 với " n ẻ N Giải: Giả sử tồn tại n ẻ N sao cho n2 + 3n + 5 M 121 ị 4n2 + 12n + 20 M 121 (vì (n, 121) = 1) ị (2n + 3)2 + 11 M 121 (1) ị (2n + 3)2 M 11 Vì 11 là số nguyên tố ị 2n + 3 M 11 ị (2n + 3)2 M 121 (2) Từ (1) và (2) ị 11 M 121 vô lý Vậy n2 + 3n + 5 M 121 Ví dụ 2: CMR n2 - 1 M n với " n ẻ N* Giải: Xét tập hợp số tự nhiên N* Giả sử $ n ³ 1, n ẻ N* sao cho n2 - 1 M n Gọi d là ước số chung nhỏ nhất khác 1 của n ị d ẻ (p) theo định lý Format ta có 2d-1 º 1 (mod d) ị m < d ta chứng minh m\n Giả sử n = mq + r (0 Ê r < m) Theo giả sử n2 - 1 M n ị nmq+r - 1 M n ị 2r(nmq - 1) + (2r - 1) M n ị 2r - 1 M d vì r < m mà m ẻ N, m nhỏ nhất khác 1 có tính chất (1) ị r = 0 ị m\n mà m < d cũng có tính chất (1) nên điều giả sử là sai. Vậy n2 - 1 M n với " n ẻ N* Bài tập tương tự Bài 1: Có tồn tại n ẻ N sao cho n2 + n + 2 M 49 không? Bài 2: CMR: n2 + n + 1 M 9 với " n ẻ N* Bài 3: CMR: 4n2 - 4n + 18 M 289 với " n ẻ N Hướng dẫn - Đáp số Bài 1: Giả sử tồn tại n ẻ N để n2 + n + 2 M 49 ị 4n2 + 4n + 8 M 49 ị (2n + 1)2 + 7 M 49 (1) ị (2n + 1)2 M 7 Vì 7 là số nguyên tố ị 2n + 1 M 7 ị (2n + 1)2 M 49 (2) Từ (1); (2) ị 7 M 49 vô lý. Bài 2: Giả sử tồn tại n2 + n + 1 M 9 với " n ị (n + 2)(n - 1) + 3 M 3 (1) vì 3 là số nguyên tố ị ị (n + 2)(n - 1) M 9 (2) Từ (1) và (2) ị 3 M 9 vô lý Bài 3: Giả sử $ n ẻ N để 4n2 - 4n + 18 M 289 ị (2n - 1)2 + 17 M 172 ị (2n - 1) M 17 17 là số nguyên tố ị (2n - 1) M 17 ị (2n - 1)2 M 289 ị 17 M 289 vô lý. Bài tập và phương pháp Cỏch 1: Để chứng minh A(n) chia hết cho k, cú thể xột mọi trường hợp số dư khi chia n cho k. Vớ dụ: Chứng minh rằng: a) Tớch của hai số nguyờn liờn tiếp chia hết cho 2. b) Tớch của ba số nguyờn liờn tiếp chia hết cho 3. Giải: a) Viết tớch của hai số nguyờn liờn tiếp dưới dạng A(n) = n(n + 1). Cú hai trường hợp xảy ra : * n 2 => n(n + 1) 2 * n khụng chia hết cho 2 (n lẻ) => (n + 1) 2 => n(n +1) 2 b) Xét mọi trường hợp: n chia hết cho 3; n=3q+1; n = 3q+2 + Nếu n chia hết cho 3, hiển nhiên A(n) chia hết cho 3 + Nếu n = 3q+1 => n+2 = 3q+3 chia hết cho 3 + Nếu n= 3q+2 => n+1 = 3q+2+1 = 3q+3 chia hết cho 3 Trong mọi trường hợp A(n) luôn chứa một thừa số chia hết cho 3. Vậy A(n) chia hết cho 3 (đpcm) Cỏch 2: Để chứng minh A(n) chia hết cho k, cú thể phõn tớch k ra thừa số: k = pq . + Nếu (p, q) = 1, ta chứng minh A(n) p v