Tài liệu Toán học - Các phương pháp giải toán chia hết

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 +  ... 
ị 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à A(n) q.
	+ Nếu (p, q) 1, ta phõn tớch A(n) = B(n) .C(n) rồi chứng minh:B(n) p và C(n) q .
Vớ dụ 1: a) Chứng minh: A(n) = n(n +1)(n + 2) 6.
 b) Chứng minh: tớch của hai số chẵn liờn tiếp chia hết cho 8.
Giải: a) Ta cú 6 = 2.3; (2,3) = 1 . Theo chứng minh trờn đó cú A(n) chia hết cho 2 và 3. Do đú A(n) chia hết cho 6.
	 b) Ta viết A(n) = 2n(2n + 2) = 2n. 2(n +1) = 4n(n + 1).
	 8 = 4 . 2.
	Vỡ 4 4 và n(n +1) 2 nờn A(n) 8
Vớ dụ 2 : Chứng minh rằng n5 - n chia hết cho 10, với mọi số nguyờn dương n.	
(Trớch đề thi HSG lớp 9 cấp tỉnh năm học 2005 - 2006)
Giải: A(n) = n5 - n = n(n4 - 1) = n(n2 - 1)(n2 + 1) = n(n - 1)(n + 1)(n2 +1) 2
	n = 5k + 1 => (n - 1) 5
	n = 5k + 4 => (n + 1) 5.
	n = 5k + 2 => n2 + 1 = (5k + 2)2 + 1 = (25k2 + 20k + 4 + 1) 5
 	n = 5k + 3 => n2 + 1 = (5k + 3)2 + 1 = (25k2 + 30k + 9 + 1) 5
Vậy : A(n) chia hết cho 2 và 5 nờn phải chia hết cho 10.
Cỏch 3: Để chứng minh A(n) chia hết cho k, cú thể biến đổi A(n) thành tổng (hiệu) của nhiều hạng tử, trong đú mỗi hạng tử đều chia hết cho k. (Đó học trong tớnh chất chia hết của một tổng ở lớp 6)
(Liờn hệ: A(n) khụng chia hết cho k ...)
Vớ dụ 1: Chứng minh n3 - 13n (n > 1) chia hết cho 6. (Trớch đề thi HSG cấp II toàn quốc năm 1970). Giải: n3 - 13n = n3 - n - 12n = n(n2 - 1) - 12n = (n - 1)n(n + 1) - 12n
(n - 1)n(n + 1) là tớch của 3 số tự nhiờn liờn tiếp nờn chia hết cho 6 ; 12n 6 . Do đú A(n) 6
Vớ dụ 2: Chứng minh n2 + 4n + 5 khụng chia hết cho 8 , với mọi số n lẻ.
Giải: Với n = 2k +1 ta cú: 
A(n) = n2 + 4n + 5 = (2k + 1)2 + 4(2k + 1) + 5 = 4k2 + 4k + 1 + 8k + 4 + 5
 = 4k(k + 1) + 8(k + 1) + 2.
