Chuyên đề bồi dưỡng học sinh giỏi - Các phương pháp giải bà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ố...â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 +...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