Chuyên đề Chia hết và Đồng dư

PHẦN SỐ HỌC
Bài 1: TÍNH CHIA HẾT TRÊN TẬP HỢP SỐ NGUYÊN.
SỐ NGUYÊN TỐ.
A. Nhắc lại và bổ sung các kiến thức cần thiết:
I. Tính chia hết:
1. Định lí về phép chia: Với mọi số nguyên a,b (b0), bao giờ cũng có một cặp số nguyên q, r sao cho : a = bq + r với .
a gọi là số bị chia , b là số chia, q là thương và r là số dư.
Trong trường hợp b > 0 và r0 có thể viết: a = bq + r = b(q +1)+ r - b.
Ví dụ: Mọi số nguyên a đều có dạng: 
a = 2q 1 (xét phép chia cho b = 2)
a = 3q ; 3q 1 (xét phép chia cho b = 3)
a = 4q ; 4q 1 ; 4q 2 (xét phép chia cho b = 4).
a = 5q; 5q 1; 5q 2 (xét phép chia cho b = 5)
......................
2. Tính chia hết: Nếu a chia b mà số dư r = 0, ta nói :
 a chia hết cho b hay a là bội của b (kí hiệu a b)
b chia hết a hay b là ước của a (kí hiệu b\ a)
Vậy: ab (b\ a) khi và chỉ khi có số nguyên q sao cho a = bq.
3. Các tính chất:
	1) Nếu ab thì a b (b0)
	2) a a; 0 a với mọi a 0
	3) a 1 với mọi a
	4) Nếu a m thì an m (m 0, n nguyên dương).
	5) Nếu ab và ba thì |a| = |b|
	6) Nếu a b và b c (b,c0) thì a c.
	7) Nếu a c và bc(c0) thì (ab)c. Điều ngược lại không đúng.
	8) Nếu a m hoặc b m thì ab m(m0). Điều ngược lại không đúng.
	9) Nếu ap và a q, (p, q)= 1 thì a pq
	10) Nếu a = mn; b = pq và mp nq thì ab
11) Nếu ab m và (b,m) = 1 thì a m
12) Nếu ab m và a m thì b m
II. Số nguyên tố:
1.Định nghĩa: Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước là 1 và chính nó.
	Hợp số là số tự nhiên lơn hơn 1 có nhiều hơn hai ước.
	Số 1 và số 0 không phải là số nguyên tố cũng không phải là hợp số.
2. Định lí cơ bản của số học: Mọi số tự nhiên lớn hơn 1 đều phân tích được ra thừa số nguyên tố một cách duy nhất(không kể thứ tự các thừa số).
	Số nguyên tố được coi như là tích chỉ gồm một thừa số là chính nó.
	Có vô số số nguyên tố (không có số nguyên tố lớn nhất).
	Số hoàn chỉnh: là số bằng tổng các ước của nó không kể bản thân nó.
	Ví dụ: 6 , 28, ... , 2n-1(2n - 1)
III. Một số phương pháp thông thường để giải bài toán về chia hết: 
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ụ 1: 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) Chứng minh tương tự a.
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ụ 2: 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ụ 3 : 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ụ 4: 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). Gv diễn đạt đề thành lời.
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ụ 5: 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
Ví dụ 6: 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.
IV. Một số phương pháp đặc biệt để giải toán chia hết:
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ụ 7: 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ụ 8: Chứng minh : 16n - 15n - 1 chia hết cho 225.
Đặ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
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ụ 9: 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 giả thiết.
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
B. PHẦN BÀI TẬP: Chứng minh: 
1. a) 192007 - 192006 chia hết cho 9.
 b) 92n + 14 chia hết cho 5.
 c) Tổng của 3 số tự nhiên liên tiếp chia hết cho 3, tổng của 5 số tự nhiên liên tiếp chia hết cho5.
2. Tích của một số chính phương và một số tự nhiên đứng liền trước nó là một số chia hết cho 12.
3. (n2 - 1)n2(n2 + 1) chia hết cho 60
4. a) n2 + 11n + 39 không chia hết cho 49
 b) n2 + 3n +5 không chia hết cho 11
5. a) n4 + 6n3 + 11n2 + 6n chia hết cho 24.
 b) n4 - 4n3 - 4n2 - 16n (chẵn, n > 4) chia hết cho 384.
6. 4n + 15n - 1 chia hết cho 9.
7. n2 + 4n + 3 (n lẻ) chia hết cho 8.
8. n3 + 3n2 - n - 3 chia hết cho 48.
9) 36n -26n chia hết cho 35
10) ab(a2 + b2)(a2 - b2) chia hết cho 30 với mọi số nguyên a,b.
11) a) (62n + 19n - 2n+1) chia hết cho17.
 b) (7.52n + 12.6n) chia hết cho 19.
 c) (5n+2 + 26.5n + 82n+1) chia hết cho 59.