A(n) bằng tổng của ba hạng tử, trong đú hai hạng tử đầu đều chia hết cho 8 , duy chỉ cú hạng tử 2 khụng chia hết cho 8. Vậy A(n) khụng chia hết cho 8.
Cỏch 4: Phõn tớch A(n) thành nhõn tử. Nếu cú một nhõn tử chia hết cho k thỡ A(n) chia hết cho k.
Hệ quả: Nếu A(n) = B(n).C(n) mà B(n)và C(n) đều khụng chia hết cho k thỡ A(n) khụng chia hết cho k
A(n) = k . B(n).
Trường hợp này thường sử dụng các kết quả:
* (an - bn ) chia hết cho (a - b) 	với (a ạ b)
* (an - bn ) chia hết cho (a - b) 	với (a ạ ± b; n chẵn)
(an - bn ) chia hết cho (a - b) 	với (a ạ - b; n lẻ)
Vớ dụ 1: Chứng minh : 2 + 22 + 23 + ... + 260 chia hết cho 15.
Giải: Ta cú: 
2 + 22 +23 + ... + 260 = (2 + 22 + ... + 24) + (25+ ... + 28) + ... + (257 +...+ 260)
= 2(1 + 2 + 4 + 8) + 25(1 + 2 + 4 + 8) + ... + 257(1 + 2 + 4 + 8) 
= 15.(2 + 25 + ... + 257) 15.
Vớ dụ 2: Chứng minh rằng: 27 + 37 + 57 chia hết cho 5
Giải: Vì 7 là số lẻ nên (27 + 37) chia hết cho (2 + 3)
hay 27 + 37 chia hết cho 5 => 27 + 37 + 57 chia hết cho 5 (đpcm)
mà 	 57 chia hết cho 5 
Cỏch 5: Dựng nguyờn tắc Dirichlet: 
Nguyờn tắc Dirichlet phỏt biểu dưới dạng hỡnh ảnh như sau:
Nếu nhốt k chỳ thỏ vào m chuồng mà k> m thỡ phải nhốt ớt nhất hai chỳ thỏ vào chung một chuồng.
Vớ dụ: Chứng minh rằng trong m + 1 số nguyờn bất kỡ thế nào cũng cú hai số cú hiệu chia hết cho m.
Giải: Chia một số nguyờn bất kỡ cho m ta được số dư là một trong m số 0; 1 ; 2; 3; ...; m - 1. Theo nguyờn tắc Dirichlet, chia m + 1số cho m thỡ phải cú ớt nhất hai số cú cựng số dư . Do đú hiệu của hai số này sẽ chia hết cho m.
Cỏch 6: Dựng phương phỏp qui nạp toỏn học: Để chứng minh A(n) k ta làm theo trỡnh tự sau:
Thử với n = 1 hoặc 2(Tức số n nhỏ nhất chọn ra). Nếu sai => Dừng.Nếu đỳng A(1)k.Tiếp tục: 
Giả sử A(k) k.
Chứng tỏ A(k + 1) k. Nếu đỳng => Kết luận : A(n) k
Vớ dụ: Chứng minh : 16n - 15n - 1 chia hết cho 225.
Giải: Đặt A(n) = 16n - 15n -1 , ta cú : A(1) = 16 - 15 - 1 = 0 225 => A(1) đỳng.
Giả sử A(k) đỳng : A(k) = 16k - 15k -1 225. 
Ta chứng minh A(k + 1) đỳng, tức là c/m: 16k + 1 - 15(k + 1) - 1225.
Thật vậy, 16k+1 - 15(k + 1) - 1 = 16. 16k - 15k - 15 - 1
 = (15 + 1) 16k - 15k - 15 - 1
	 = 15.16k + 16k - 15k -15 - 1
	 = (16k - 15k - 1) + 15(16k - 1) 
 = (16k - 15k - 1) + 15(16 - 1) (16k-1 + ... +1)
	 = (16k - 15k - 1) + 225(16k-1+ ... + 1) 225
Khi gặp những bài toỏn chứng minh với là số tự nhiờn, ta vẫn thường dựng phương phỏp quy nạp. Cụ thể lược đồ của cỏch giải này là: 
Giả sử , ta chứng minh . Nhưng để ý rằng nếu thỡ 
Vỡ vậy cú thể xem đõy là một biến dạng của phương phỏp quy nạp, để chứng minh ta qua hai bước: 
Áp dụng phương phỏp này, ta cú thể giải được một loạt cỏc bài toỏn chia hết khỏ cồng kềnh.
Vớ dụ 1: Chứng minh cú chia hết cho 125.
Giải: Cú .
Xột nhưng nờn (đpcm)
Vớ dụ 2: Chứng minh cú chia hết cho 64.
Giải: Cú 
Xột 
Lại ỏp dụng phương phỏp trờn với 
Cỏch 7: Phương phỏp phản chứng:
Để chứng minh A(n) k ta chứng minh A(n) khụng chia hết cho k là sai.
	A => B ú B => A
Vớ dụ: Chứng minh nếu a2 + b2 3 thỡ a và b đều chia hết cho 3.
Giải: Giả sử a và b khụng chia hết cho 3 => a = 3k 1 ; b = 3h 1
a2 + b2 = (3k 1)2 + (3h 1)2 = 9k2 6k + 1 + 9h2 6h + 1 
 	 = 3(3k2 + 3h2 2k 2h) + 2 khụng chia hết cho 3 mõu thuẫn với GT
Tương tự cho trường hợp chỉ cú một trong hai số chia hết cho 3.
Do đú a và b phải chia hết cho 3.