Các phương pháp giải các bài toán chia hết

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ả 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ý. II. Phép chia hết * Tóm tắt lý thuyết 1. Định lý về phép chia hết: a) Định lý Cho a, b là các số nguyên tuỳ ý, , khi đó có 2 số nguyên q, r duy nhất sao cho : với , a là só bị chia, b là số chia, q là thương số và r là số dư. Đặc biệt với r = 0 thì a = b.q Khi đó ta nói a chia hết cho b hay b là ước của a, ký hiệu . có số nguyên q sao cho a = b.q Vậy b) Tính chất a) Nếu và thì b) Nếu và thì a = b c) Nếu , và (b,c) = 1 thì d) Nếu và (c,b) = 1 thì 2. Tính chất chia hết của một tổng, một hiệu, một tích. - Nếu - Nếu - Nếu .b - Nếu a m (n là số tự nhiên) 3. Đồng dư thức a) Định nghĩa : Cho số nguyên m > 0. Nếu 2 số nguyên a, b cho cùng số dư khi chia cho m thì ta nói a đồng dư với b theo môđun m . Kí hiệu : b) Tính chất a) b) c) d) Phương pháp chứng minh chia hết Vấn đề 1: Phương pháp 1: Dùng tính chất Trong n ( số nguyên liên tiếp có một và chỉ một số chia hết cho n. Ví dụ 1: a) Tích 5 số tự nhiên liên tiếp chia hết cho 120. b) Chứng minh rằng với mọi số nguyên n thì Giải a) Ta có 120 = Trong 5 số nguyên liên tiếp phải có 2 số chẵn liên tiếp nên tích chia hết cho 8. Mặt khác trong 5 số nguyên liên tiếp có 1 số chia hết cho 3 và 1 số chia hết cho 5 nên tích chia hết cho 3. 5 mà (3,5,8) = 1 . Vậy tích 5 số tự nhiên liên tiếp chia hết cho 120. b) Ta có : Vì n-1, n, n+1 là 3 số nguyên liên tiếp nên tích ( n-1) n (n+1) Phương pháp 2: Dùng công thức khai triển nếu n lẻ nếu n chẵn Ví dụ 2 a) Với n chẵn, chứng minh rằng b) Chứng minh rằng : Giải: a) Ta có 323 = 17 . 19 và (1) Vì và do n chẵn. Mặt khác : (2) Vì do n chẵn. Từ (1) và (2) suy ra b) Ta có : 2222;5555 Vì Phương pháp 3: Dùng định lý về phép chia có dư Để chứng minh ta xét về mọi trường hợp về số dư. Khi chia n cho p có thể dư là 0; 1; 2; ...; p - 1 hoặc là nếu p lẻ. Ví dụ 3: Chứng minh rằng nếu thì Giải: Vì nên n = 3k + 1 hoặc n = 3k + 2 1) Nếu n = 3k + 1 thì Vì 2) Nếu n = 3k + 2 thì Vậy thì Phương pháp 4: Sử dụng nguyên tắc Đirichlet Nếu đem n + 1 vật xếp vào n ngăn kéo thì có ít nhất một ngăn kéo chứa từ 2 vật trở lên. Ví dụ 4: Chứng minh rằng a) có thể tìm được một số có dạng 19911991...19910...0 và chia hết cho 1992. b) Trong 8 số tự nhiên mỗi số có 3 chữ số, bao giờ cũng chọn được 2 số mà khi viết liền nhau ta được một số có 6 chữ số và chia hết cho 7. Giải: a) Lấy 1992 số 1991; 19911991 ;...; chia cho 1992. Vì đây là dãy các số lẻ nên không có số nào chia hết cho 1992, do đó dư trong phép chia các số này cho 1992 chỉ thể là 1; 2; ...; 1991. Vậy phải có 2 số có cùng dư khi chia cho 1992, hiệu 2 số đó có dạng 19911991...19910...0 và chia hết cho 1992. b) Lấy 8 số đã cho chia cho 7 thì có 2 số có cùng số dư, giả sử là và chia cho 7 có số dư là r. Khi đó : = = (đpcm) Phương pháp 5: Dùng quy nạp toán học Ta cần chứng minh (1) với n = 1; 2; ... 1) Ta chứng minh (1) đúng với n = 1, nghĩa là 2) Giả sử (1) đúng với n = k , nghĩa là ta có 3) Ta chứng minh (1) đúng với n = k+1 , nghĩa là phải chứng minh Ví dụ 5: Chứng minh rằng với mọi : Giải: Với n = 1 ta có: Giả sử với n = k, ta có: ( 1) với m Với n = k + 1 ta có: (2) Từ (1) suy ra: , thay vào (2) ta có: Vậy : Phương pháp 6: Dùng định lý Fermat Với P là số nguyên tố ta có: Đặc biệt nếu (a,p) =1 thì Ví dụ 6: Chứng minh rằng Giải: Theo định lý Fermat : Do đó : Dấu hiệu chia hết Vấn đề 2: *Dấu hiệu chia hết cho 6: Một số chia hết cho 6 khi và chỉ khi nó đồng thời chia hết cho 2 và cho 3. 1) Các dấu hiệu chia hết đơn giản a. Chia hết cho 2, 5, 4, 25 và 8; 125. ( hoặc 25) ( hoặc 25) ( hoặc 125) ( hoặc 125) b) Chia hết cho 3; 9. (hoặc 9) ( hoặc 9) Nhận xét: Dư trong phép chia N cho 3 ( hoặc 9) cũng chính là dư trong phép chia tổng các chữ số của N cho 3 ( hoặc 9). Ví dụ 7: Tìm các chữ số x, y để: a) b) Giải: a) Để ta phải có chia hết cho 9 và 5 y = 0 hoặc y = 5 Với y = 0 thì từ ta phải có 1+3+5+x+4 khi đó ta có số 13554 với x = 5 thì từ : ta phải có 1+3+5+x+4 +5 lúc đóta có 2 số: 135045; 135945. b) Ta có Vì nên bằng 72 hoặc 144. + Với =72 thì =08, ta có số: 123408. + Với =14 thì =80, ta có số 123480 2. Một số dấu hiệu chia hết khác a) Dấu hiệu chia hết cho 11: Cho Ví dụ 8 Tìm các chữ số x, y để Giải: Ta có: 1375 = 11.125. Vậy số cần tìm là 713625 b) Dấu hiệu chia hết cho 101 Ví dụ 9 a) Hỏi số có chia hết cho 101 không? b) Tìm n để Giải: a) Ghép 2 chữ số liên tiếp nhau thì A1991 có 2 cặp số là 91;19 Ta có: 1991.91-1991.19 = 1991. 72 101 nên b) c) Dấu hiệu chia hết cho7;13 Các bài tập khác về chia hết Vấn đề 3 1) Chứng minh không chia hết - Nếu và thì - Nếu và thì - Nếu thì hoặc với p là số ngyuên tố. - Số chính phương( là bình phương của số tự nhiên ) chia hết cho số nguyên tố p thì sẽ chia hết cho p2. Vậy nếu nhưng thì n là số chính phương. Ví dụ 11 Chứng minh rằng với mọi số tự nhiên n : a) b) Giải: a)Với n = 3k thì do đó Với n = 3k + 1 thì Với n = 3k+2 thì do đó Vậy vớ mọi n. 2) Tìm số tự nhiên n để a(n) Phương pháp: Giả sử có A(n), ta biến đổi hoặc dùng phép chia đa thức đẻ đi đến hằng số m , từ đó suy ra n. Kiểm nghiệm các giá trị tìm được n. Ví dụ 12: a) Tìm n > 0 sao cho chia hết cho n +1 b) Tìm n > 0 và sao cho 3n - 8 Giải: a) Giả sử Thử lại với n = 2 ta có : 2 = 2. Vậy , n > 0 b) Giả sử Vậy 3n - 8 với n > 0; 3) Bài tập về số chính phương Phương pháp 1: Dùng tính chẵn lẻ Ví dụ 13 Chứng minh rằng số chính phương có chứa chữ số lẻ ở hàng chục thì chữ số hàng đơn vị luôn bằng 6. Giải: Giả sử số chính phương có dạng Chữ số hàng chục của 20n(5n + b) là chẵn nên theo giả thiết chữ số hàng chục của b2 phải lẻ, từ đó suy ra b = 6; 4. Khi đó b2 = 36; 16 nên chữ số hàng đơn vị của luôn bằng 6. Phương pháp 2: Sử dụng chia hết và chia có dư Ví dụ 14: Tìm số chính phương biết Giải: Giả sử = ( n - 10 )( n +10) Vì n < 100 và 101 là số nguyên tố nên n + 10 = 101 suy ra n = 91. Thử lại : = 912= 8281 có 82 - 81 = 1 Phương pháp 3 Sử dụng tính chất a) Nếu a là số chính phương và ( a, b) = 1 thì a và b đều là số chính phương b) Nếu có số nguyên m sao cho thì n không thể là số chính phương. Ví dụ 15 Chứng minh rằng tích của 4 số tự nhiên liên tiếp không thể là số chính phương. Giải: Ta có A = n(n+1)(n+2)(n+3) = Vậy A không thể là số chính phương. III) Các bài tập về chia hết 1.Chứng minh rằng: a) b) 2. Tìm số tự nhiên n để 3. Với 4 số nguyên a,b,c, d . Chứng minh rằng: (a-b)(a-c)(a-d)(b-c)(b-d)(c-d) 4. Chứng minh rằng với mọi n : a) b) 5. Chứng minh 6. Chứng minh rằng với mọi số tự nhiên n : a) b) 7. Với giá trị nào của n thì (n+5)(n+6)6n. Với 8. Tìm số nguyên tố p sao cho tổng tất cả các ước tự nhiên của p4 là một số chính phương. 9.Cho n là số tự nhiên , d là ước nguyên dương của 2n2 chứng minh rằng n2+d không chính phương.