12) a)a2 + b2 chia hết cho 7 thì a và b cũng chia hết cho 7.
13) 55552222 + 22225555 7
Bổ sung: Nhị thức Newton:
an - bn a - b (với mọi n) , an + bn a + b (n lẻ) ; an - bn a + b (n chẵn) 
Hướng dẫn giải:
1. a) = 192006.(19 - 1) = 192006.18 9
 b) = (81n -1) + 1 + 14 = (81 - 1). Q + 15 5
 c) (n + 1) + (n + 2) + (n +3) = 3n + 6 3
2. n2(n2 - 1) = n2(n - 1)(n + 1) = [(n -1).n] . [n. (n + 1)] 3; 4.
3. = (n - 1)(n + 1)n . n(n2 - 4 + 5)
 = (n - 1) .n. n. (n + 1)(n+ 2) (n - 2) + 5(n - 1)(n + 1) n . n 5; 4; 3.
4. a) = n2 + 4n + 7n + 28 + 11 = 
Bài 2: 
ĐỒNG DƯ THỨC .
A. Tóm tắt lý thuyết:
I. Định nghĩa: 
1.Định nghĩa: Cho số nguyên m > 0.Nếu hai số nguyên a và b khi chia cho m có cùng số dư thì ta nói rằng a đồng dư với b theo môđun m và viết: 
 	 ab (modm). 
2. Ví dụ: 3 5 (mod 2)
	 14 0 (mod 7) ...
II. Tính chất : 
Nếu a b (mod m) thì a - b m
Nếu a b (mod m) và b c (mod m) thì a c (mod m)
Nếu a b (mod m) và c d (mod m) thì a c b d (mod m)
Nếu a b (mod m) và c d (mod m) thì ac bd (mod m)
Nếu a b (mod m) thì an bn (mod m)
Nếu a b (mod m) thì ka kb (mod m) với k > 0
Nếu ka kb (mod km) thì a b (mod m) với k > 0
Nếu ka kb (mod m) và (k , m) = 1thì a b (mod m) .
Định lí Fermat: Nếu p là số nguyên tố thì : np n (mod p) ; n Z
Hoặc : Nếu p là số nguyên tố thì : np-1 1 (mod p), với (n,p) = 1
Định lí Euler : Cho m là một số nguyên dương bất kì và (m) là số các số dương nhỏ hơn m và nguyên tố với m. Thế thì : n(m) 1 (mod m)
* Cách tính (m) : phân tích m ra thừa số nguyên tố : 
	m = a1α. a2β ... anλ . Thế thì : (m) = m
B. Bài tập ứng dụng:
Bài 1: Chứng minh 2100 - 1 chia hết cho 5
Giải : Ta có 24 1 (mod 5) 
 => (24)25 125 (mod 5).
 => 2100 1 (mod 5) hay 2100 - 1 5
Bài 2: Tìm số dư của phép chia 299 cho 3.
Giải : Có 23 -1 (mod 3)
 (23)33 (-1)33 (mod 3)
	 299 -1 (mod 3) . Vậy 299 chia 3 dư 2.
Bài 3 : Tìm chữ số cuối cùng của 2999
Bài 4: Chứng minh 22008 không chia hết cho 10.
Bài 5: Chứng minh rằng trong các số tự nhiên thế nào cũng có số k sao cho 1983k - 1 chia hết cho 105.
Giải: 
Cách 1: Áp dụng nguyên tắc Dirichlet:
	Cho k lần lượt lấy 105 + 1 giá trị liên tiếp từ 1 trở đi, ta được 105 + 1 giá trị khác nhau của 1983k - 1. Chia 105 +1 số này cho 105 , ta có nhiều nhất là 105 số dư, do đó theo nguyên tắc Dirichlet, phải có hai số cho cùng số dư khi chia cho 105. Giả sử đó là hai số 1983m -1 và 1983n - 1 (m > n). Thế thì hiệu của hai số này phải chia hết cho 105:
(1983m - 1) - (1983n -1) = 1983m - 1983n = 1983n (1983m-n -1) 105.
Do 1983 không chia hết cho 105 => 1983n cũng không chia hết cho 105.
Vì vậy 10m-n - 1 chia hết cho 105. Như vậy tìm được số k = m-n sao cho 1983k - 1 chia hết cho 105.
Cách 2: Áp dụng định lí Euler:
	Vì 1983 không chia hết cho 2 và không chia hết cho 5 , còn 105 = 2555 nên (1983, 105) = 1 . Áp dụng định lí Euler: 1983(10) 1 (mod 105)
