Chuyên đề Số học Trường THCS Thanh Phú

Vì k(k + 1) 2 nên 4k(k + 1) 8 ; 8(k + 1) 8 và 2 không chia hết cho 8 nên n2 + 4n + 5 không chia hết cho 8.
5.5) Nếu số dư khi chia a cho b > 0 là r (0 1) cho b là số dư khi chia rn cho b (số dư này bằng rn nếu rn < b).
Ví dụ : Chứng minh rằng A(n) = n(n2 + 1)(n2 + 4) 5 với mọi số nguyên n.
Giải : 	n chia cho 5 dư 0 n 5
	n chia cho 5 dư ±1 n2 chia cho 5 dư (±1)2 = 1 n2 + 4 5
	n chia cho 5 dư ±2 n2 chia cho 5 dư (±2)2 = 4 n2 + 1 5
Ví dụ : Chứng minh rằng nếu n không chia hết cho 7 thì n2 + 1 hoặc n3 – 1 chia hết cho 7.
Giải : 	n không chia hết cho 7 nên n có dạng : 7k ± 1, 7k ± 2 hoặc 7k ± 3
	n = 7k ± 1 n3 = 7p ± 1
	n = 7k ± 2 n3 = 7q ± 8 = 7(q ± 1) ± 1
	n = 7k ± 3 n3 = 7m ± 27 = 7(m ± 4) ± 1
	Trong mọi trường hợp, n3 + 1 hoặc n3 – 1 là bội của 7.
5.6) Có thể dùng các công thức sau :
Ta đã biết : 	a2 – b2 = (a – b)(a + b)
	a3 – b3 = (a – b)(a2 + ab + b2)
	a3 + b3 = (a + b)(a2 – ab + b2)
Một cách tổng quát :
	an – bn = (a – b).M với n bất kì	(1)
	Trong đó : M = an – 1 + an – 2b + … + abn – 2 + bn – 1
	 với n chẵn	(2)
	Trong đó : N = 
	an + bn = (a + b).P với n lẻ	(3)
	Trong đó : P = an – 1 - an – 2b + … - abn – 2 + bn – 1
Do đó, theo (1) và (2) :
	an – bn chia hết cho a – b (nếu a ¹ b) với n bất kì.
	an – bn chia hết cho a + b (nếu a ¹ -b) với n chẵn.
Theo (3) : 	an + bn chia hết cho a + b (nếu a ¹ -b) với n lẻ.
Ví dụ : a) Chứng minh rằng 24n – 1 15
Giải :	Ta có : 24 = 16, do đó : 24n – 1 = 16n – 1 = (16 – 1).M = 15.M
b) Chứng minh rằng 25 + 35 + 55 5
Giải : Vì 5 là số lẻ nên 25 + 35 = (2 + 3).P và 55 5 nên 25 + 35 + 55 5
5.6) Có thể chứng minh bằng quy nạp toán học :
	Để chứng minh một mệnh đề đúng với mọi số tự nhiên n bằng phương pháp quy nạp toán học, ta tiến hành theo ba bước sau :
Bước 1 : Kiểm tra mệnh đề đúng với n = 1 (hoặc n = no)
Bước 2 : Giả sử mệnh đề đúng với n = k > 1 (hoặc k > no) ; (Ta gọi là giả thiết quy nạp). Rồi chứng minh mệnh đề đúng với n = k + 1.
Bước 3 : Kết luận mệnh đề đúng với mọi số tự nhiên n.
Ví dụ : Chứng minh rằng 16n – 15n – 1 225.
Giải : 	Với n = 1 thì 16n – 15n – 1 = 16 – 15 – 1 = 0 225 (đúng)
	Giả sử 16k – 15k – 1 225
