Chuyên đề số học: Bài toán chia hết

Chia sẻ: Thanh Tran | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

3.218
lượt xem 1.806
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chia hết là dạng toán quan trọng trong chương trình toán học THCS, kèm theo đó là các bài toán khó và hay. Bài toán này xin gửi đến các bạn đọc phương pháp giải các bài toán chia hết : phương pháp xét số dư, phương pháp qui nạp, phương pháp đòng dư... Mời các em cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chuyên đề số học: Bài toán chia hết

Chương 3 Bài toán chia h t 3.1 Lý thuy t cơ b n 29 3.2 Phương pháp gi i các bài toán chia h t 31 Ph m Quang Toàn (Ph m Quang Toàn) .v n 4 h Chia h t là m t đ tài quan tr ng trong chương trình S h c c a b c THCS. Đi kèm theo đó là các bài toán khó và hay. Bài vi t này xin c 2 gi i thi u v i b n đ c nh ng phương pháp gi i các bài toán chia h t: phương pháp xét s dư, phương pháp quy n p, phương pháp đ ng dư, v.v... 3.1 Lý thuy t cơ b n h o 3.1.1 u i Đ nh nghĩa v chia h t Đ nh nghĩa 3.1 Cho hai 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 V v i 0 ≤ r < b. a = bq + r Trong đó, ta nói a là s b chia, b là s chia, q là thương, r là s dư. Như v y, khi a chia cho b thì có th đưa ra các s dư r ∈ {0; 1; 2; · · · ; |b|}. Đ c bi t, v i r = 0 thì a = bq, khi đó ta nói a chia h t cho b (ho c a là b i c a b, ho c b là ư c c a a). Ta kí hi u b | a. Còn khi a không chia 29
30 3.1. Lý thuy t cơ b n h t cho b, ta kí hi u b a. Sau đây là m t s tính ch t thư ng dùng, ch ng minh đư c suy ra tr c ti p t đ nh nghĩa. 3.1.2 Tính ch t Sau đây xin gi i thi u m t s tính ch t v chia h t, vi c ch ng minh nguyên thì: Tính ch t 3.1– N u a = 0 thì a | a, 0 | a. .v n khá là d dàng nên s dành cho b n đ c. Ta có v i a, b, c, d là các s Tính ch t 3.2– N u b | a thì b | ac. Tính ch t 3.3– N u b | a và c | b thì c | a. 4 h 2 Tính ch t 3.4– N u c | a và c | b thì c | (ax ± by) v i x, y nguyên. c o Tính ch t 3.5– N u b | a và a | b thì a = b ho c a = −b. i h Tính ch t 3.6– N u c | a và d | b thì cd | ab. V u Tính ch t 3.7– N u b | a, c | a thì BCNN(b; c) | a. Tính ch t 3.8– N u c | ab và UCLN(b, c) = 1 thì c | a. Tính ch t 3.9– N u p | ab, p là s nguyên t thì p | a ho c p | b. T tính ch t trên ta suy ra h qu H qu 3.1– N u p | an v i p là s nguyên t , n nguyên dương thì pn | an . Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 31 3.1.3 M t s d u hi u chia h t Ta đ t N = an an−1 . . . a1 a0 D u hi u chia h t cho 2; 5; 4; 25; 8; 125 2|N ⇔ 2 | a0 ⇔ a0 ∈ {0; 2; 4; 6; 8} 5|N ⇔ 5 | a0 ⇔ a0 ∈ {0; 5} 4; 25 | N ⇔ 4; 25 | a1 a0 8; 125 | N ⇔ 8; 125 | a2 a1 a0 D u hi u chia h t cho 3 và 9 3; 9 | N ⇔ 3; 9 | (a0 + a1 + · · · + an−1 + an ) M t s d u hi u chia h t khác .v n 11 | N 101 | N ⇔ ⇔ 4 h 11 | [(a0 + a2 + · · · ) − (a1 + a3 + · · · )] 101 | [(a1 a0 + a5 a4 + · · · ) − (a3 a2 + a7 a6 + · · · )] 7; 13 | N 37 | N 19 | N ⇔ ⇔ ⇔ 2 7; 37 | [(a2 a1 a0 + a8 a7 a6 + · · · ) − (a5 a4 a3 + a11 a10 a9 + · · · )] c 37 | (a2 a1 a0 + a5 a4 a3 + · · · + an an−1 an−2 ) 19 | an + 2an−1 + 22 an−2 + · · · + 2n a0 3.2 h o Phương pháp gi i các bài toán chia h t 3.2.1 i Áp d ng đ nh lý Fermat nh và các tính ch t c a chia h t u V Đ nh lý Fermat nh Đ nh lý 3.1 (Đ nh lý Fermat nh )– V i m i s nguyên a và s nguyên t p thì ap ≡ p (mod p). Ch ng minh. 1. N u p | a thì p | (a5 − a). 2. N u p a thì 2a, 3a, 4a, · · · , (p − 1)a cũng không chia h t cho p. G i r1 , r2 , · · · , rp−1 l n lư t là s dư khi chia a, 2a, 3a, · · · , (p−1)a cho p. thì chúng s thu c t p {1; 2; 3; · · · ; p − 1} và đôi m t khác nhau (vì ch ng h n n u r1 = r3 thì p | (3a − a) hay p | 2a, Chuyên đ S h c Di n đàn Toán h c
32 3.2. Phương pháp gi i các bài toán chia h t ch có th là p = 2, mà p = 2 thì bài toán không đúng). Do đó r1 r2 · rp−1 = 1 · 2 · 3 · · · (p − 1). Ta có a ≡ r1 (mod p) 2a ≡ r2 (mod p) ··· (p − 1)a ≡ rp−1 (mod p) Nhân v theo v ta suy ra 1·2·3 · · · (p−1)·ap−1 ≡ r1 r2 · · · rp−1 Vì U CLN (a, p) = 1 nên ap ≡ a (mod p). (mod p) ⇒ ap−1 ≡ 1 Như v y v i m i s nguyên a và s nguyên t p thì ap ≡ a (mod p). .v n (mod p) lý còn đư c phát bi u dư i d ng sau: 4 h Nh n xét. Ta có th ch ng minh đ nh lý b ng quy n p. Ngoài ra, đ nh 2 Đ nh lý 3.2– V i m i s nguyên a, p là s nguyên t , U CLN (a, p) = 1 thì ap−1 ≡ 1 (mod p). Phương pháp s o c d ng tính ch t chia h t và áp d ng đ nh lý h Fermat nh toán. u i Cơ s : S d ng các tính ch t chia h t và đ nh lý Fermat nh đ gi i Ví d 3.1. Cho a và b là hai s t nhiên. Ch ng minh r ng 5a2 +15ab− V b2 chia h t cho 49 khi và ch khi 3a + b chia h t cho 7. L i gi i. ⇒) Gi s 49 | 5a2 + 15ab − b2 ⇒ 7 | 5a2 + 15ab − b2 ⇒ 7 | (14a2 + 21ab) − (5a2 + 15ab − b2 ) ⇒ 7 | (9a2 + 6ab + b2 ) ⇒ 7 | (3a + b)2 ⇒ 7 | 3a + b. ⇐) Gi s 7 | 3a + b. Đ t 3a + b = 7c (c ∈ Z. Khi đó b = 7c − 3a. Như v y ⇒ 5a2 + 15ab − b2 = 5a2 + 15a(7c − 3a) − (7c − 3a)2 = 49(c2 + 3ac − a2 ) Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 33 chia h t cho 49. V y 5a2 + 15ab − b2 chia h t cho 49 khi và ch khi 3a + b chia h t cho 7. Ví d 3.2. Cho 11 | (16a + 17b)(17a + 16b) v i a, b là hai s nguyên. Ch ng minh r ng 121 | (16a + 17b)(17a + 16b). L i gi i. Ta có theo đ u bài, vì 11 nguyên t nên ít nh t m t trong hai s 16a + 17b và 17a + 16b chia h t cho 11. Ta l i có (16a + 17b) + (17a + 16b) = 33(a + b) chia h t cho 11. Do đó n u m t trong hai s .v Ví d 3.3. Ch ng minh r ng A = 130 + 230 + · + 1130 không chia h t cho 11. n 16a + 17b và 17a + 16b chia h t cho 11 thì s còn l i cũng chia h t cho 11. Cho nên 121 | (16a + 17b)(17a + 16b). 4 h L i gi i. V i m i a = 1, 2, · · · , 10 thì (a, 10) = 1. Do đó theo đ nh lý Fermat bé thì a10 ≡ 1 (mod 11) ⇒ a30 ≡ 1 (mod 11) v i m i a = 1, 2, · · · , 10 và 1130 ≡ 0 (mod 11). Như v y 10 s 1 c 2 A ≡ 1 + 1 + · · · + 1 +0 (mod 11) ≡ 10 h o(mod 11) ⇒ 11 A i Ví d 3.4. Cho p và q là hai s nguyên t phân bi t. Ch ng minh r ng pq−1 + q p−1 − 1 chia h t cho pq. Do đó V u L i gi i. Vì q nguyên t nên theo đ nh lý Fermat nh thì pq−1 ≡ 1 pq−1 + q p−1 ≡ 1 (mod q) (mod q) Vì q và p có vai trò bình đ ng nên ta cũng d dàng suy ra q p−1 + pq−1 ≡ 1 (mod p). Cu i cùng vì U CLN (q, p) = 1 nên pq−1 + q p−1 ≡ 1 (mod pq) hay pq−1 + q p−1 − 1 chia h t cho pq. Chuyên đ S h c Di n đàn Toán h c
34 3.2. Phương pháp gi i các bài toán chia h t Bài t p đ ngh Bài 1. Ch ng minh r ng 11a+2b chia h t cho 19 khi và ch khi 18a+5b chia h t cho 19 v i a, b là các s nguyên. Bài 2. Ch ng minh r ng 2a + 7 chia h t cho 7 khi và ch khi 3a2 + 10ab − 8b2 . Bài 3. Cho p là s nguyên t l n hơn 5. Ch ng minh r ng n u n là s t nhiên có p − 1 ch s và các ch s đó đ u b ng 1 thì n chia h t cho p. .v n Bài 4. Gi s n ∈ N, n ≥ 2. Xét các s t nhiên an = 11 · 1 đư c vi t b i n ch s 1. Ch ng minh r ng n u an là m t s nguyên t thì n là ư c c a an − 1. 4 h Bài 5. Gi s a và b là các s nguyên dương sao cho 2a − 1, 2b − 1 và a + b đ u là s nguyên t . Ch ng minh r ng ab + ba và aa + bb 2 đ u không chia h t cho a + b. c Bài 6. Ch ng minh r ng v i m i s nguyên t p thì t n t i s nguyên n sao cho 2n + 3n + 6n − 1 chia h t cho p. 3.2.2 Xét s dư h o u i Cơ s : Đ ch ng minh A(n) chia h t cho p, ta xét các s n d ng n = kp + r v i r ∈ {0; 1; 2; · · · ; p − 1}. Ch ng h n, v i p = 5 thì s nguyên n có th vi t l i thành 5k; 5k + 1; 5k + 2; 5k + 3; 5k + 4. Ta th m i d ng này vào các v trí c a n r i V lý lu n ra đáp s . Sau đây là m t s ví d Ví d 3.5. Tìm k ∈ N đ t n t i n ∈ N sao cho 4 | n2 − k v i k ∈ {0; 1; 2; 3}. L i gi i. Gi s t n t i k ∈ N đ t n t i n ∈ N th a mãn 4 | n2 − k. Ta xét các Trư ng h p: (m ∈ N∗ ) Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 35 1. N u n = 4m thì n2 − k = 16m2 − k chia h t cho 4 khi và ch khi 4 | k nên k = 0. 2. N u n = 4m ± 1 thì n2 − k = 16m2 ± 8m + 1 − k chia h t cho 4 khi và ch khi 4 | 1 − k nên k = 1. 3. N u n = 4m ± 2 thì n2 − k = 16m2 ± 16m + 4 − k chia h t cho 4 khi và ch khi 4 | k nên k = 0. n V y k = 0 ho c k = 1. h .v Ví d 3.6. Ch ng minh r ng v i m i n ∈ N thì 6 | n(2n + 7)(7n + 1). L i gi i. Ta th y m t trong hai s n và 7n + 1 là s ch n ∀n ∈ N. Do đó 2 | n(2n + 7)(7n + 1). Ta s ch ng minh 3 | n(2n + 7)(7n + 1). Th t v y, xét 2 1. V i n = 3k thì 3 | n(2n + 7)(7n + 1). 4 n(2n + 7)(7n + 1). o c 2. V i n = 3k + 1 thì 2n + 7 = 6k + 9 chia h t cho 3 nên 3 | i n(2n + 7)(7n + 1). h 3. V i n = 3k + 2 thì 7n + 1 = 21k + 15 chia h t cho 3 nên 3 | N. V u Do đó 3 | n(2n + 7)(7n + 1) mà (2, 3) = 1 nên 6 | n(2n + 7)(7n + 1) ∀n ∈ Ví d 3.7. (HSG 9, Tp H Chí Minh, vòng 2, 1995) Cho x, y, z là các s nguyên th a mãn (x − y)(y − z)(z − x) = x + y + z (3.1) Ch ng minh r ng 27 | (x + y + z). L i gi i. Xét hai trư ng h p sau Chuyên đ S h c Di n đàn Toán h c
36 3.2. Phương pháp gi i các bài toán chia h t 1. N u ba s x, y, z chia h t cho 3 có các s dư khác nhau thì các hi u x−y, y −z, z −x cùng không chia h t cho 3. Mà 3 | (x+y +z) nên t (3.1) suy ra vô lí . 2. N u ba s x, y, z ch có hai s chia cho 3 có cùng s dư thì trong ba hi u x−y, y −z, z −x có m t hi u chia h t cho 3. Mà 3 (x+y +z) nên t (3.1) suy ra vô lí. V y x, y, z chia cho 3 có cùng s dư, khi đó x − y, y − z, z − x đ u chia n h t cho 3. T (3.1) ta suy ra 27 | (x + y + z), ta có đpcm. .v Bài t p đ ngh Bài 1. i) Tìm s t nhiên n đ 7 | (2n − 1). ii) Ch ng minh r ng 7 (2n + 1) ∀n ∈ N. 4 h Bài 2. Ch ng minh r ng v i m i s nguyên a thì a(a6 − 1) chia h t 2 cho 7. Bài 3. Tìm n đ 13 | 32n + 3n + 1. o c Bài 4. Ch ng minh r ng v i m i a, b ∈ N thì ab(a2 − b2 )(4a2 − b2 ) luôn luôn chia h t cho 5. i h Bài 5. Ch ng minh r ng 24 | (p − 1)(p + 1) v i p là s nguyên t l n u hơn 3. Bài 6. Ch ng minh r ng không t n t i s nguyên a đ a2 + 1 chia h t V cho 12. Bài 7. Ch ng minh r ng v i m i s nguyên x, y, z n u 6 | x + y + z thì 6 | x3 + y 3 + z 3 . Bài 8. Cho ab = 20112012 , v i a, b ∈ N. H i t ng a + b có chia h t cho 2012 hay không ? Bài 9. S 3n + 2003 trong đó n là s nguyên dương có chia h t cho 184 không ? Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 37 Bài 10. Cho các s nguyên dương x, y, z th a mãn x2 + y 2 = z 2 . Ch ng minh r ng xyz chia h t cho 60. Bài 11. Cho các s nguyên dương x, y, z th a mãn x2 +y 2 = 2z 2 . Ch ng minh r ng x2 − y 2 chia h t cho 84. Bài 12. Cho n > 3, (n ∈ N). Ch ng minh r ng n u 2n = 10a+b, (0 < b < 9) thì 6 | ab. 3.2.3 Phân tích Phân tích thành tích .v Cơ s : Đ ch ng minh A(n) chia h t cho p, ta phân tích A(n) = D(n)p, n h còn n u trong ta không th đưa ra cách phân tích như v y, ta có th vi t p = kq. 2 4 • N u (k, q) = 1 thì ta ch ng minh A(n) cùng chia h t cho k và q. • N u (k, q) = 1 thì ta vi t A(n) = B(n)C(n) và ch ng minh B(n) chia h t cho k, C(n) chia h t cho q. o c i n h Ví d 3.8. Cho n là m t s nguyên dương. Ch ng minh r ng 2 | (n + 1) (n + 2) · · · (2n) . L i gi i. Ta có V u (n + 1) (n + 2) · · · (2n) = (2n)! n! = (1.3.5...(2n − 1)) (2.4.6...2n) n n! n! = 1.3.5...(2n − 1).2 . n! n = 1.3.5...(2n − 1).2 . Do đó 2n | (n + 1) (n + 2) · · · (2n) . Chuyên đ S h c Di n đàn Toán h c
38 3.2. Phương pháp gi i các bài toán chia h t Ví d 3.9. Ch ng minh r ng v i m i s nguyên n thì 6 | n3 − n. L i gi i. Phân tích n3 − n = n(n2 − 1) = n(n − 1)(n + 1) Bi u th c là tích ba s nguyên liên ti p nên t n t i ít nh t m t trong ba s m t s chia h t cho 2 và m t s chia h t cho 3. Mà (2, 3) = 1 nên 6 | n3 − n. .v n Ví d 3.10. Ch ng minh r ng n6 − n4 − n2 + 1 chia h t cho 128 v i n l . L i gi i. Ta có 4 h n6 − n4 − n2 + 1 = (n2 − 1)2 (n + 1) = (n − 1)2 (n + 1)2 Vì n l nên đ t n = 2k, k ∈ N, suy ra c 2 (n2 − 1)2 = (2k + 1)2 − 1 = (4k 2 + 4k)2 = [4k(k + 1)]2 o V y 64 | (n2 − 1)2 . Vì n l nên 2 | n + 1, suy ra đpcm. h u i Ví d 3.11. Cho ba s nguyên dương khác nhau x, y, z. Ch ng minh r ng (x − y)5 + (y − z)5 + (x − z)5 chia h t cho 5(x − y)(y − z)(x − z). V L i gi i. Ta có (x − y)5 + (y − z)5 + (x − z)5 = (x − z + z − y)5 + (y − z)5 + (z − x)5 = (x − z)5 + 5(x − z)4 (z − y) + 10(x − z)3 (z − y)2 +10(x − z)4 (z − y) + 10(x − z)3 (z − y)2 +10(x − z)2 (z − y)3 + 5(x − z)(z − y)4 = 5(x − z)(z − y)× × (x − z)3 + 2(x − z)2 (z − y) + 2(x − z)(z − y)2 + (z − y)3 . Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 39 Nhưng ta cũng có: (x − z)3 + 2(x − z)2 (z − y) + 2(x − z)(z − y)2 + (z − y)3 = (x − y + y − z)3 + 2(x − y + y − z)2 (z − y) +2(x − y + y − z)(z − y)2 + (z − y)3 = (x − y)3 + 2(x − y)2 (y − z) + 3(x − y)(y − z)2 +(y − z)3 + 2(x − y)2 (z − y) +4(x − y)(y − z)(z − y) + 2(y − z)2 (z − y) +2(x − y)(z − y)2 + 2(y − z)(z − y)2 + (z − y)3 = (x − y)3 + 3(x − y)2 (y − z) + 3(x − y)(y − z)2 n +2(x − y)2 (z − y) + 4(x − y)(y − z)(z − y) + 2(x − y)(z − y)2 , .v Bi u th c cu i cùng có nhân t chung (x − y). Ta suy ra đi u ph i h ch ng minh. Bài t p đ ngh 2 4 Bài 1. Ch ng minh r ng n u a, k là các s nguyên, a l thì 2k+1 | k c (a2 − 1). o Bài 2. Ch ng minh r ng n5 − n chia h t cho 30 v i m i n ∈ Z. h Bài 3. Ch ng minh r ng 3n4 − 14n3 + 21n2 − 10n chia h t cho 24 v i i m i n ∈ Z. u Bài 4. Ch ng minh r ng n5 − 5n3 + 4n chia h t cho 120 v i m i n ∈ Z. Bài 5. Ch ng minh r ng n3 − 3n2 − n + 3 chia h t cho 48 v i m i n V l , n ∈ Z. Bài 6. Ch ng minh r ng n8 − n6 − n4 + n2 chia h t cho 1152 v i m i s nguyên n l . Bài 7. Ch ng minh r ng n4 − 4n3 − 4n2 + 16n chia h t cho 348 v i m i n là s nguyên ch n. Bài 8. Ch ng minh r ng n4 − 14n3 + 71n2 − 154n + 120 chia h t cho 24 v i m i s t nhiên n. Chuyên đ S h c Di n đàn Toán h c
40 3.2. Phương pháp gi i các bài toán chia h t Bài 9. Cho x, y, z là các s nguyên khác 0. Ch ng minh r ng n u x2 − yz = a, y 2 − zx = b, z 2 − xy = c thì t ng (ax + by + cz) chia h t cho t ng (a + b + c). Bài 10. Cho m, n là hai s chính phương l liên ti p. Ch ng minh r ng mn − m − n + 1 chia h t cho 192. Bài 11. (HSG 9 TQ 1970) Ch ng minh r ng n12 − n8 − n4 + 1 chia h t cho 512 v i m i s t nhiên n l . Bài 12. (HSG 9 TQ 1975) Ch ng minh r ng n4 + 6n3 + 11n2 + 6n chia h t cho 24 v i m i s nguyên dương n. Tách t ng .v n 4 h Cơ s : Đ ch ng minh A(n) chia h t cho p, ta bi n đ i A(n) thành t ng nhi u h ng t r i ch ng minh m i h ng t đ u chia h t cho p. như: c 2 Ta có th s d ng m t s h ng đ ng th c áp d ng vào chia h t, ví d o Cho a, b là các s th c và n là s nguyên dương. Khi đó ta có i h an − bn = (a − b)(an−1 + an−2 b + · · · + abn−2 + bn−1 ) Ta s có h qu là: u H qu 3.2– N u a − b = 0 thì an − bn chia h t cho a − b. V H qu 3.3– N u a + b = 0 và n l thì an + bn chia h t cho a + b. H qu 3.4– N u a + b = 0 và n ch n thì an − bn chia h t cho a + b Ví d 3.12. Ch ng minh r ng ax2 + bx + c ∈ Z, ∀x ∈ Z khi và ch khi 2a, a + b, c ∈ Z Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 41 L i gi i. Phân tích ax2 + bx + c = ax2 − ax + (a + b)x + c x(x − 1) = 2a. + (a + b)x + c ∈ Z, ∀x ∈ Z. 2 Ví d 3.13. Ch ng minh r ng 6 | (a3 + 5a) ∀a ∈ N. (ch ng minh ví d Equation 4.27). .v n L i gi i. Phân tích a3 +5a = (a3 −a)+6a. Hi n nhiên đúng vì 6 | n3 −n Nh n xét. T ví d Equation 4.27 ta cũng có th đưa ra các bài toán 4 h sau, ch ng minh cũng b ng cách v n d ng phương pháp tách t ng: Bài toán 3.1. Cho m, n ∈ Z. Ch ng minh r ng 6 | m2 n2 (m − n). và ch khi 6 | (a + b + c) c 2 Bài toán 3.2. Cho a, b, c ∈ Z. Ch ng minh r ng 6 | (a3 + b3 + c3 ) khi h o Bài toán 3.3. Cho a ∈ Z. Ch ng minh r ng a a2 a3 3 + 2 + 6 ∈Z u i Bài toán 3.4. Vi t s 20112012 thành t ng các s nguyên dương. Đem t ng l p phương t t c các s h ng đó chia cho 3 thì đư c dư là bao nhiêu ? V Ví d 3.14. Cho m, n là các s nguyên th a mãn: m 1 1 1 1 1 = 1 − + − + ··· − + n 2 3 4 1334 1335 Ch ng minh r ng 2003 | m. Chuyên đ S h c Di n đàn Toán h c
42 3.2. Phương pháp gi i các bài toán chia h t L i gi i. Đ ý r ng 2003 là s nguyên t . Ta có m 1 1 1 1 1 = 1− + − + ··· − + n 2 3 4 1334 1335 1 1 1 1 1 1 1 = 1 + + + ··· + −2 + + + ··· + 2 3 1335 2 4 6 1334 1 1 1 1 1 1 = 1 + + + ··· + − 1 + + + ··· + 2 3 1335 2 3 667 1 1 1 = + + ··· + 668 669 1335 = = 1 + 668 1335 2003 p 1 1 + + 1 + 669 1334 1 668.1335 669.1334 1 + ··· + + ··· + 1 1 + 1 1001 1002 1001.1002 .v n = 2003. q 4 h đây p là s nguyên còn q = 668 · 669 · · · 1335. Vì 2003 nguyên t nên (q, 2003) = 1. Do đó t (∗) suy ra 2003pn = mq. c 2 Vì p, n nguyên nên suy ra 2003|mq mà (q, 2003) = 1 nên 2003|m. h o Ví d 3.15. Ch ng minh r ng v i m i s t nhiên n thì A = 2005n + u i 60n − 1897n − 168n chia h t cho 2004. L i gi i. Ta có 2004 = 12 × 167. Vì (12, 167) = 1 nên đ ch ng minh A chia h t cho 2004 ta ch ng minh A chia h t cho 12 và 167. V Áp d ng tính ch t an − bn chia h t cho a − b v i m i n t nhiên và a − b = 0 suy ra 2005n − 1897n chia h t cho 2005 − 1897 = 108 = 12 × 9, hay 2005n − 1897n chia h t cho 12. Tương t thì 168n − 60n chia h t cho 12. V y A chia h t cho 12. Ti p t c phân tích A = (2005n − 168n ) − (1897n − 60n ). L p lu n tương t như trên thì 2005n − 168n và 1897n − 60n chia h t cho 167, t c A chia h t cho 167. V y ta có đi u ph i ch ng minh. Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 43 Ví d 3.16. (Đ thi tuy n sinh ĐHKHTN-ĐHQG Hà N i, vòng 1, năm 2007-2008) Cho a, b là hai s nguyên dương và a + 1, b + 2007 đ u chia h t cho 6. Ch ng minh r ng 4a + a + b chia h t cho 6. L i gi i. Phân tích 4a + a + b = (4a + 2) + (a + 1) + (b + 2007) − 2010 4a + 2 = 4a − 1 + 3 = (4 − 1)(4a−1 + · · · 1) + 3 chia h t cho 6 nên 4a + a + b chia h t cho 6. .v n Như v y 3 | 4a + 2. Do đó 4a + a + b là t ng c a các s nguyên dương h Bài t p đ ngh 4 Bài 1. Đưa ra các m r ng t bài t p đ ngh c a phương pháp phân tích thành tích thành các bài toán v n d ng phương pháp tách c 2 t ng (gi ng như cách m r ng c a ví d 1.9). Bài 2. (Hungary MO 1947) Ch ng minh r ng 46n + 296.13n chia h t o cho 1947 v i m i s t nhiên n l . Bài 3. Ch ng minh r ng 20n + 16n − 3n − 1 chia h t cho 323 v i m i i s t nhiên n ch n. h2903n − 803n − 464n + 261n u Bài 4. Ch ng minh r ng chia h t cho 1897 v i m i s t nhiên n. V Bài 5. Ch ng minh r ng v i m i s nguyên n > 1 ta có nn + 5n2 − 11n + 5 chia h t cho (n − 1)2 . Bài 6. (HSG 9 Tp Hà N i, vòng 2, 1998) Ch ng minh r ng 1997 | m v i m, n ∈ N th a mãn m 1 1 1 1 1 1 = 1 − + − + ··· + − + . n 2 3 4 1329 1330 1331 Bài 7. Ch ng minh r ng 32n+1 + 2n+2 chia h t cho 7 v i m i n ∈ N. Chuyên đ S h c Di n đàn Toán h c
44 3.2. Phương pháp gi i các bài toán chia h t Bài 8. Ch ng minh r ng 20032005 + 20172015 chia h t cho 12. Bài 9. Cho p là s t nhiên l và các s nguyên a, b, c, d, e th a mãn a + b + c + d + e và a2 + b2 + c2 + d2 + e2 đ u chia h t cho p. Ch ng minh r ng s a5 + b5 + c5 + d5 + e5 − 5abcde cũng chia h t cho p. Bài 10. (Canada Training for IMO 1987) Kí hi u: 1 · 3 · 5 · · · (2n − 1) = (2n − 1)!! 2 · 4 · 6 · · · (2n) = (2n)!!. Ch ng minh r ng (1985)!! + (1986)!! chia h t cho 1987. Bài 11. Ch ng minh r ng s 22225555 + 55552222 chia h t cho 7. .v n t và 1 + 1 + ··· + 1 = 4 m h Bài 12. Cho k là s nguyên dương sao cho s p = 3k + 1 là s nguyên 1·2 3·4 c 2 (2k − 1)2k n v i hai s nguyên dương nguyên t cùng nhau m và n.Ch ng minh m chia h t cho p. 3.2.4 Xét đ ng dư h o (T p chí Mathematics Reflections, đăng b i T.Andreescu) u i Đ nh nghĩa và m t s tính ch t Đ nh nghĩa 3.2 Cho a, b là các s nguyên và n là s nguyên dương. Ta nói, a đ ng dư v i b theo modun n và kí hi u a ≡ b (mod n) n u a và V b có cùng s dư khi chia cho n. Như v y a ≡ n (mod n) ⇐⇒ n | (a − b). Ví d : 2012 ≡ 2 (mod 5). Tính ch t (b n đ c t ch ng minh) Cho a, b, c, d, n là các s nguyên. a ≡ a (mod n), Tính ch t 3.10– a ≡ b (mod n) ⇔ b ≡ a (mod n), a ≡ b (mod n), b ≡ c (mod n) ⇒ a ≡ c (mod n). Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 45 a ≡ b (mod n) a ± c ≡ b ± d (mod n) Tính ch t 3.11– ⇒ c ≡ d (mod n) ac ≡ bd (mod n) Tính ch t 3.12– a ≡ b (mod n) ⇒ ak ≡ bk (mod n), ∀k ≥ 1. Tính ch t 3.13– a ≡ b (mod n) ⇒ ac ≡ bc (mod mc), c > 0 Tính ch t 3.14– (a + b)n ≡ bn (mod a), (a > 0). Tính ch t 3.15– N u d là ư c chung dương c a a, b và m thì a ≡ b a d b (mod m) thì ≡ (mod ). d m d .v n Tính ch t 3.16– a ≡ b (mod m), c là ư c chung c a a và b, (c, m) = 1 h a b thì ≡ (mod m). c c 2 4 Phương pháp đ ng dư th c đ gi i các bài toán chia h t chia h t. o c Cơ s : S d ng các tính ch t và đ nh nghĩa trên đ gi i các bài toán i h Ví d 3.17. Ch ng minh r ng v i m i s t nhiên n thì 7 | 8n + 6. u L i gi i. Ta có 8n ≡ 1 (mod 7) =⇒ 8n + 6 ≡ 7 ≡ 0 (mod 7). dương n. V Ví d 3.18. Ch ng minh r ng 19 | 7 · 52n + 12 · 6n . v i m i s nguyên L i gi i. Ta có 52 = 25 ≡ 6 (mod 19) =⇒ (52 )n ≡ 6n (mod 19) =⇒ 7 · 52n ≡ 7 · 6n (mod 19) =⇒ 7 · 52n + 12 · 6n ≡ 19 · 6n ≡ 0 (mod 19). Ví d 3.19. Vi t liên ti p các s 111, 112, · · · , 888 đ đư c s A = 111112 · · · 888. Ch ng minh r ng 1998 | A. Chuyên đ S h c Di n đàn Toán h c
46 3.2. Phương pháp gi i các bài toán chia h t L i gi i. Ta th y A ch n nên 2 | A. M t khác A = 111 · 1000777 + 112 · 1000776 + · · · + 888. Do 1000k ≡ 1 (mod 999), ∀k ∈ N nên A ≡ 111 + 112 + · · · + 888 ≡ 0 (mod 999). Suy ra 999 | A, và (999, 2) = 1 nên 1998 | A. Ví d 3.20. Ch ng minh r ng 7 | 55552222 + 22225555 . L i gi i. Ta có .v n 2222 ≡ −4 (mod 7) =⇒ 22225555 ≡ (−4)5555 (mod 7) 5555 ≡ 4 (mod 7) =⇒ 55552222 ≡ 4 (mod 7) 4 h L i có =⇒ 5555 2222 + 2222 5555 ≡ −4 c 2 5555 −45555 + 42222 = −42222 43333 − 1 +4 2222 (mod 7) h o = −42222 641111 − 1 i Và 64 ≡ 1 (mod 7) =⇒ 641111 − 1 ≡ 0 (mod 7). Do đó 7 | 55552222 + 22225555 Bài t p đ ngh V u Bài 1. M t s bài t p phương pháp phân tích có th gi i b ng phương pháp đ ng dư th c. 777 333 Bài 2. Ch ng minh r ng 333555 + 777555 chia h t cho 10. 1967 Bài 3. Ch ng minh r ng s 1110 − 1 chia h t cho 101968 . Bài 4. Cho 9 | a3 + b3 + c3 , ∀a, b, c ∈ Z. Ch ng minh r ng 3 | a · b · c. Bài 5. Ch ng minh r ng 222333 + 333222 chia h t cho 13. Di n đàn Toán h c Chuyên đ S h c
3.2. Phương pháp gi i các bài toán chia h t 47 Bài 6. Ch ng minh r ng 9n + 1 không chia h t cho 100, ∀n ∈ N. Bài 7. Ch ng minh r ng v i m i s nguyên không âm n thì 25n+3 + 5n · 3n+1 chia h t cho 17. Bài 8. Tìm n ∈ N sao cho 2n3 + 3n = 19851986. Bài 9. Vi t liên ti p 2000 s 1999 ta đư c s X = 19991999 · · · 1999. Tìm s dư trong phép chia X cho 10001. 7 n 77 7 Bài 10. Ch ng minh r ng 100 | 77 − 77 . .v Bài 11. Cho b2 − 4ac và b2 + 4ac là hai s chính phương v i a, b, c ∈ N. Ch ng minh r ng 30 | abc. 3.2.5 Quy n p 4 h Cơ s : Đ ch ng minh m nh đ đúng v i m i s t nhiên n ≥ p, ta 2 làm như sau: c • Ki m tra m nh đ đúng v i n = p. • Gi s m nh đ đúng v i n = k. Ta đi ch ng minh m nh đ cũng đúng v i n = k + 1. h o n ∈ N∗ . u i Ví d 3.21. Ch ng minh r ng A = 4n + 15 − 1 chia h t cho 9 v i m i L i gi i. V i n = 1 =⇒ A = 18 chia h t cho 9. V Gi s bài toán đúng v i n = k. Khi đó 9 | 4k +15k −1, hay 4k +15k −1 = 9q v i q ∈ N∗ . Suy ra 4k = 9q − 15k + 1. Ta đi ch ng minh bài toán đúng v i n = k+1, t c 9 | 4k+1 +15(k+1)−1. Th t v y: 4k+1 + 15(k + 1) − 1 = 4 · 4k + 15k + 14 = 4 (9q − 15k + 1) + 15k + 14 = 36q − 45k + 18 chia h t cho 9. Ta có đpcm. Chuyên đ S h c Di n đàn Toán h c
48 3.2. Phương pháp gi i các bài toán chia h t Ví d 3.22. (HSG 9 TQ 1978)Ch ng minh r ng s đư c t o b i 3n ch s gi ng nhau thì chia h t cho 3n v i 1 ≤ n, n ∈ N. L i gi i. V i n = 1, bài toán hi n nhiên đúng. Gi s bài toán đúng v i n = k, t c 3k | aa · · · a. 3n s a V i n = k + 1 ta có: aa · · · a = aa · · · a aa · · · a aa · · · a 3k+1 3k 3k 3k 3k −1 3k = aa · · · a × 1 00 · · · 0 00 · · · 0 1 3k −1 .v n chia h t cho 3k+1 . Ta có đpcm. 4 h c 2 Ví d 3.23. Ch ng minh r ng v i m i n ∈ N∗ , k là s t nhiên l thì o n 2n+2 | k 2 − 1 h n L i gi i. V i n = 1 thì k 2 − 1 = k 2 − 1 = (k + 1)(k − 1). Do k l ,nên h t cho 23 = 8. u i đ t k = 2m + 1 v i m ∈ N∗ , thì khi đó (k + 1)(k − 1) = 4k(k + 1) chia p p Gi s bài toán đúng v i n = p, t c 2p+2 | k 2 − 1 hay k 2 = q · 2p+2 + 1 v i q ∈ N∗ . V Ta ch ng minh bài toán đúng v i n = p + 1. Th t v y A = k2 = k =q·2 p+1 2p p+2 −1 k 2p · 2 + q · 2p+2 p − 1 = k 2·2 − 1 = k 2 +1 p 2 −1 = q · 2p+3 · 1 + q · 2p+1 chia h t cho 2p+3 . Ta có đpcm. Di n đàn Toán h c Chuyên đ S h c