Mà (10) = 105(1 - ) (1 - ) = 4. 104.
Nên ta có 19834.10 1 (mod 105).
số 4.104 là số k phải tìm.
Đề bài áp dụng:
1. Tìm số dư khi :
a) chia 8! Cho 11	b) chia 15325 -1 cho 9
c) chia 340 cho 83.	d) chia 21000 cho 25
e) chia 301293 cho 13
2. Chứng minh rằng : 
a) 24n - 1 15	b) 270 + 370 13	c) 122n+1 - 11n+2 133
d) 22225555 + 55552222 7	e) 14k + 24k + 34k + 44k không chia hết cho 5
Bài 3: 	 PHƯƠNG TRÌNH NGHIỆM NGUYÊN
1. Định nghĩa: Phương trình nghiệm nguyên (còn gọi là phương trình Điôphan) là một phương trình có nhiều ẩn số, với tất cả các hệ số đều là số nguyên, và ta phải tìm các nghiệm nguyên của nó.
2.Ví dụ : (Bài toán cổ) Trăm trâu trăm cỏ,
	 Trâu đứng ăn năm,
	 Trâu nằm ăn ba,
	 Lụ khụ trâu già,
	 Ba con một bó.
	Hỏi có bao nhiêu trâu đứng, bao nhiêu trâu nằm, bao nhiêu trâu già?
Giải:
Gọi số trâu đứng là x, số trâu nằm là y, thì số trâu già là : 100 - (x + y)
Ta có phương trình: 
	 hay 7x + 4y = 100
Nếu không có điều gì hạn chế thì phương trình này có vô số nghiệm:
	Nhưng theo đề toán thì x,y (số trâu) phải là số nguyên (dương) nên ta chỉ phải tìm các nghiệm nguyên dương của phương trình .
	Đó là một ví dụ điển hình về phương trình nghiệm nguyên.
	Sự nghiên cứu về phương trình nghiệm nguyên có sự đóng góp to lớn của rất nhiều nhà toán học nổi tiếng: Euclide và Archimède, Fermat, Euler và Lagrange, Gauss, Dirichlet, Riemann và Hilbert, ...
	Sau đây chúng ta sẽ xét một vài dạng phương trình nghiệm nguyên đơn giản nhất .
3. Phương trình bậc nhất:
a) Phương trình bậc nhất hai ẩn: là phương trình có dạng : ax + by = c , trong đó a, b, c là số nguyên, a, b khác 0
* Chú ý : Có thể giả thiết a, b, c nguyên tố cùng nhau (vì nếu không thì có thể chia hai vế cho ƯCLN của chúng)
Định lí: Phương trình ax + by = c có nghiệm nguyên khi và chỉ khi (a,b) = 1
Ví dụ : Các pt: 7x + 4y = 100 ; 4x + 2y = 5 , ...
Định lí 2: Nếu phương trình ax + by = có một nghiệm nguyên là cặp số xo,yo thì nó có vô số nghiệm nguyên, đó là tập hợp các cặp số có dạng :
 ; với t là số nguyên tuỳ ý (t = 0; 1; 2; 3; ...)
Ta gọi xo ; yo là một nghiệm riêng của pt, còn công thức trên là nghiệm tổng quát của phương trình.
Muốn giải phương trình ax + by = c , với (a;b) = 1 , ta chỉ cần tìm một nghiệm riêng nào đó của nó.
Ví dụ: Giải pt : 7x + 4y = 100.
Ta thấy x = 0 ; y = 25 là một nghiệm riêng của pt. Do đó nghiệm tổng quát của pt là : , với t = 0; 1; 2; 3; ...
Đối với bài toán “trăm trâu, trăm cỏ” ta phải tiếp tục xét thêm: x,y (số trâu) phải là số nguyên (dương), tức: 
	x = 4t > 0 ó t > 0
	y = 25 - 7t > 0 ó 0 < t < 4.
Nghĩa là chỉ được lấy t = 1,2,3:
	t = 1 => x = 4 ; y = 18 ; z = 78
	t = 2 => x = 8 ; y = 11 ; z = 81
	t = 2 => x = 12 ; y = 4 ; z = 84
ĐỀ TOÁN:
1. Tìm x ; y nguyên dương thoả mãn :
a) 5x + 3y = 2	b) 32x - 40y = 38	c) 38x + 117y = 15
2. Tìm tất cả các số nguyên dương x , y thoả mãn phương trình:
a) 5x + 7y = 112	b) 5x + 19y = 674	c) 3x2 + 10xy + 8y2 = 96.
3. Tìm nghiệm nguyên dương nhỏ nhất của phương trình:
a) 15x - 49y = 11	b) 41x - 37y = 187
4. Tìm nghiệm nguyên của phương trình:
	2x2 + xy + 7 = 0
5. Ba người đi câu cá . Trời đã tối và mệt lả, họ vất cá trên bờ sông , rồi mỗi người tìm một nơi lăn ra ra ngủ. Người thứ nhất thức dậy , đến bên bờ sông, đếm số cá thấy chia ba thừa một con , bèn vứt một con xuống sông và xách 1/3 về nhà.Người thứ hai thức dậy, tưởng hai bạn mình còn ngủ, đến bờ sông đếm số cá, rồi vứt 1 xuống sông và xách 1/3 về nhà. Người thư ba thức dậy , cũng nghĩ là mình dậy sớm nhất nên lại làm như hai người trước.
Biết họ là ba người đi câu dở, tìm số cá ba người đã câu được?