Ta chứng minh : 16k+1 – 15(k + 1) – 1 225.
Thật vậy : 16k+1 – 15(k + 1) – 1 = 16.16k – 15k – 15 – 1 = (15 + 1).16k – 15k – 15 – 1 =
= (16k – 15k – 1) + 15.16k – 15.
Theo giả thiết quy nạp (16k – 15k – 1) 225, 
Còn 15.16k – 15 = 15(16k – 1) = 15.(16 – 1).M 15.15.
Vậy 16k+1 – 15(k + 1) – 1 225.
5.7) Dùng nguyên lí Dirichlet :
Nguyên lí Dirichlet có thể phát biểu một cách tổng quát như sau :
“Nếu đem n + 1 con thỏ nhốt vào n cái chuồng thì có ít nhất một chuồng chứa từ 2 con thỏ trở lên”
Ví dụ : Chứng minh rằng trong n + 1 số nguyên bất kì có 2 số mà hiệu chia hết cho n.
Giải : Lấy n + 1 số nguyên bất kì chia cho n thì có n + 1 số dư. Nhưng khi chia một số cho n thì sẽ có n số dư từ 0 đến n – 1. Vậy trong n + 1 phép chia trên sẽ có 2 số có cùng số dư. Khi đó hiệu hai số này chia hết cho n.
Bài tập áp dụng :
Chứng minh rằng : A = 75(41975 + 41974 + 41973 + … + 4 + 5) + 25 chia hết cho 41976.
Giải : 	A = 25.3(41975 + 41974 + 41973 + … + 42 + 4 + 1) + 25
	A = 25.(4 – 1) (41975 + 41974 + 41973 + … + 42 + 4 + 1) + 25
	A = 25.(41976 – 1) + 25 = 25
Chứng minh rằng số P = luôn luôn là một số tự nhiên với mọi số tự nhiên x.
Giải : 	P = 
	Mà : x5 + 10x4 + 35x3 + 50x2 + 24x 
= x(x4 + 10x3 + 35x2 + 50x + 24)
= x[(x4 + 5x3 + 4x2) + (5x3 + 25x2 + 20x) + (6x2 + 30x + 24)]
= x[x2(x2 + 5x + 4) + 5x(x2 + 5x + 4) + 6(x2 + 5x + 4)]
= x(x2 + 5x + 4)(x2 + 5x + 6)
= x(x + 1)(x + 4)(x + 2)(x + 3).
Vì 120 = 3.5.8 với 3, 5, 8 đôi một nguyên tố cùng nhau, do đó chỉ cần chứng minh :	x(x + 1)(x + 4)(x + 2)(x + 3) lần lượt chia hết cho 3, 5, 8.
Chứng minh rằng : là tối giản.
Giải : Dùng thuật toán Ơclit.
Tìm n để các phân số sau là tối giản :
 b) 
Giải : 	a) n + 13 = n – 2 + 15 (n + 13 , n – 2) = (n – 2 , 15).
	 tối giản (n – 2 , 15) = 1 
 = 
Đã có (3 , 7) = (3 , 3n + 1) = (6n + 1 , 3n + 1) = 1. 
Cần có : (6n + 1 , 7) = 1
6n + 1 = 7n – (n – 1) (6n + 1 , 7) = (n – 1 , 7) = 1 n – 1 ¹ 7k n ¹ 7k + 1
Chứng minh rằng :
A = (n + 1)(n + 2)(n + 3)….(3n) 3n
B = 
Giải :	Chứng minh bằng quy nạp
a) Với n = 1, ta có : A = 2.3 3
	Giả sử mệnh đề đúng với n = k, tức là :
	Ak = (k + 1)(k + 2)(k + 3)…(3k) 3k (1)
Ta hãy xét : Ak + 1 = (k + 2)(k + 3)(k + 4)…[3(k + 1)] 3k + 1
	Ak + 1 = 3(k + 1)(k + 2)(k + 3)…(3k)(3k + 1)(3k + 2)
	 = 3Ak(3k + 1)(3k + 2)
Nhưng theo (1) thì Ak 3k. Vậy Ak + 1 = 3Ak(3k + 1)(3k + 2) 3k + 1
Vậy mệnh đề đúng với mọi số tự nhiên : n ³ 1
b) Với n = 0, ta có : B = 7 + 12 = 19 19
Giả sử mệnh đề đúng với n = k, tức là :
Bk = 7.52k + 12.6k 19 (1)
Ta hãy xét : Bk + 1 = 7.52(k + 1) + 12.6k + 1
	 = 7.52k.52 + 12.6k.6
	 = (6 + 19)7.52k + 12.6k.6
	 = 6(7.52k + 12.6k) + 19.7.52k
	 = 6Bk + 19.7.52k
Nhưng theo (1) thì Bk 19. Vậy Bk + 1 = 6Bk + 19.7.52k 19
Vậy mệnh đề đúng với mọi số tự nhiên n.
Chứng minh rằng : 
Trong 6 số nguyên dương liên tiếp không có hai số nào có ước chung d ³ 6.
Giải : 	Ước chung của hai số nguyên a và a + m phải là ước của a và m. Với 6 số nguyên dương liên tiếp thì 0 < m £ 5 d = (a, a + m) £ 5.
Chứng minh rằng với mọi số nguyên n ta có An = n2 + n + 1 không bao giờ chia hết cho 9.
Giải : 	Chứng minh bằng phương pháp phản chứng.
Giả sử ngược lại có số nguyên a sao cho A = a2 + a + 1 chia hết cho 9
 a2 + a + 1 = 9k 4a2 + 4a + 4 = 36k (2a + 1)2 = 36k – 3 
(2a + 1)2 = 3(12k – 1)
12k – 1 chia hết cho 3 (vô lý)
Vậy An = n2 + n + 1 không chia hết cho 9 với mọi số nguyên n.
Tìm hai số tự nhiên a và b, biết :
a + b = 128 và (a,b) = 16
a.b = 216 và (a,b) = 6.
Giải : 	a) Đặt a = 16m, b = 16n (m,n Î N)
	 a + b = 16m + 16n = 128 m + n = 8
m
0
1
2
3
4
5
6
7
8
n
8
7
6
5
4
3
2
1
0
Từ đó suy ra a, b.
b) Tương tự câu a.
Cho A = m + n và B = m2 + n2 , trong đó m và n là hai số tự nhiên nguyên tố cùng nhau. Tìm ước chung lớn nhất của A và B.
Giải : 	Đặt d = (m + n , m2 + n2) (m + n)2 d (m + n)2 – (m2 + n2) = 2mn d 
 d là ước chung của m + n và 2mn. (1)
(m,n) = 1 (m + n, n) = (m + n, m) = 1 (2)
Do (1) và (2) 2 d d = 1 hoặc d = 2.
II. Đồng dư thức :
Định nghĩa : 
Cho một số nguyên m > 0. Nếu hai số nguyên a và b cho cùng một số dư khi chia cho m (tức 
là a – b chia hết cho m) thì ta nói rằng a đồng dư với b theo module m và viết a º b (modm).
 Thí dụ : 
46 º 16 (mod 10) vì 46 – 16 = 30 10
5 º 1 (mod 2) vì 5 – 1 = 4 2
-2 º 16 (mod 3) vì –2 – 16 = –18 3
Nếu a – b chia hết cho m thì có một số nguyên t sao cho a – b = m.t
Do đó theo định nghĩa của đồng dư thức :
a º b (mod m) a – b = m.t (t nguyên) hay a = b + m.t
Trong trường hợp < m thì a º b (mod m) có nghĩa là chia a cho m có dư là b.
	Nói riêng : a º 0 (mod m) có nghĩa là a chia hết cho m.
Chú ý : Nếu nếu a º b (mod m) là sai thì ta cũng viết a º b (mod m)
Các tính chất của đồng dư thức :
Tính chất 1 : Với mọi số nguyên a, ta có : a º a (mod m)
Tính chất 2 : a º b (mod m) b º a (mod m)
Tính chất 3 : a º b (mod m), b º c (mod m) a º c (mod m)
Tính chất 4 : a º b (mod m), c º d (mod m) a + c º b + d (mod m)
Tính chất 5 : a º b (mod m), c º d (mod m) ac º bd (mod m)
Các hệ quả của tính chất 4 và tính chất 5 :
a1 º b1 (mod m), a2 º b2 (mod m), a3 º b3 (mod m), …, an º bn (mod m)
 a) a1 + a2 + a3 + … + an º b1 + b2 + b3 + … + bn (mod m)
 b) a1.a2.a3 … an º b1.b2. b3…bn (mod m)
 c) an º bn (mod m)
Tính chất 6 : Nếu a º b (mod m) và d là ước chung của a và b sao cho (d , m) = 1 thì :
 (mod m)
Tính chất 7 : Nếu a º b (mod m) và số nguyên dương d là ước chung của cả ba số a, b, m thì (mod )
Tính chất 8 : Nếu a º r (mod m) với 0 £ r < m, thì r chính là số dư trong phép chia a cho m.
Một số thí dụ áp dụng :
Ví dụ 1 : Chứng minh rằng các số A = 61000 - 1 và B = 61001 + 1 đề là bội của 7.
Giải : 	Ta có 6 º –1 (mod 7) 61000 º 1 (mod 7) A = 61000 – 1 º (mod 7)
Ta có 6 º –1 (mod 7) 61001 º –1 (mod 7) B = 61000 + 1 º (mod 7)
Ví dụ 2 : Tìm chữ số sau cùng của số 6713 và 21000
	(Tìm chữ số sau cùng của một số N có nghĩa là tìm số dư của phép chia N cho 10, tức là tìm số không âm nhỏ hơn 10 và đồng dư với N theo module 10)
Giải : 	Ta có 62 = 36 º 6 (mod 10)
	Do đó 6n º 6 (mod 10) với mọi n > 0
	Suy ra 6713 º 6 (mod 10). Tức là chữ số cuối cùng của 6713 là 6.
Chú ý rằng : 24 = 16 º 6 (mod 10) và 1000 = 4.250, ta có : 21000 = 24.250 = (24)250 
Do đó : 21000 º 6250 (mod 10). Tức là chữ số cuối cùng của 21000 cũng là 6.
Ví dụ 3 : Tìm số dư trong phép chia 3100 – 1 cho 7
Giải :	Ta có 33 = 27 º –1 (mod 7)
	3100 = 33.33 + 1 = (33)33.3
Do đó : (33)33 º –1 (mod 7) 3100 = (33)33.3 º –1.3 (mod 7) 3100 – 1 º –4 (mod 7)
Vậy số dư trong phép chia 3100 – 1 cho 7 là –4 (hay là 3)
Ví dụ 4 : Chứng minh rằng A = 22225555 + 55552222 7
Giải : Ta có 2222 º 3 (mod 7) 22225 º 35 º 5 (mod 7) 22225555 = (22225)1111 º 51111 (mod 7)
 	 5555 º 4 (mod 7) 55552 º 42 º 2 (mod 7) 55552222 = (55552)1111 º 21111 (mod 7)
Do đó : A = 22225555 + 55552222 = (22225)1111 + (55552)1111 º 51111 + 21111 (mod 7)
Ta lại có : 51111 + 21111 = (5 + 2).Q 7. Vậy A = 22225555 + 55552222 7
Ví dụ 5 : Chứng minh rằng chia hết cho 102010
Giải :	Ta chứng minh bài toán một cách tổng quát : 
	Với mọi số tự nhiên n thì chia hết cho 10n + 1
	Với n = 0 thì mệnh đề đúng : 11 – 1 = 10 10
Giả sử mệnh đề đúng với n = k, ta có :
	Ak = (1)
Ta xét :
Nhưng mọi lũy thừa của 11 đều đồng dư với 1 (mod 10) nên 10 số hạng trong móc vuông cũng vậy, do đó :
 º (mod 10)
Và biểu thức trong móc vuông chia hết cho 10
Mặt khác theo (1) : vậy :
	Ak + 1 10k + 1.10 = 10k + 2
Với n = 2009, ta có : chia hết cho 102010
Định lý Fermat :
“Nếu p là số nguyên tố thì np – n chia hết cho p với mọi số nguyên n”
np º n (mod p), p là số nguyên tố
Đặc biệt : nếu (n , p) = 1 thì np – 1 º 1 (mod m)
Ví dụ 1 : Chứng minh rằng 11991 + 21991 + 31991 + … + 19911991 chia hết cho 11 
Giải : 	Theo định lí Fermat thì a11 º a (mod 11), do đó a1991 º a11 (mod 11) º a (mod 11)
	Vậy 11991 + 21991 + 31991 + … + 19911991 º 1 + 2 + 3 + … + 1991 º 1991.