1 2 Mục lục Nguyễn Tất Thu Chương 1 Các nguyên lí 1.1 Nguyên lí cực hạn Nguyên lí cực hạn được phát biều đơn giản như sau: Nguyên lí 1: Trong một tập hữu hạn và khác rỗng các số thực luôn luôn có thể chọn được số bé nhất và số lớn nhất. Nguyên lí 2: Trong một tập khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất. Ví dụ 1.1. Chứng minh rằng p 2 là số vô tỉ. Lời giải. Giả sử p 2 là số hữu tỉ. Khi đó, tồn tại các số nguyên dương a,b sao cho p 2 = a b . Xét tập hợp A = {n p 2|n và n p 2 là các số nguyên dương}. Ta có A 6= ∅ vì a = b p 2 ∈ A. Gọi n0 là phần tử nhỏ nhất trong A, khi đó tồn tại số nguyên dương k để n0 = p 2k. Xét n0( p 2−1) = n0 p 2− n0 = (n0 − k) p 2. Vì n0( p 2−1) = 2k − n0 và n0 − k là các số nguyên dương nên n0( p 2−1) ∈ A và n0( p 2−1) < n0. Điều này rái với việc giả sử n0 là phần tử nhỏ nhất thuộc A. Vậy p 2 là số vô tỉ. Ví dụ 1.2. Chứng minh rằng phương trình x 6 +4y 6 = 2z 6 (1) không có nghiệm nguyên dương. Lời giải. Giả sử phương trình (1) có nghiệm nguyên dương. Xét (x0; y0; z0) là nghiệm của (1) sao cho x0 nhỏ nhất. 4 Chương 1. Các nguyên lí Ta có x 6 0 . . .2 nên x0 chẵn, hay x0 = 2x1. Khi đó 64x 6 1 +4y 6 0 = 2z 6 0 Hay 32x 6 1 +2y 6 0 = z 6 0 Tương tự, suy ra z0 = 2z1, y0 = 2y1 với x1, y1, z1 thỏa mãn x 6 1 +4y 6 1 = 2z 6 1 . Hay (x1; y1; z1) cũng là một nghiệm của (1) nhưng x1 < x0. Điều này trái với việc giả sử x0 nhỏ nhất. Vậy bài toán được chứng minh. Ví dụ 1.3. Cho x, y là hai số nguyên dương thỏa x 2 + y 2 +1 x y ∈ Z. Chứng minh rằng: x 2 + y 2 +1 x y = 3. Lời giải. Xét tập S = ½ (x; y) ∈ NxN| x 2 + y 2 +1 x y = k ∈ Z ¾ ta có: S 6= ∅. Gọi (a;b) ∈ S sao cho a+ b nhỏ nhất. Không mất tính tổng quát, ta giả sử a > b. Nếu a > b. Ta cố định b, khi đó a là nghiệm của phương trình t 2 − kbt+ b 2 +1 = 0. Phương trình này có thêm nghiệm nữa là a 0 ∈ N ⇒ ¡ a 0 ;b ¢ ∈ S Theo Viét, ta có: ( a+ a 0 = kb a.a 0 = b 2 +1 ⇒ a 0 = k y− a = b 2 +1 a Vì a > b > 1 ⇒ b 6 a−1 ⇒ a 0 = b 2 +1 a 6 (a−1) 2 +1 a = a−2+ 2 a < a suy ra a 0 + b < a+ b vô lí. Do vậy ta có: a = b, suy ra k = 2a 2 +1 a 2 = 2+ 1 a 2 ∈ Z ⇒ ( a = 1 k = 3 . Ví dụ 1.4. Chứng minh rằng không tồn tại số nguyên dương n > 1 lẻ để 15n +1 chia hết cho n. Nguyễn Tất Thu 1.2. Nguyên lí quy nạp 5 Lời giải. Giả sử tồn tại số nguyên dương lẻ n > 1 thỏa n là ước của 15n +1. Gọi p là ước nguyên tố nhỏ nhất của n, khi đó p lẻ và là ước của 15n +1. Suy ra 152n −1 = (15n −1)(15n +1). . .p. Gọi k là số nguyên dương nhỏ nhất thỏa mãn 15k −1 . . .p. Theo định lí Fecma, ta có 15p−1 −1 . . .p. Do đó k là ước của 2n và p −1, hay k|(p −1,2n). Vì p là ước nguyên tố nhỏ nhất của n nên (p −1,n) = 1, suy ra (p −1;2n) = 2. Từ đó ta có k = 1 hoặc k = 2. • k = 1 ta có 151−1 = 14 nên p = 7, khi đó 15n+1 ≡ 2 (mod 7).. Điều này dẫn tới mâu thuẫn. • k = 2 ta có 152 −1 = 224 nên p = 7. Theo trên ta có điều vô lí, Vậy bài toán đượcc chứng minh. Bài tập 1.1. Chứng minh rằng với hai số nguyên dương a,b nguyên tố cũng nhau, luôn tồn tại hai số nguyên x, y sao cho ax+ b y = 1. Bài tập 1.2. Tìm nghiệm nguyên của phương trình x 3 +2y 3 = 4z 3 . Bài tập 1.3. Chứng minh rằng phương trình x 2 + y 2 = 3z 2 chỉ có duy nhất nghiệm tự nhiên x = y = z = 0. Bài tập 1.4. Chứng minh rằng phương trình x 3 +3y 3 = 9z 3 không có nghiệm nguyên dương. Bài tập 1.5. (IMO 1988) Cho a, b là các số nguyên dương sao cho ab +1là ước của a 2 + b 2 . Chứng minh rằng a 2 + b 2 ab +1 là số chính phương. Bài tập 1.6. Cho a,b là hai số tự nhiên lẻ thỏa mãn a là ước của b 2+2 và b là ước của a 2+2. Chứng minh rằng a 2 + b 2 +2 ab là một số chính phương. 1.2 Nguyên lí quy nạp 1.2.1 Nguyên lí quy nạp Nếu T(n) với n là số tự nhiên thỏa mãn hai điều kiện sau: i) Đúng với n = n0 ii) Từ sự đúng đắn của T(n) với n = k (hoặc n0 6 n 6 k) suy ra được tính đúng đắn của T(n) với n = k +1 thì T(n) đúng với mọi số tự nhiên n > n0. Nguyễn Tất Thu 6 Chương 1. Các nguyên lí 1.2.2 Phương pháp chứng minh bằng quy nạp Nếu T(n) với n là số tự nhiên thỏa mãn hai điều kiện sau: i) Đúng với n = n0 ii) Từ sự đúng đắn của T(n) với n = k (hoặc n0 6 n 6 k) suy ra được tính đúng đắn của T(n) với n = k +1 thì T(n) đúng với mọi số tự nhiên n > n0. Để chứng minh T(n) có tính chất P với mọi số tự nhiên n > n0 bằng phương pháp quy nạp, ta tiến hành theo hai bước sau: Bước 1: Chứng minh T(n0) có tính chất P Bước 2: Giả sử T(n) có tính chất P với n = k > n0 (hoặc n0 6 n 6 k), ta chứng minh T(k+1) cũng có tính chất P. Khi đó T(n) có tính chất P với mọi n > n0. Ví dụ 1.5. Chứng minh rằng với mỗi số tự nhiên n thì 3 3n+3 −26n−27 luôn chia hết cho 169. Lời giải. Với n = 0, ta có P(n) = 3 3n+3 −26n−27 = 0 nên P(0). . .169. Giải sử P(n) . . .169, khi đó P(n+1) = 3 3n+6 −26(n+1)−27 = 27P(n)+262 (n+1). Do P(n) và 262 đều chia hết cho 169 nên P(n+1). . .169. Theo nguyên lí quy nạp ta có đpcm. Ví dụ 1.6. Chứng minh rằng với mọi số nguyên n > 2, sẽ tồn tại các số nguyên dương a1,a2,...,an sao cho aj + ai chia hết cho aj − ai với 1 6 i < j 6 n. Lời giải. Ta sẽ chứng minh bài toán bằng phương pháp quy nạp toán học với n số. Với n = 2, ta chọn a1 = 1 và a2 = 2. Ta giả sử có thể tìm được các số nguyên a1,a2,••• ,an sao cho aj + ai chia hết cho aj − ai với 1 6 i < j 6 n, n là số nguyên dương lớn hơn 1. Gọi m là bội chung nhỏ nhất của các số a1,a2,••• ,an,aj − ai với 1 6 i < j 6 n. Khi đó, ta chọn n+1 số nguyên dương sau a1 = m,a2 = m+ a1,a3 = m+ a2,••• ,an+1 = an + m. Ta chứng minh dãy trên thoả mãn điều kiện của đề bài. Thật vậy, ta có m chia hết cho a 0 i − a 0 1 = ai−1 và a 0 i + a 0 1 = 2m+ ai−1 vì sự xác định m và m chia hết cho a 0 j − a 0 i = aj−1 − ai−1 (2 6 i < j 6 n+1). Nên, a 0 j + a 0 i = 2m+(aj−1 + ai−1) vì sự xác định m và giả thiết quy nạp. Vậy bài toán được chứng minh. Nguyễn Tất Thu 1.2. Nguyên lí quy nạp 7 Ví dụ 1.7. (USA MO 1978 Một số nguyên dương n được gọi là "tốt" nếu ta có thể phân tích n = a1 + a2 +••• + ak với a1,a2,••• ,ak là các số nguyên dương thỏa mãn 1 a1 + 1 a2 +••• + 1 ak = 1. Chứng minh rằng nếu các số nguyên dương từ 33 đến 73 là số "tốt" thì mọi số nguyên dương n > 33 đều là số "tốt". Lời giải. Trước hết, ta chứng minh: Nếu n là số "tốt" thì 2n+8 và 2n+9 cũng là số "tốt". Thật vậy n = a1 + a2 +••• + ak nên 2n+8 = 2a1 +2a2 +••• +2ak +4+4 và 2n+9 = 2a1 +2a2 +••• +2ak +3+6. Mà 1 a1 + 1 a2 +••• + 1 ak = 1 nên 1 2a1 + 1 2a2 +••• + 1 2ak + 1 4 + 1 4 = 1 và 1 2a1 + 1 2a2 +••• + 1 2ak + 1 3 + 1 6 = 1. Từ đó, suy ra 2n+8 và 2n+9 là số "tốt". Băng quy nạp, ta chứng minh: nếu n > 74 thì n là số "tốt". Thật vậy: Do 33 là số "tốt" nên ta có 2.33+8 = 74 và 2.33+9 = 75 là các số "tốt". Giả sử 33,34,••• ,n là số "tốt" với n > 75. • Nếu n = 2k thì n+1 = 2k+1 = (2k−8)+9. Do 2k−8 < n nên 2k−8 là số "tôt", do đó (2k−8)+9 là số "tôt". • Nếu n = 2k +1 thì n+1 = (2k −6)+8. Do 2k −6 là số "tốt" nên 2k −6+8 cũng là số "tốt". Do vậy, ta có n+1 là số "tốt". Theo nguyên lí quy nạp ta có đpcm. Bài tập 1.7. Chứng minh rằng với mỗi số nguyên dương n thì 1. 4.3 2n+2 +32n–36 . . .64 2. 7 n +3n−1 . . .9 3. 11n+2 +122n+1 . . .133 4. 5 2n−1 .2 n +3 n+1 .2 2n−2 . . .19. Nguyễn Tất Thu 8 Chương 1. Các nguyên lí Bài tập 1.8. Chứng minh rằng với mọi số nguyên n > 3, tồn tại các số nguyên dương lẻ x, y sao cho 7x 2 + y 2 = 2 n . Bài tập 1.9. Cho a(n) = 1 3 +2 3 +••• + n 3 với n là số nguyên dương. Chứng minh rằng với mỗi số nguyên dương n thì 4a(n) là tích của hai số chính phương liên tiếp. Bài tập 1.10. Cho k là số nguyên dương lẻ. Chứng minh rằng với mỗi số nguyên dương n thì k 2 n −1 . . .2 n+2 Bài tập 1.11. Chứng minh rằng ³ 1+ p 2 ´2n + ³ 1− p 2 ´2n là số nguyên chẵn và ³ 1+ p 2 ´2n − ³ 1− p 2 ´2n = a p 2 trong đó a là số nguyên dương với mọi n > 1. Bài tập 1.12. Chứng minh rằng từ n + 1 số bất kì trong 2n số tự nhiên đầu tiên luôn tìm được hai số là bội của nhau. 1.3 Nguyên lí Dirichle Nguyên lí Dirichle được phát biểu như sau: Nếu nhốt n+1 con thỏ vào n cái chuồng thì có ít nhất một chuồng chứa 2 con thỏ. Ta có nguyên lí Dirichle mở rộng như sau: Nếu nhốt n con thỏ vào m chuồng (m 6 n) thì có một chuồng chứa ít nhất • n+ m−1 m ¸ con. Ví dụ 1.8. Chứng minh rằng từ 20 số được chọn từ tập X = {1,4,7,••• ,100} ta luôn tìm được hai số có tổng bằng 104. Lời giải. Xét các tập {1}, {52}, {4,100}, {7,97},••• ,{49,55}. có tất cả 18 tập. Vì lấy từ X 20 số nên có ít nhất một cặp được chọn và cặp số đó có tổng bằng 104. Ví dụ 1.9. Cho n > 1 là số nguyên và A là tập hợp gồm n số nguyên dương. Chứng minh rằng tồn tại một tập con B của A sao cho P x∈B x . . .n. Nguyễn Tất Thu 1.3. Nguyên lí Dirichle 9 Lời giải. Giả sử A = {a1,a2,••• ,an}. Xét các số s0 = a1, s1 = a2, s2 = a1 + a2, s3 = a1 + a2 + a3,••• , sn = a1 + a2 +••• + an. Trong dãy trên có n+1 số, do đó sẽ tồn tại ít nhất hai số si và s j (i > j)sao cho si − s)j . . .n. Hay aj+1 +••• + ai . . .n. Vậy tập B = {aj+1,••• ,ai} thỏa yêu cầu bài toán. Ví dụ 1.10. Chứng minh rằng từ 7 số nguyên dương bất kì không vượt quá 126, ta luôn tìm được hai số a,b sao cho a < b 6 2a. Lời giải. Chia tập {1,2,••• ,126} thành 6 tập {1;2}, {3;4;5;6}, {7;8;9;10;11;12;13;14},•••, {63;64;••• ;126}. Vì có 7 số nên sẽ tồn tại hai số a,b cũng thuộc vào một trong 6 tập trên. Rõ ràng hai số đó thỏa mãn a < b 6 2a. Vậy bài toán được chứng minh. Ví dụ 1.11. Trên bàn cờ 10 × 10 người ta viết các số từ 1 đến 100. Mỗi hàng chọn ra số lớn thứ ba. Chứng minh rằng tồn tại một hàng có tổng các số trong hàng đó nhỏ hơn tổng các chữ số lớn thứ ba được chọn. Lời giải. Kí hiệu các số lớn thứ ba là a9 < a8 < ... < a0. Khi đó số phần tử lớn hơn a0 nhiều nhất là 20 (nhiều nhất là 2 phần tử ở mỗi hàng). Suy ra a0 > 80 (1). Tương tự a1 > 78 (2). Mặt khác a8 > a9 +1, a7 > a9 +2,...,a2 > a9 +7. Kết hợp với (1) và (2) suy ra: a0 + a1 +...+ a9 > 80+78+(a9 +1)+...+(a9 +7) = 8a9 +180. Xét hàng chứa a9. Tổng các số của dòng chứa a9 là S(a9) 6 100+99+ a9 + a9 −1+...+ a9 −7 = 8a9 +171 < 8a9 +180 6 a0 + a1 +...+ a9 (đpcm). Ví dụ 1.12. Cho tập S = {1,2,...,999} và A là một tập con bất kì của S mà |A| = 835. Chứng minh rằng luôn tồn tại 4 phần tử a,b, c,d thuộc A sao cho: a+2b +3c = d. Nguyễn Tất Thu Lời giải. Đặt A = {a1,a2,...,a835} với a1 < a2 < ... < a835. Xét hiệu d = a835 −3a1 = 3(a835 − a1)−2a835 > 3.834−2.999 = 504 Do đó 166 cặp số sau là phân biệt (d −2;1), (d −4;2),..., (d −2.165;165),(d −2.166;166). Vì có 164 phần tử S không thuộc tập A, nên trong các cặp trên tồn tại ít nhất một cặp (x; y) với y 6= a1 mà x, y ∈ A, giả sử cặp đó là (d −2k;k) với k ∈ {1,2,...,166} . Khi đó ta có ngay: x+2y+3a1 = a835, suy ra đpcm. Bài tập 1.13. Chứng minh rằng tồn tại một số tự nhiên gồm toàn số 1 và chia hết cho 2013. Bài tập 1.14. Cho 5 số nguyên phân biệt a1,a2,a3,a4,a5. Đặt P = (a1 − a2)(a1 − a3)(a1 − a4)(a1 − a5)(a2 − a3)(a2 − a4)(a2 − a5)(a3 − a4)(a3 − a5)(a4 − a5). Chứng minh rằng P . . .288. Bài tập 1.15. Cho 69 số nguyên dương phân biệt không vượt quá 100. CMR có thể chọn được 4 số a, b, c, d sao cho a < b < c và a+ b + c = d. Bài tập 1.16. Cho A là một tập con của tập các số tự nhiên dương. Biết rằng trong 2013 số tự nhiên liên tiếp bất kì luôn tồn tại một số thuộc A. Chứng minh rằng trong A luôn tồn tại hai số sao cho số này chia hết cho số kia. Bài tập 1.17. Chứng minh rằng trong 39 số tự nhiên liên tiếp bất kì luôn có ít nhất một số có tổng các chữ số chia hết cho 11. Bài tập 1.18. Xét 2002 số nguyên dương phân biệt sao cho không có số nào có ước số nguyên tố lớn hơn 23. Chứng minh rằng ta có thể tìm được bốn số phân biệt sao cho tích của chúng là lũy thừa bậc bốn của một số tự nhiên. Chương 2 Lý thuyết chia hết 2.1 Chia hết 2.1.1 Định nghĩa Định nghĩa 2.1. Cho a 6= 0 và b là hai số nguyên. Ta nói a chia hết cho b hoặc b chia hết a nếu tồn tại số nguyên c sao cho a = b.c. Ta kí hiệu a . . .b hoặc b|a. Ta nói b là ước của a và a được gọi là bội của b. 2.1.2 Tính chất Định lí 2.1. Cho a,b, c là các số nguyên. Khi đó, ta có các tính chất sau: +) Nếu a|b, b 6= 0 thì |a| 6 |b| +) Nếu a|b và a|cthì a|mb + nc với mọi số nguyên m và n. +) Nếu a|b và a|b ± c thì a|c +) a|a (tính phản xạ) +) Nếu a|b và b|cthì a|c(tính bắc cầu) +) Nếu a|b và b|a thì |a| = |b|. Chứng minh. Các tính chất trên chứng minh tương đối đơn giản. Sau đây ta chỉ chứng minh một tính chất là tính chất thứ nhất. Ta có a|b nên tồn tại số nguyên c sao cho b = ac. Do đó |b| = |ac| = |a|.|c|. Vì c là số nguyên và b 6= 0 nên |c| > 1. Suy ra |b| > |c|. 2.1.3 Thuật toán chia hết Định lí 2.2. Cho hai số nguyên dương a,b. Khi đó, tồn tại duy nhất cặp số tự nhiên (q; r) sao cho a = bq + r, 0 6 r 6 b −1. 12 Chương 2. Lý thuyết chia hết Số q được gọi là thương và r được gọi là số dư trong phép chia a cho b. Nếu r = 0 thì a chia hết cho b. Chứng minh. Đặt q = ha b i , ta có a b −1 6 q < a b . Đặt r = a− bq ta có 0 6 r < b và a = bq + r. Giả sử tồn tại hai cặp (q; r) và (q 0 ; r 0 ) sao cho a = bq + r = bq0 + r 0 , 0 6 r, r 0 6 b −1. Khi đó b(q − q 0 ) = r 0 − r ⇒ r 0 − r . . .b. Do 0 6 r, r 0 6 b−1 nên 0 6 |r − r 0 | 6 b−1. Từ đây ta suy ra r − r 0 = 0 hay r = r 0 , do đó q = q 0 . Vậy định lí được chứng minh. Chú ý 2.1. Ta có thể mở rộng tính chất trên cho hai số nguyên bất kì. Cụ thể: Cho hai số nguyên a,b với b 6= 0. Khi đó, tồn tại duy nhất cặp số nguyên (q; r) sao cho a = bq + r, 0 6 r < |b|. Ở trên ta có thể chọn điều kiện của r như sau: − • b 2 ¸ 6 r 6 • b 2 ¸ . Như vậy, tập các số nguyên khi phân hoạch theo bội của b thì được chia thành b tập rời nhau. Chẳng hạn, khi phân hoạch theo bội của 3 thì Z = A ∪ B ∪ C trong đó A = {3k|k ∈ Z}, B = {3k +1|k ∈ Z} và C = {3k +2 (hoặc 3k −1)|k ∈ Z} Ví dụ 2.1. Tìm các số nguyên x để biểu thức sau nhận giá trị nguyên A = 2x 3 − x 2 + x−1 2x−1 . Lời giải. Ta có A = x 2 + 1 2 − 1 2(2x−1) . Suy ra 2A = 2x 2 +1− 1 2x−1 . Vì A nguyên nên 2A nguyên, do đó 1 2x−1 nguyên hay 2x−1 là ước của 1. Suy ra x = 0 hoặc x = 1. Với x = 0 ta có A = 1, với x = 1 ta có A = 1. Vậy x = 0, x = 1 là những giá trị cần tìm. Nguyễn Tất Thu 2.1. Chia hết 13 Ví dụ 2.2. Tìm các số tự nhiên x để biểu thức sau là số nguyên A = 2x 3 − x 2 +5x+4 x 2 +1 . Lời giải. Ta có A = 2x−1+ 3x+5 x 2 +1 . Vì x ∈ Z nên A ∈ Z khi và chỉ khi 3x+5 x 2 +1 ∈ Z Suy ra 3x+5 > x 2 +1 ⇔ x 2 −3x−4 6 0 ⇔ −1 6 x 6 4. Mà x là số tự nhiên nên x ∈ {0;1;2;3;4}. Thay lần lượt các giá trị của x ta có x ∈ {0;1;4}. Ví dụ 2.3. Chứng minh rằng A = n(n 2 +1)(n 2 +4). . .5 với mọi số nguyên dương n. Lời giải. Ta xét các trường hợp sau • n = 5k, ta có A . . .5. • n = 5k ±1, ta có n 2 +4 . . .5 nên A . . .5. • n = 5k ±2, ta có n 2 +1 . . .5 nên A . . .5. Vậy A . . .5 với mọi số nguyên dương n. Ví dụ 2.4. Cho a,b là các số nguyên. Chứng minh rằng 8a+9b . . .31 ⇔ a+5b . . .31. Lời giải. Ta có 5(8a+9b)−9(a+5b) = 31a. Do (5;31) = (9;31) = 1 nên 8a+9b . . .31 ⇔ a+5b . . .31. Ví dụ 2.5. Cho các số nguyên x, y. Chứng minh rằng 1. x n − y n . . .x− y với mọi số tự nhiên n. 2. x n + y n . . .x+ y với mọi số tự nhiên n lẻ. Nguyễn Tất Thu 14 Chương 2. Lý thuyết chia hết Lời giải. 1) Với mọi số tự nhiên n, ta có x n − y n = (x− y)(x n−1 + y n−2 x+...+ y n−1 ). Suy ra x n − y n . . .x− y. 2) Với n là số tự nhiên lẻ, ta có x n + y n = (x+ y)(x n−1 − x n−2 y+...+ y n−1 ). Suy ra x n + y n . . .x+ y. Ví dụ 2.6. Tìm số nguyên dương lớn nhấtx để 23x+26 chia hết 2014!. Lời giải. Từ 1 đến 2014 có • 2014 23 ¸ = 87 số chia hết cho 23. Trong đó có ba số chia hết cho 232 là 232 , 2.232 , 3.232 . Do đó 2014!. . .2390 và 2014!không chia hết cho 2391. Suy ra x+26 = 90 ⇒ x = 64. Ví dụ 2.7. Cho n > 2 là số nguyên dương. Chứng minh rằng 2 2 n+1 + 2 2 n + 1 có ít nhất 3 ước nguyên dương lớn hơn 1. Lời giải. Ta có a 4 + a 2 +1 = ¡ a 2 +1 ¢2 − a 2 = ¡ a 2 + a+1 ¢ ¡a 2 − a+1 ¢ Suy ra 2 2 n+1 +2 2 n +1 = ³ 2 2 n−1 ´4 + ³ 2 2 n−1 ´2 +1 = ³ 2 2 n −2 2 n−1 +1 ´ ³2 2 n +2 2 n−1 +1 ´ = ³ 2 2 n −2 2 n−1 +1 ´ •³ 2 2 n−2 ´4 + ³ 2 2 n−2 ´2 +1 ¸ = ³ 2 2 n −2 2 n−1 +1 ´ ³2 2 n−1 +2 2 n−2 +1 ´ ³2 2 n−1 −2 2 n−2 +1 ´ . Từ đó, ta có đpcm. Ví dụ 2.8. Cho n là số nguyên dương thỏa 3 n −1 . . .2 2014 . Chứng minh rằng n > 2 2012 . Lời giải. Đặt n = 2 k .m với m lẻ. Khi đó 3 n −1 = ³ 3 2 k −1 ´ •³ 3 2 k ´m−1 + ³ 3 2 k ´m−2 +...+3 2 k +1 ¸ Vì m lẻ nên ³ 3 2 k ´m−1 + ³ 3 2 k ´m−2 +...+3 2 k +1 là số lẻ. Do đó 3 n −1 . . .2 2014 ⇔ 3 2 k −1 . . .2 2014 . Nguyễn Tất Thu 2.1. Chia hết 15 Mà 3 2 k −1 = (3−1) (3+1) ¡ 3 2 +1 ¢ ³ 3 2 2 +1 ´ ... ³ 3 2 k−1 +1 ´ = 2 3 . ¡ 3 2 +1 ¢ ³ 3 2 2 +1 ´ ... ³ 3 2 k−1 +1 ´ . Vì 3 2 m +1 ³ m = 1,k −1 ´ chỉ chia hết cho 2 mà không chia hết cho 4 nên 3 2 k −1 . . .2 2014 ⇔ k +2 > 2014 ⇔ k > 2012. Suy ra n > 2 2012 . Ví dụ 2.9. Tìm tất cả các số nguyên a,b, c với 1 < a < b < c sao cho (a−1) (b −1) (c −1) là một ước của abc −1. Lời giải. Đặt x = a−1, y = b −1, z = c −1 ⇒ 0 < x < y < z, khi đó x yz là ước của (x+1) (y+1) (z +1)−1 = x yz + x y+ yz + zx+ x+ y+ z. Hay x yz là ước của x y+ yz + zx+ x+ y+ z. Suy ra x y+ yz + zx+ x+ y+ z x yz = 1 x + 1 y + 1 z + 1 x y + 1 yz + 1 zx = f (x, y, z) là số nguyên dương. Ta có f (x, y, z) 6 f (1,2,3) = 2+ 5 6 < 3 ⇒ f (x, y, z) = 1 hoặc f (x, y, z) = 2. Mặt khác f (3,4,5) = 59 60 < 1 ⇒ x ∈ {1,2}. • f (x, y, z) = 1 ⇔ x y+ yz + zx+ x+ y+ z = x yz. (1) +) x = 1, khi đó (1) ⇔ 2(y+ z)+1 = 0 vô nghiệm. +) x = 2, khi đó (1) ⇔ 3(y+ z)+2 = yz ⇔ (y−3) (z −3) = 11 ⇔ ( y−3 = 1 z −3 = 11 ⇔ ( y = 4 z = 14 . • f (x, y, z) = 2 ⇔ x y+ yz + zx+ x+ y+ z = 2x yz. (2) +) x = 1, khi đó (2) ⇔ 2(y+ z)+1 = yz ⇔ (y−2) (z −2) = 5 ⇔ ( y−2 = 1 z −2 = 5 ⇔ ( y = 3 z = 7 vô nghiệm. +) x = 2, khi đó (2) ⇔ 3(y+ z)+2 = 3yz vô nghiệm. Vậy (a;b; c) = (2;4;8),(3;5;16) . Nguyễn Tất Thu 16 Chương 2. Lý thuyết chia hết Ví dụ 2.10. Tìm tất cả các cặp nguyên dương (a,b) sao cho a 2 2ab2 − b 3 +1 là một số nguyên dương. Lời giải. Vì a 2 2ab2 − b 3 +1 là số nguyên dương nên 2ab2 − b 3 + 1 = b(2a− b) + 1 > 0. Suy ra 2a− b > 0. Ta có a 2 > 2ab2 − b 3 +1 (*). +) Nếu b = 2a thì (*) đúng +) Nếu b > 2a ⇒ a 2 > b 2 (2a−1− b)+ b 2 +1 > b 2 ⇒ a > b Do đó, ta luôn có b = 2a hoặc a > b. Đặt a 2 2ab2 − b 3 +1 = k ∈ Z + . Hay a 2 −2ab2k + kb3 − k = 0 (1). Với mỗi k thì phương trình (1) có hai nghiệm nguyên không âm a1 > a2 . Theo định lí Viet, ta có a1 + a2 = 2b 2 k ⇒ a1 > b 2 k a1a2 = k ¡ b 3 −1 ¢ ⇒ a2 = k ¡ b 3 −1 ¢ a1 6 b. Suy ra a2 = 0 hoặc b = 2a2. +) a2 = 0 ⇒ b 3 −1 = 0 ⇒ b = 1 ⇒ a = 2k +) b = 2a2 ⇒ b 2 4 − k = 0 ⇒ b 2 = 4k và a1 = b 4 2 − b 2 . Suy ra k = m2 ⇒ a2 = m,a1 = 8m4 − m. Vậy (a;b) ∈ © (2m;1),(m;2m), ¡ 8m4 − m;2m ¢ª với m ∈ Z +. Một số bài tập luyện tập. Bài tập 2.1. Tìm số tự nhiên n để n 2 +1 . . .n+1. Lời giải. Ta có n 2 +1 n+1 = n−1+ 2 n+1 . Từ đây, suy ra n+1 = 1 hoặc n+1 = 2. Hay là n = 0,n = 1. Bài tập 2.2. Tìm số nguyên x sao cho A = 3x 2 +2x−1 x 2 +1 là số nguyên. Nguyễn Tất Thu 2.1. Chia hết 17 Lời giải. Ta có A = 3+ 2x−4 x 2 +1 . A là số nguyên khi và chỉ khi 2x−4 x 2 +1 là số nguyên. Suy ra |2x−4| > x 2 +1 ⇔ x 2 +2x−3 6 0 ⇔ −1 6 x 6 3. Mà x nguyên nên x ∈ {−1;0;1;2;3}. Thử lại ta có x ∈ {−1;0;1;2}. Bài tập 2.3. Cho số nguyên x thỏa mãn 17|3x+2. Chứng minh rằng 17 là ước của 6x 3 + x 2 −5x+15. Lời giải. Ta có 6x 3 + x 2 −5x+15 = 6x 3 + x 2 −5x−2+17 = (3x+2)(2x 2 − x−1)−17 . . .17. Bài tập 2.4. Chứng tỏ rằng với mọi số tự nhiên n, giữa n 2 và (n +1)2 có thể tìm thấy ba số tự nhiên a, b, c sao cho c ¯ ¯ a 2 + b 2 . Lời giải. Chọn a = n 2 +2,b = n 2 + n+1, c = n 2 +1 . Bài tập 2.5. Cho số tự nhiên n. Chứng minh rằng n 5 5 + n 4 2 + n 3 3 − n 30 là số nguyên. Lời giải. Ta có n 5 5 + n 4 2 + n 3 3 − n 30 = 6n 5 +15n 4 +10n 3 − n 30 Do 6n 5 +15n 4 +10n 3 − n = n(n+1)(2n+1)(3n 2 +3n−1) Mà n(n+1)(2n+1). . .6. Ta chứng minh a(n) = 6n 5 +15n 4 +10n 3 − n . . .5 (1). • n = 5k thì a(n) . . .5. • n = 5k +1 hoặc n = 5k −2 thì 3n 2 +3n−1 . . .5 nên a(n) . . .5. • n = 5k −1 thì n+1 . . .5 nên a(n) . . .5. • n = 5k +2 thì 2n+1 . . .5 nên a(n) . . .5. Từ đó ta có đpcm. Nguyễn Tất Thu 18 Chương 2. Lý thuyết chia hết Bài tập 2.6. Chứng minh rằng 120|n 5 −5n 3 +4n với mọi số tự nhiên n. Lời giải. Ta có 120 = 2 3 .3.5 và n 5 −5n 3 +4n = n(n 2 −1)(n 2 −4) = (n−2)(n−1)n(n+1)(n+2) Trong 5 số tự nhiên liên tiếp luôn tồn tại ít nhất một số chia hết cho 5, một số chia hết cho 3 và có ít nhất hai số chẵn liên tiếp nên tích hai số chẵn này chia hết cho 8. Do đó: n 5 −5n 3 +4n chia hết cho 120. Bài tập 2.7. Cho n là số nguyên dương. Chứng minh rằng (n+1)(n+2)...(2n) . . .2 n . Lời giải. Ta chứng minh bài toán bằng phương pháp quy nạp. Với n = 1 ta thấy bài toán đúng. Giả sử (n+1)(n+2)...(2n) . . .2 n Ta chứng minh (n+2)(n+3)...(2n).(2n+1)(2n+2). . .2 n+1 . Thật vậy (n+2)(n+3)...(2n).(2n+1)(2n+2) = (n+1)(n+2)...(2n).(2n+1).2 . . .2 n+1 . Vậy bài toán được chứng minh. Bài tập 2.8. Xác định tất cả các cặp số (a,b) nguyên dương sao cho ab2 + b + 7 chia hết a 2b + a+ b. Lời giải. Ta có ab2 + b +7 ¯ ¯a 2b + a+ b nên ab2 + b +7 ¯ ¯b(a 2 b + a+ b)− a(ab2 + b +7) = b 2 −7a • b 2 = 7a ⇒ a = 7k 2 ,b = 7k với k ∈ N. • b 2 −7a > 0 ⇒ ab2 + b +7 6 b 2 −7a (vô lí). Vì ab2 + b +7 > b 2 > b 2 −7a. • b 2 −7a < 0 ⇒ ab2 + b +7 6 7a− b 2 ⇒ b 2 < 7 ⇒ b = 1,b = 2. +) b = 1 ⇒ 7a−1 = 7(a+8)−57 . . .a+8 ⇒ " a+8 = 57 a+8 = 19 ⇒ " a = 49 a = 11 Nguyễn Tất Thu 2.1. Chia hết 19 +) b = 2 ⇒ 7a−4 = 2(4a+9)−(a+22) . . .4a+9 ⇒ a+22 . . .4a+9 . Suy ra a+22 > 4a+9 ⇒ a 6 13 3 ⇒ a ∈ {1,2,3,4}. Thử lại ta thấy không có a thỏa bài toán. Vậy (a;b) = ¡ 7k 2 ;7k ¢ , (49;2), (11;2). Bài tập 2.9. Tìm tất cả các số nguyên dương n sao cho với mọi số nguyên lẻ a mà a 2 < n thì a|n. Lời giải. Gọi a là số nguyên lẻ lớn nhất mà a 2 < n, suy ra n 6 (a+2)2 . Vì a,a−2,a−4 là các số lẻ không nên n chia hết cho a,a−2,a−4. Suy ra a(a−2) (a−4) 6 (a+2)2 ⇔ a 3 −7a 2 +4a−4 6 0 ⇒ a < 7. Do đó a ∈ {1,3,5}. • Nếu a = 1 ta có: 1 6 n 6 9, từ đây ta tìm được n = 3. • Nếu a = 3 ta có 9 < n 6 25, từ đây ta tìm được n ∈ {12;15;18;21;24}. • Nếu a = 5 ta có 25 < n 6 49, từ đây ta tìm được n ∈ {30,45}. Vậy n ∈ {3;12;15;18;21;24;30;45}. Bài tập 2.10. Tìm tất cả các số nguyên dương (x,n) sao cho x n + 2 n + 1 là một ước của x n+1 +2 n+1 +1. Lời giải. • n = 1 ⇒ x 2 +5 = (x+3) (x−3)+14 . . .x+3 ⇒ " x+3 = 7 x+3 = 14 ⇒ " x = 4 x = 11 . • Xét n > 2. +) Với x ∈ {1,2,3} ta có 1+2 n +1 < 1+2 n+1 +1 < 2 ¡ 1+2 n +1 ¢ 2 n +2 n +1 < 2 n+1 +2 n+1 +1 < 2 ¡ 2 n +2 n +1 ¢ 2 ¡ 3 n +2 n +1 ¢ < 3 n+1 +2 n+1 +1 < 3 ¡ 3 n +2 n +1 ¢ Do đó x n +2 n +1 không là ước của x n+1 +2 n+1 +1 với x ∈ {1,2,3}. +) Xét x > 4, ta có x n+1 +2 n+1 +1 < x(x n +2 n +1) Ta chứng minh x n+1 +2 n+1 +1 > (x−1) ¡ x n +2 n +1 ¢ . (1) Thật vậy (1) ⇔ x n+1 +2 n+1 +1 > x n+1 + x.2 n + x− x n −2 n −1 ⇔ x n +2 n+1 +2 n +2 > x ¡ 2 n +1 ¢ (2) Nguyễn Tất Thu 20 Chương 2. Lý thuyết chia hết Ta có x n = x n 2 + x n 2 > 2 2n + x 2 2 . Suy ra x n +2 n+1 +2 > 2 2n + x 2 2 +2 n+1 +2 n +2 > 2 2n +2.2 n +1+ x 2 2 = (2 n +1) 2 + x 2 2 > x ¡ 2 n +1 ¢ ⇒ (2) đúng. Vậy (x−1) ¡ x n +2 n +1 ¢ < x n+1 +2 n+1 +1 < x ¡ x n +2 n +1 ¢ Suy ra x n +2 n +1 không là ước của x n+1 +2 n+1 +1. Bài tập 2.11. Cho tam thức f (x) = ax2+bx+c trong đó a,b, c ∈ Z, a chẵn và b lẻ. Chứng minh rằng với mỗi số nguyên dương n, tồn tại số nguyên dương x sao cho 2 n ¯ ¯ax2 + bx + c . Lời giải. • n = 1 ta chọn x1 lẻ nếu c lẻ và x1 chẵn nếu c chẵn. Khi đó 2 1 ¯ ¯ax2 1 + bx1 + c • Giả sử 2 n ¯ ¯ax2 n + bxn + c = P(xn) với xn ∈ N∗, ta chỉ ra tồn tại xn+1 ∈ N∗ để 2 n+1 ¯ ¯ax2 n+1 + bxn+1 + c = P(xn+1) Nếu 2 n+1 |P(xn) thì ta chọn xn+1 = xn. Ngược lại, P(xn) = 2 n .d với d ∈ N,d lẻ. Ta có P(x)− P(xn) = (x− xn)[a(x+ xn)+ b] với a(x+ xn)+ b lẻ với mọi x ∈ N. Đặt xn+1 = xn +2 n .k với k ∈ N∗,k lẻ. Ta có: P(xn+1) = P(xn)+2 n .k[a(xn+1 + xn)+ b] = 2 n [d + k(a(xn+1 + xn)+ b)] Do d + k(a(xn+1 + xn)+ b) là số chẵn nên ta có: 2 n+1 |P(xn+1) . Nguyễn Tất Thu 2.1. Chia hết 21 Bài tập 2.12. Cho các số nguyên a,b, c với b 6= c. Chứng minh rằng nếu các phương trình ax2 + bx + c = 0 và (c − b) x 2 +(c − a) x+ a+ b có nghiệm chung thì a+ b +2cchia hết cho 3. Lời giải. Gọi x0là nghiệm chung của hai phương trình đã cho. Đặt f (x) = ax2 + bx + c, g(x) = (c − b) x 2 +(c − a) x+ a+ b Ta có f (x)− g(x) = (a+ b − c) ¡ x 2 + x−1 ¢ . Nếu a+ b − c 6= 0thì x0 là nghiệm của phương trình x 2 + x−1 = 0 nên x0 là số vô tỉ. Theo thuật toán Ơclit, ta có f (x) = m ¡ x 2 + x−1 ¢ + nx + p với m,n, p ∈ Z. Ta có f (x0) = 0 ⇒ nx0 + p = 0 điều này vô lí. Do đó, ta có a+ b − c = 0 ⇒ a+ b +2c = 3c . . .3. Bài tập 2.13. Cho các số nguyên dương m,n thỏa m 6 n 2 4 và nếu p là ước nguyên tố của m thì p 6 n. Chứng minh rằng n! . . .m. Lời giải. Giả sử p là ước nguyên tố của m và k là số mũ cao nhất của p trong phân tích đó. Ta chứng minh n! . . .p k . Với k = 1, vì p 6 n nên n! . . .p. Vì m 6 n 2 4 nên p k 6 n 2 4 ⇒ n > 2 q p k. Ta chứng minh n > kp, bằng cách chứng minh 2 q p k > kp ⇔ p k −2 2 > k 2 . (∗) Với k = 2 thì (*) đúng. Với k = 3 thì (*) đúng với p > 3, còn với p = 2 ⇒ n > 5 ⇒ n! . . .8 = 2 3 Với k > 4, áp dụng bđt Becnuli ta có p k −2 2 > 1+ k −2 2 (p −1) > k 2 nên (*) đúng. Do n > kp nên n! . . .p k . Bài toán được chứng minh. Nguyễn Tất Thu 22 Chương 2. Lý thuyết chia hết Bài tập 2.14. Tìm các số nguyên a,b sao cho a 2 + ab +1 ¯ ¯b 2 + ab + a+ b −1. Lời giải. Ta có a 2 + ab +1|b 2 + ab + a+ b −1 ⇔ a 2 + ab +1|b 2 +2ab + a 2 + a+ b = (a+ b)(a+ b +1). Nếu a+ b = 0 hoặc a+ b = −1 thì ta có lời giải cho bài toán. Nếu a+ b = 1 ⇒ a+1|2 ⇒ a = −3,a = 0,a = −2,a = 1. Xét a+ b ∉ {−1,0,1}, khi đó vì ¡ a 2 + ab +1,a+ b ¢ = (a,a+ b) = 1 nên ta có a 2 + ab +1|a+ b +1 ⇒ a 2 + ab +1|a 2 + ab − a− b = (a−1) (a+ b). Suy ra a 2 + ab +1|a−1 (2). Với a = 1 thì (2) hiển nhiên đúng. Với |a+ b| 6 1 thì (2) hiển nhiên đúng. Xét ( a 6= 1 |a+ b| > 2 , khi đó |a(a+ b)+1| 6 |a−1|. Ta có 2|a|−1 6 |a(a+ b)|−1 6 |a(a+ b)+1| 6 |a−1| Suy ra a = 0,a = −1,a = −2. Vậy (a,b) ∈ {(−k,k); (−k −1,k); (−3,4); (−2,3); (1,0); (−1,3); (−1,4); (−2,4)} với k ∈ Z. Bài tập 2.15. Cho n số nguyên dương lẻ. Chứng minh rằng 3 n +1 không chia hết cho n. Lời giải. Giả sử tồn tại n để 3 n +1 . . .n. Gọi p là ước nguyên tố nhỏ nhất của n. Khi đó 3 n ≡ −1(mod p) ⇒ 3 2n ≡ 1(mod p) Mà 3 p−1 ≡ 1(mod p) nên 3 (2n,p−1) ≡ 1(mod p) Mà (n; p −1) = 1 nên (2n; p −1) = 2 ⇒ 3 2 −1 = 8 . . .p vô lí do p lẻ. Bài tập 2.16. Tìm các số nguyên a,b, c > 1 thỏa ab−1 chia hết cho c, bc−1 chia hết cho a và ca −1 chia hết cho b. Nguyễn Tất Thu 2.1. Chia hết 23 Lời giải. Từ giả thiết, ta có a,b, c đôi một nguyên tố cùng nhau. Từ đó, ta có (ab −1) (bc −1) (ca−1) . . .abc Hay ab + bc + ca −1 . . .abc. Vì ab + bc + ca > 1 nên ta có ab + bc + ca > abc ⇒ f (a,b, c) = 1 a + 1 b + 1 c > 1. (1) Không mất tính tổng quát, ta giả sử a < b < c. Ta có f (3,4,5) = 1 3 + 1 4 + 1 5 < 1 nên a = 2. Khi đó 1 b + 1 c > 1 2 . Vì 1 4 + 1 5 = 9 20 < 1 2 ⇒ 2 < b < 4 ⇒ b = 3 ⇒ 1 c > 1 2 − 1 3 = 1 6 ⇒ 3 < c < 6 ⇒ c = 4,5. Thử lại ta có (a,b, c) = (2,3,5) và các bộ hoán vị. Bài tập 2.17. Tìm tất cả các số nguyên dương m,n sao cho m2 + n n 2 − m và n 2 + m m2 − n là các số nguyên. Lời giải. • m = n ta có m2 + n n 2 − m = m2 + m m2 − m = 1+ 2 m−1 nên m = 2,m = 3. • m > n, khi đó n 2 + m m2 − n > 1 ⇔ n 2 + m > m2 − n ⇔ n+1 > m Suy ra m = n+1, khi đó m2 + n n 2 − m = (n+1)2 + n n 2 − n−1 = 1+ 4n+2 n 2 − n−1 +) Với n = 1 ta có m2 + n n 2 − m ∈ Z. +) Với n > 2, suy ra 4n+2 n 2 − n−1 > 1 ⇔ n 2 −5n−3 6 0 ⇔ n 6 5+ p 37 2 . Nên n = 2,3,4,5. Thử lại ta có n = 2 ⇒ m = 3. • m < n tương tự như trên ta có được Nguyễn Tất Thu 24 Chương 2. Lý thuyết chia hết ( m = 2 n = 3 và ( m = 1 n = 2 . Vậy các cặp (m;n) cần tìm là: (2;2),(3;3),(1;2),(2;1),(2;3),(3;2) 2.2 Số nguyên tố Định nghĩa 2.2. • Số nguyên tố là số nguyên dương lớn hơn 1 chỉ chia hết cho 1 và chính nó. • Số nguyên dương khác 1 không là số nguyên tố được gọi là hợp số. Định lí 2.3. Tồn tại vô hạn số nguyên tố. Chứng minh. Để chứng minh định lí này, ta cần bổ đề sau: Bổ đề: Mọi số nguyên dương lớn hơn 1 đều có ít nhất một ước nguyên tố. Thật vậy: Giả sử tồn tại số nguyên dương n khác 1 và n không có ước nguyên tố. Trong các số như vậy ta xét n là số nhỏ nhất. Vì n không là số nguyên tố nên tồn tại các số nguyên dương a,b sao cho n = ab và 1 < a,b < n. Vì a < n nên a có ít nhất một ước nguyên tố. Rõ ràng ước nguyên tố của a cũng là ước của n. Điều này trái với giả sử ở trên. Vậy bổ đề được chứng minh. Trở lại bài toán: Ta có thể chứng minh định lí trên theo hai cách sau: Cách 1: Xét Pn = n! + 1, theo bổ đề trên ta có Pn có ít nhất một ước nguyên tố pn. Dễ thấy pn > n. Vậy mỗi số nguyên dương n ta có ít nhất một số nguyên tố pn > n. Từ đó, suy ra có vô hạn số nguyên tố. Cách 2: Gải sử có hữu hạn số nguyên tố p1 < p2 < ... < pn. Xét số a = p1p2 ... pn + 1, ta có a có một ước nguyên tố q. Dễ thấy q > pn (vì nếu q 6 pn thì q sẽ trùng với một trong các số p1, p2,..., pn,khi đó q là ước của 1).Điều này trái với việc giả sử trên. Vậy định lí được chứng minh. Định lí 2.4. Nếu số nguyên dương n là hợp số, thì n có ước nguyên tố không vượt quá p n. Chứng minh. Vì n là hợp số, nên n = ab với a,b là các số nguyên 1 < a 6 b < n. Suy ra n > a 2 hay a 6 p n. Định lí được chứng minh. Ví dụ 2.11. Chứng minh rằng với mọi số tự nhiên n > 1 thì n 5 + n 4 + 1 không phải là số nguyên tố. Nguyễn Tất Thu 2.2. Số nguyên tố 25 Lời giải. Ta có: n 5 + n 4 +1 = ¡ n 2 + n+1 ¢ ¡n 3 − n+1 ¢ . Mà n 2 + n+1 > 1 và n 3 − n+1 > 1 nên n 5 + n 4 +1 là hợp số. Ví dụ 2.12. Tìm tất cả các cặp số nguyên dương (a;b) sao cho a 4 +4b 4 là số nguyên tố. Lời giải. Ta có: a 4 +4b 4 = ¡ a 2 +2b 2 ¢2 −(2ab) 2 = ¡ a 2 +2ab +2b 2 ¢ ¡a 2 −2ab +2b 2 ¢ . Từ đó ta tìm được a = b = 1. Ví dụ 2.13. Cho n là số tự nhiên dương. Chưng minh rằng luôn tồn tại n số tự nhiên liên tiếp sao cho chúng là hợp số. Lời giải. Đặt a = (n+1)!. Xét n số a+2,a+3,...,a+ n+1. Ta thấy n số này đều là hợp số. Ví dụ 2.14. Chứng minh rằng: Có vô hạn số nguyên tố dạng 4k +3. Lời giải. Giả sử có hữu hạn số nguyên tố dạng 4k +3. Gọi các số đó là p1, p2,..., pn. Xét số nguyên dương m = 4p1p2 ... pn +3, khi đó m có dạng 4k +3. Nếu tất cả các ước nguyên tố của m đều có dạng 4k +1 thì m có dạng 4k +1 (vô lí). Do đó, m có ít nhất một ước nguyên tố dạng 4k + 3, kí hiệu số nguyên tố này là p.Dễ thấy p > pn (vô lí). Ví dụ 2.15. Cho p là số nguyên tố dạng 4k +3. Chứng minh rằng x 2 + y 2 chia hết cho p khi và chỉ khi x và ychia hết cho p. Lời giải. +) Nếu x hoặc y chia hết cho p thì hiển nhiên số còn lại cũng chia hết cho p. +) Xét x, y cùng không chia hết cho p. Vì p là số nguyên tố nên (x; p) = (y; p) = 1. Do đó, theo định lí Fecma ta có: x p−1 ≡ y p−1 ≡ 1(mod p) hay x 4k+2 ≡ y 4k+2 (mod p) ⇔ ¡ x 2 ¢2k+1 ≡ ¡ y 2 ¢2k+1 (mod p) Suy ra x ≡ y(mod p), do đó x 2 + y 2 ≡ 2x 2 (mod p) ⇒ 2 . . .p vô lí. Vậy ta có điều phải chứng minh. Chú ý 2.2. Với mọi số nguyên x thì x 2 +1 không có ước dạng 4k +3. Ví dụ 2.16. Cho p, q, r là các số nguyên tố và n là số tự nhiên thỏa p n + q n = r 2 Chứng minh n = 1. Nguyễn Tất Thu 26 Chương 2. Lý thuyết chia hết Lời giải. Giả sử n > 2. Trong ba số p, q, r có một số chẵn. • r = 2, khi đó p n + q n = 4 điều này không xảy ra. • p > q = 2, ta có: p n +2 n = r 2 . +) n lẻ. Suy ra : (p +2)(p n−1 −2p n−2 +...+2 n−1 ) = r 2 Vì p +2 > 1 và p n−1 −2.p n−2 +...+2 n−1 > 2 n−1 > 1. Nên ta có r = p +2, suy ra p n +2 n = (p +2)2 = p 2 +4p +4. Điều này không thể xảy ra với n > 3. +) n = 2k, ta có: p 2k +2 2k = r 2 . Theo phương trình Pitago ta có: p k = a 2 − b 2 , 2 k = 2ab, r = a 2 + b 2 với a,b ∈ Z,a > b,(a,b) = 1. Ta có: b = 1,a = 2 k−1 , suy ra p k = 4 k−1 −1 < 4 k ⇒ p = 3. Hay 3 k = 4 k−1 −1 phương trình này vô nghiệm. Do đó ta có n = 1. Ví dụ 2.17. Cho p là số nguyên tố. Tìm tất cả các số nguyên k sao cho p k 2 − pk là số nguyên dương. Lời giải. Ta xét các trường hợp sau: • p = 2 ta có: k 2 −2k = (k −1)2 −1 không thể là một số chính phương lớn hơn 0. • p > 3. +) k . . .p, ta có k = np và k 2 − pk = p 2n(n−1). Do n(n−1) > 0 không thể là số chính phương nên trường hợp này không tồn tại k. +) (k; p) = 1, suy ra (k;k − p) = 1. Do đó k(k − p) là số chính phương khi và chỉ khi k = m2 ,k − p = n 2 Suy ra p = m2 − n 2 = (m+ n)(m− n). Mà p nguyên tố nên dẫn đến ( m− n = 1 m+ n = p ⇒ m = p +1 2 và k = (p +1)2 4 . Thử lại ta thấy thỏa mãn. Vậy k = (p +1)2 4 với p là số nguyên tố lẻ. Ví dụ 2.18. Chứng minh rằng với mọi số nguyên tố p thì p 3 + p −1 2 không phải là tích của hai số tự nhiên liên tiếp. Nguyễn Tất Thu 2.2. Số nguyên tố 27 Lời giải. Nếu p = 2 suy ra p 3 + p −1 2 không nguyên. Nếu p = 4k + 1, suy ra p 3 + p −1 2 = (4k +1)3 + 2k là số lẻ nên p 3 + p −1 2 không thể là tích của hai số tự nhiên liên tiếp. Nếu p = 4k +3. Giả sử p 3 + p −1 2 = x(x+1) ⇔ 2p(2p 2 +1) = (2x+1)2 +1 với x ∈ N. Suy ra (2x+1) 2 +1 . . .p vô lí vì p = 4k +3. Từ các trường hợp trên, ta có điều phải chứng minh. Ví dụ 2.19. Nếu p là số nguyên tố có dạng 4k+1 thì tồn tại hai số nguyên dương c,d sao cho p = c 2 + d 2 . Lời giải. Trước hết ta có bổ đề sau: Bổ đề: Nếu p ≡ 1(mod 4) là số nguyên tố thì •µ p −1 2 ¶ ! ¸2 ≡ −1(mod p). Thật vậy: Theo định lí Winsol thì (p −1)! ≡ −1(mod p). Mà p − k ≡ (−1).k(mod p) nên (p −1)! = 1.2...µ p −1 2 ¶ . µ p − p −1 2 ¶ ...(p −1) ≡ (−1) p −1 2 •µ p −1 2 ¶ ! ¸2 ≡ −1(mod p). Chứng minh định lí: Vì p ≡ 1(mod 4) nên tồn tại x sao cho x 2 ≡ −1(mod p) (Chẳng hạn x = µ p −1 2 ¶ ! ). Đặt t = £p p ¤ ⇒ (t+1) 2 > p. Xét tập S = {a+ xb|0 6 a,b 6 t}, ta có |S| = (t+1) 2 > p . Suy ra trong S có ít nhất một cặp đồng dư với nhau theo (mod p). Hay a+ bx ≡ a1 + b1x(mod p) ⇒ (a− a1) 2 ≡ (b − b1) 2 x 2 ≡ −(b − b1) 2 (mod p) Suy ra (a− a1) 2 +(b − b1) 2 ≡ 0(mod p). Vì 0 6 a,a1,b,b1 6 t nên ta có (a− a1) 2 +(b − b1) 2 = p. Đặt c = |a− a1|,d = |b − b1| ta có p = a 2 + b 2 . Nguyễn Tất Thu 28 Chương 2. Lý thuyết chia hết Bài tập vận dụng. Bài tập 2.18. Tìm tất cả các số nguyên tố p sao cho: 1. p +10 và p +14 cũng là số nguyên tố. 2. p +2, p +6, p +8, p +12, p +14 đều là số nguyên tố. Lời giải. 1) Ta có p = 2 không thỏa và p = 3 thỏa bài toán. Xét p > 5, ta có các trường hợp sau • p = 3k +1, khi đó p +14 = 3k +15 = 3(k +5) là hợp số. • p = 3k +2, khi đó p +10 = 3(k +4) là hợp số. Vậy p = 3 là số cần tìm. 2) Ta có p là số lẻ và p = 3 không thỏa, p = 5 thỏa bài toán. Xét p > 5. Xét p = 5k + r ta thấy trường hợp này không thỏa. Vậy p = 5 là số cần tìm. Bài tập 2.19. Cho số nguyên tố p sao cho 8p 2 +1 là số nguyên tố. Chứng minh rằng 8p 2 −1 cũng là số nguyên tố. Lời giải. Ta xét các trường hợp sau • p = 2 ⇒ 8p 2 +1 = 33 . . .3 • p = 3 ⇒ 8p 2 +1 = 73 là số nguyên tố • p > 5, khi đó p 2 = 3k +1 ⇒ 8p 2 +1 = 3(8k +3) . . .3 nên 8p 2 +1 không là số nguyên tố. Do đó, ta chỉ có p = 3 ⇒ 8p 2 −1 = 71 là số nguyên tố. Bài tập 2.20. Cho số nguyên dương n thỏa mãn 2 n −1 là số nguyên tố. Chứng minh rằng n là số nguyên tố. Lời giải. Giả sử n là hợp số, ta có n = ab với 2 6 a 6 b < n. Khi đó 2 n −1 = 2 ab −1 = (2a −1)(2a(b−1) +2 a(b−2) +...+1) là hợp số. Điều này trái với giả thiết. Vậy n là số nguyên tố. Bài tập 2.21. Chứng minh rằng có vô hạn số nguyên tố dạng 3k −1. Lời giải. Giả sử có hữu hạn số nguyên tố p1, p2,..., pn dạng 3k+1. Xét a = 3p1p2 ... pn−1,khi đó ta có các khả năng sau Nguyễn Tất Thu 2.2. Số nguyên tố 29 • a là số nguyên tố, khi đó a có dạng 3k −1 và a > pn (vô lí). • a là hợp số, khi đó a có ít nhất một ước nguyên tố pn+1 có dạng 3k−1. Vì ngược lại, nếu mọi ước của a đều có dạng 3k +1 thì a có dạng 3k +1. Dễ thấy pn+1 > pn điều này cũng vô lí. Vậy có vô hạn số nguyên tố dạng 3k −1. Bài tập 2.22. Tìm số nguyên tố p để 2 p + p 2 cũng là số nguyên tố. Lời giải. Ta xét các trường hợp sau • p = 2, khi đó 2 p + p 2 = 8 là hợp số. • p = 3, khi đó 2 p + p 2 = 17 là số nguyên tố. • p > 3, khi đó 2 p + p 2 = (2p + 1) + (p 2 − 1). Vì p lẻ và không chia hết cho 3 nên 2 p + 1 . . .3 và p 2 −1 . . .3. Suy ra 2 p + p 2 . . .3 nên 2 p + p 2 là hợp số. Vậy p = 3 là số cần tìm. Bài tập 2.23. Tìm các số tự nhiên m,n sao cho x = 3 3m2+6n−61 +4 là số nguyên tố. Lời giải. Ta có 3m2 +6n−61 = 3k +2 . Nếu k > 1 ta có x = 3 3k+2 +4 = 9.27k +4 . . .13. Suy ra k = 0 hay 3m2 +6n−61 = 2 ⇔ m2 +2n−21 = 0. Vì m2 lẻ và m2 < 21 nên m2 = 1,m2 = 9. * m = 1 ⇒ n = 10. * m = 3 ⇒ n = 6. Bài tập 2.24. Tìm các số nguyên tố a,b, c sao cho ab + bc + ca > abc. Lời giải. Giả sử a 6 b 6 c. Ta có abc < ab + bc + ca < 3bc ⇒ a < 3 ⇒ a = 2. Khi đó 2bc < 2(b + c)+ bc ⇒ bc < 2(b + c) 6 4c ⇒ b 6 3 ⇒ b ∈ {2,3}. +) b = 2 ⇒ 2c < 2(2+ c) đúng với mọi c > 2, c nguyên tố. +) b = 3 ⇒ 3c < 2(3+ c) ⇒ c < 6 ⇒ c ∈ {3,5}. Bài tập 2.25. Tìm tất cả các số tự nhiên a,b, c sao cho a 3 + b 3 + c 3 −3abc là số nguyên tố. Nguyễn Tất Thu 30 Chương 2. Lý thuyết chia hết Lời giải. Không mất tính tổng quát, ta giả sử a > b > c. Ta có a 3 + b 3 + c 3 −3abc = (a+ b + c) ¡ a 2 + b 2 + c 2 − ab − bc − ca¢ . Do đó a 3 + b 3 + c 3 −3abc là số nguyên tố khi xảy ra một trong các trường hợp sau: • a+ b + c = 1 và a 2 + b 2 + c 2 − ab − bc − ca là số nguyên tố. Từ a+ b + c = 1 ⇒ a = 1,b = c = 0, khi đó a 3 + b 3 + c 3 −3abc = 1 không là số nguyên tố. • a 2 + b 2 + c 2 − ab − bc − ca = 1 và a+ b + c là số nguyên tố. Ta có a 2 + b 2 + c 2 − ab − bc − ca = 1 ⇔ (a− b) 2 +(b − c) 2 +(c − a) 2 = 2 Suy ra    a = b b − c = 1 c − a = −1 ⇔ ( a = b c = b −1 ⇒ a+ b + c = 3b −1 Hoặc    a− b = 1 b − c = 0 a− c = 1 ⇔ b = c = a−1. Vậy các số tự nhiên cần tìm là (k;k,k −1) với 3k −1 là số nguyên tố. Hoặc (k;k −1;k −1) với 3k −2 là số nguyên tố. Bài tập 2.26. Cho a,b, c là các số nguyên khác 0, a 6= c thỏa : a c = a 2 + b 2 c 2 + b 2 . Chứng minh rằng a 2 + b 2 + c 2 không phải là số nguyên tố. Lời giải. Đẳng thức a c = a 2+b 2 b 2+c 2 tương đương (a− c)(b 2 − ac) = 0. Vì a 6= c nên suy ra b 2 = ac. Khi đó: a 2 + b 2 + c 2 = a 2 + ac + c 2 = a 2 +2ac + c 2 − b 2 = (a+ c) 2 − b 2 = (a+ c − b)(a+ c + b) Dễ thấy a 2 + b 2 + c 2 > 3. Do đó nếu a 2 + b 2 + c 2 là số nguyên tố thì có 4 trường hợp có thể xảy ra. (1) a+ c − b = 1 và a+ b + c = a 2 + b 2 + c 2 (2) a+ c + b = 1 và a+ c − b = a 2 + b 2 + c 2 (3) a+ c − b = −1 và a+ b + c = −(a 2 + b 2 + c 2 ) (4) a+ c + b = −1 và a+ b + c = −(a 2 + b 2 + c 2 ). Ở hai trường hợp đầu ta có a 2 + b 2 + c 2 −2(a+ c)+1 = 0 Nguyễn Tất Thu 2.2. Số nguyên tố 31 hay (a−1)2 +(c −1)2 + b 2 = 1 ⇒ a = c = 1 (trái với giả thuyết) Ở hai trường hợp sau ta có (a+1)2+(c +1)2+b 2 = 1, suy ra a = c = −1 (trái với giả thuyết). Bài tập 2.27. Tìm ba số nguyên tố p, q, r thỏa p q + q p = r. Lời giải. Ta có r > 2 ⇒ r lẻ. Do đó p, q phải khác tính chẵn, lẻ nên trong hai số phải có một số bằng 2. Giả sử p = 2, khi đó 2 q + q 2 = r. +) q = 3 ⇒ r = 17 thỏa. +) q > 3. Vì q lẻ nên q 2 = 3k +1 và 2 q = 3l −1. Suy ra 2 q + q 2 = 3(k + l) là hợp số. Vậy (3;2;17) và (2;3;17) là hai bộ cần tìm. Bài tập 2.28. Chứng minh rằng nếu 1+2 n +4 n là số nguyên tố thì n = 3 k . Lời giải. Giả sử n = 3 k .m, (m,3) = 1,m > 1 và đặt a = 2 3 k , ta có 1+2 n +4 n = 1+ a m + a 2m. +) m = 3q +1, ta có 1+ a m + a 2m = 1+ a.a 3q + a 2 .a 6q = a 2 ¡ a 6q −1 ¢ + a ¡ a 3q −1 ¢ + a 2 + a+1 Vì a 3 −1 = (a−1) ¡ a 2 + a+1 ¢ ⇒ 1+ a m + a 2m là hợp số. +) m = 3q +2, ta có 1+ a m + a 2m = 1+ a 2 .a 3q + a 4 .a 6q = a 4 ¡ a 6q −1 ¢ + a 2 ¡ a 3q −1 ¢ + a 4 + a 2 +1 Vì a 3 −1 = (a−1) ¡ a 2 + a+1 ¢ và a 4 + a 2 +1 = ¡ a 2 + a+1 ¢ ¡a 2 − a+1 ¢ Nên 1+ a m + a 2m là hợp số. Do vậy n = 3 k . Bài tập 2.29. Cho p là số nguyên tố lẻ và hai số nguyên a,b thỏa p 4 là ước của hai số a 2+b 2 và a(a+ b) 2 . Chứng minh rằng p 4 là ước của a(a+ b). Lời giải. Ta có a(a+ b) 2 − a ¡ a 2 + b 2 ¢ = 2a 2 b . . .p 4 ⇒ a 2 b . . .p 4 Nguyễn Tất Thu 32 Chương 2. Lý thuyết chia hết Nếu ap thì b . . .p 4 ⇒ a 2 + b 2p 4 (vô lí). Suy ra a . . .p m ⇒ a(a+ b) 2 = p m ¡ p m + b ¢2. . .p 4 ⇒ m > 2 hay a . . .p 2 . Từ a 2 + b 2 . . .p 4 ⇒ b 2 . . .p 4 ⇒ b . . .p 2 . Từ đó, suy ra a(a+ b) . . .p 4 . Bài tập 2.30. Cho p, q là các số nguyên tố và phương trình x 2 − px+ q = 0 có nghiệm nguyên dương. Tìm p và q. Lời giải. Gọi x0 là nghiệm nguyên dương của phương trình x 2 − px + q = 0, ta có x0|q nên x0 = 1 hoặc x0 = q. • x0 = 1 ta có 1− p + q = 0 ⇔ p = q +1, suy ra q = 2, p = 3. • x0 = q ta có q 2 − pq + q = 0 ⇔ p = q +1, suy ra q = 2, p = 3. Bài tập 2.31. Chứng minh rằng nếu m có ít nhất một ước nguyên tố khác 3 thì 1+2 m +4 m là hợp số. Lời giải. Ta xét các trường hợp sau • m = 2k, ta có 1+2 m +4 m = 1+2 2k +2 4k = (22k +1)2 −2 2k = (22k +2 k +1)(22k −2 k +1) là hợp số. • m lẻ, ta có m = 3 n .k với (k,3) = 1 và k > 5. Khi đó 1+2 m +4 m = 1+ a k + a 2k với a = 2 3 n . +)k = 3t+1, khi đó a 2k + a k +1 = a 2 (a 6t −1)+ a(a 3t −1)+ a 2 + a+1. Vì a 3t −1 . . .a 3 −1 . . .a 2 + a+1 nên a 2k + a k +1 . . .a 2 + a+1. +) k = 3t+1, khi đó a 2k + a k +1 = a 4 (a 6t −1)+ a 2 (a 3t −1)+ a 4 + a 2 +1. Vì a 6t −1 . . .a 2 + a+1, a 3t −1 . . .a 2 + a+1 và a 4 + a 2 +1 . . .a 2 + a+1 nên a 2k + a k +1 . . .a 2 + a+1 Nguyễn Tất Thu 2.2. Số nguyên tố 33 Do vậy ta luôn có 1+2 m +4 m là hợp số. Bài tập 2.32. Cho T = ½ (x, y) | x, y ∈ N,0 6 2x < y 6 100, x 4 + y 4 . . .49¾ . Tìm |T|. Lời giải. Ta có x 4 + y 4 . . .49 nên suy ra x 4 + y 4 . . .7 hay    x 2 . . .7 y 2 . . .7 nên x, y . . .7. Do vậy x = 7x1, y = 7y1, suy ra 0 6 2x1 < y1 6 14. Đặt x1 = a,0 6 a 6 6. Với mỗi a ta có 14 − 2a giá trị của y1 nên số cặp (x1, y1) thỏa bài toán là X 6 a=0 (14−2a) = 2+4+6+...+14 = 56. Lời giải. Từ phương trình ta suy ra x, y khác tính chẵn, lẻ. Phương trình đã cho trở thành x 2 +1 = y 3 +8 = (y+2)(y 2 −2y+4). (1) Ta xét các trường hợp sau • y = 2k thì y 2 −2y+4 . . .4, nhưng x lẻ nên x 2 +1 6 . . .4. nên (1) vô nghiệm. • y = 4k +1, khi đó y+2 = 4k +2 là ước của x 2 +1 (vô lí). Nên trường hợp này (1) cũng vô nghiệm. • y = 4k +3, khi đó y 2 −2y+4 ≡ 9−2.6 ≡ 3 (mod 4) và là y 2 −2y+4 là ước của x 2 +1 (vô lí). Vậy phương trình đã cho vô nghiệm. Bài tập 2.33. Tìm các số nguyên tố a,b, c và số nguyên dương k sao cho a 2 + b 2 +16c 2 = 9k 2 +1. Lời giải. Từ phương trình ta suy ra a 2 + b 2 + c 2 ≡ 1 (mod 3). Suy ra,trong ba số a,b, c có hai số chia hết cho 3. • a = b = 3, ta có 18+16c 2 = 9k 2 +1 ⇔ (3k −4c)(3k +4c) = 17 Suy ra    3k +4c = 17 3k −4c = 1 ⇔    k = 3 c = 2 . Nguyễn Tất Thu 34 Chương 2. Lý thuyết chia hết • c = 3, không mất tính tổng quát, ta giả sử a = 3. Khi đó, ta có (3k − b)(3k + b) = 152 = 19.8 +)    3k + b = 19 3k − b = 8 vô nghiệm. +)    3k + b = 38 3k − b = 4 ⇔    k = 7 b = 17 . +)    3k + b = 76 3k − b = 2 ⇔    k = 13 b = 37 . +)    3k + b = 152 3k − b = 2 vô nghiệm. Bài tập 2.34. Chứng minh rằng không tồn tại số tự nhiên n để n 7 +7 là số chính phương. Bài tập 2.35. (Bulgaria MO 2014) Tìm các số nguyên tố p và q sao cho p 2 |q 3 +1 và q 2 |p 6 −1. Lời giải. Nếu p = 3, ta có q 2 |3 6 −1 = 2 3 .7.11 nên q = 2. Xét p 6= 3, ta có p 2 |(q +1)(q 2 − q +1). Mà (q+1, q 2 − q+1) = (q+1,3) = 1 hoặc 3. Suy ra hoặc p 2 |q+1 hoặc p 2 |q 2 − q+1.Từ đây, suy ra p < q. Nếu q = p +1 ta có p = 2, q = 3. Xét q > p +2. Vì q 2 |(p −1)(p +1)(p 2 + p +1)(p 2 − p +1). Do (q, p+1) = (q, p−1) = 1 và (p 2− p+1, p 2+ p+1) = (p 2+ p+1,2p) = 1 nên ta có hoặc q 2 |p 2+ p+1 hoặc q 2 |p 2 − p +1. Mà q > p +2 nên q 2 > (p +2)2 > p 2 + p +1 > p 2 − p +1. Suy ra q 2 6 |p 6 −1. Vậy (p, q) = (2,3); (3,2). 2.3 Ước chung lớn nhất - Bội chung nhỏ nhất 2.3.1 Ước chung lớn nhất Định nghĩa 2.3. Ước chung lớn nhất của hai số nguyên a và b không đồng thời bằng 0 là số nguyên lớn nhất chia hết a và b. Ta kí hiệu (a,b) hoặc gcd(a,b). Nếu (a,b) = 1thì ta gọi a và b là hai số nguyên tố cùng nhau. Nguyễn Tất Thu 2.3. Ước chung lớn nhất - Bội chung nhỏ nhất 35 Định nghĩa 2.4. Giả sử a1,a2,...,an là các số nguyên không đồng thời bằng 0. Ước chung lớn nhất của các số đó là số nguyên lớn nhất mà là ước của các số đã cho. Ta kí hiệu (a1,a2,...,an) hoăc gcd(a1,a2,...,an) Nếu (a1,a2,...,an) = 1 ta nói các số đó nguyên tố cùng nhau. Các số đã cho được gọi là đôi một nguyên tố cùng nhau nếu (ai ,aj) = 1 với mọi i 6= j. Nhận xét. Từ định nghĩa ta có các nhận xét sau: 1. Nếu d = (a,b) thì µ a d , b d ¶ = 1. 2. (a+ bc,b) = (a,b). 3. (a1,a2,...,an) = (a1,a2,...,an−2,(an−1,an)) 4. Nếu ab. . .c và (b, c) = 1 thì a . . .c. ♦ Định lí 2.5. Cho d = (a,b). Khi đó d là số nguyên dương nhỏ nhất biểu diễn được một tổ hợp tuyến tính của a và b. Tức là tồn tại hai số nguyên x, y để d = ax+ b y. Chứng minh. Đặt A = {ax + b y > 0|x, y ∈ Z, ta có A 6= ∅ vì (−1)a0b ∈ A và 1.a +0.b ∈ A. Do đó A sẽ có phần tử nhỏ nhất, gọi d là phần tử nhỏ nhất đó. Ta chứng minh d là ước của a và b. Giả sử a = dq+r, ta có r = a−dq = a− q(ax+b y) = (1− qx)a− qb y, suy ra r cũng biểu diễn được qua tổ hợp tuyến tính của a và b. Mà 0 6 r < d nên ta có r = 0, hay d|a. Chứng minh tương tự, ta cũng có d|b. Vì d = ax+ b y nên ta thấy d chia hết cho tất cả các ước chung của a và b. Định lí 2.6. (Thuật toán Ơ-clít) Giả sử r0 = a, r1 = b là các số nguyên không âm, b 6= 0. Ta áp dụng liên tiếp thuật toán chia ri = ri+1qi+1 + ri+2 với 0 < ri+2 < ri+1 với i = 0,1,...,n−2, rn = 0. Khi đó (a,b) = rn−1. Để chứng minh định lí này ta dựa vào nhận xét trên và thuật toán chia. 2.3.2 Bội chung nhỏ nhất Định nghĩa 2.5. Bội chung nhỏ nhất của hai số nguyên a và b khác 0 là số nguyên dương nhỏ nhất chia hết cho cả a và b. Kí hiệu [a,b] hoặc lcm(a,b). Tương tự ta có thể định nghĩa bội chung nhỏ nhất cho n số nguyên a1,a2,...,an khác 0 là số nguyên dương nhỏ nhất chia hết cho tất cả n số đó. Kí hiệu [a1,a2,...,an]. Nguyễn Tất Thu 36 Chương 2. Lý thuyết chia hết Nhận xét. Cho các số nguyên a,b, c,k khác 0. Ta có 1. [ka,kb] = k[a,b] 2. [a,b, c] = [[a,b], c] 3. [a,b].(a,b) = ab 4. Nếu a . . .b và a . . .c thì a . . .[b, c]. ♦ 2.3.3 Định lí cơ bản của số học Định lí 2.7. Mọi số nguyên n > 1 đều biểu diễn được dưới dạng tích của các số nguyên tố. Phân tích này là duy nhất nếu không tính thứ tự của các thừa số. Chứng minh. Ta chứng minh tồn tại biểu diễn bằng qui nạp. Với n = 2, n = 3, n = 4 = 2.2, n = 5, n = 6 = 2.3 đều biểu diễn dưới dạng tích các số nguyên tố. Giả sử khẳng định đúng đến n–1, tức mọi số nguyên không vượt quá n–1 đều biểu diễn được dưới dạng tích các số nguyên tố. Xét số nguyên n. Nếu n nguyên tố ta có ngay điều chứng minh. Nếu n là hợp số thì n = n1.n2 (1 < n1, n2 < n), từ giả thiết qui nạp ta có n1, n2 đều biểu diễn được dưới dạng tích các số nguyên tố, như vậy n cũng biểu diễn được dưới dạng tích các số nguyên tố. Để chứng minh biểu diễn trên là duy nhất, ta dựa vào bổ đề sau: Bổ đề: Nếu p là số nguyên tố và p|ab thì p|a hoặc p|b. Ta chứng minh biểu diễn duy nhất. Giả sử tồn tại số nguyên dương có ít nhất hai cách biểu diễn khác nhau, trong các số như vậy ta xét n là số nhỏ nhất. Ta có n = p1p2 ... pr = q1q2 ... qs với p1 6 p2 6 ... 6 pr và q1 6 q2 6 ... 6 qs là các số nguyên tố. Giả sử p1 6 q1. Khi đó p1|q1q2 ... qs, suy ra tồn tại i để p1|qi hay p1 = qi nên qi là q1. Xét n p1 = p2 ... pr = q2 ... qs. Do n p1 < n nên n p1 có một cách phân tích suy nhất. Do đó n cũng có một cách phân tích duy nhất. Điều này mẫu thuẫn với điều giả sử ở trên. Vậy định lí được chứng minh. Như vậy với mọi số nguyên dương n thì ta luôn phân tích được n = p α1 1 .p α2 2 .....p αk k trong đó pi ,i = 1,k là các số nguyên tố phân biệt và αi là các số nguyên dương. Nguyễn Tất Thu 2.3. Ước chung lớn nhất - Bội chung nhỏ nhất 37 Nhận xét. Giả sử a = p α1 1 .p α2 2 .....p αk k và b = p β1 1 .p β2 2 .....p βk k . với αi và βi là các số tự nhiên, pi là các số nguyên tố phân biệt. Khi đó 1. (a,b) = p min{α1,β1} 1 .p min{α2,β2} 2 .....p min{αk,βk} k 2. [a,b] = p max{α1,β1} 1 .p max{α2,β2} 2 .....p max{αk,βk} k 3. a . . .b ⇔ αi > βi với mọi i = 1,k 4. a có (α1 +1)(α2 +1)...(αk +1) ước nguyên dương khác nhau. ♦ Định lí 2.8. Trong sự phân tích số n! ra thừa số nguyên tố n! = p α1 1 p α2 2 ... p αk k ,αi > 0 thì số mũ αi của pi nào đó sẽ là αi = • n pi ¸ + " n p 2 i # +...+ " n p k i # với n < p k+1 . Chứng minh. Giả sử p là một ước của n!. Ta có n! = 1.2... p.(p +1)...2p...3p....• n p ¸ p...n = p " n p # • n p ¸ !q = p m.m!q với m = • n p ¸ và (p, q) = 1 Tương tự m! = p "m p # • m p ¸ !q 0 với (p, q 0 ) = 1. Suy ra n! = p " n p # p "m p # • m p ¸ !qq0 = p " n p # + " n p 2 # • n p 2 ¸ !qq0 với (p, qq0 ) = 1. Cứ tiếp tục như thế ta thu được số mũ của p: α = • n p ¸ + • n p 2 ¸ +...+ • n p k ¸ . Nguyễn Tất Thu 38 Chương 2. Lý thuyết chia hết Ví dụ 2.20. Chứng minh rằng (a 2 ,b 2 ) = (a,b) 2 . Lời giải. Đặt (a,b) = d, khi đó µ a d , b d ¶ = 1. Suy ra µ a 2 d 2 , b 2 d 2 ¶2 = 1 nên (a 2 ,b 2 ) = d 2 = (a,b) 2 Ví dụ 2.21. Tìm (a+ b,a 2 + b 2 với a,b là hai số nguyên tố cùng nhau. Lời giải. Ta có (a+ b,a 2 + b 2 ) = (a+ b,(a+ b) 2 −2ab) = (a+ b,2ab) = (a+ b,2) do (a+ b,ab) = (a+ b,a(a+ b)− a 2 ) = (a+ b,a 2 ) = (b,a 2 ) = 1. Suy ra (a+ b,a 2 + b 2 ) = 1 hoặc 2. Ví dụ 2.22. Cho hai số nguyên a,b nguyên tố cùng nhau. Tìm ¡ a+ b,a 2 − ab + b 2 ¢ . Lời giải. Đặt d = ¡ a+ b,a 2 − ab + b 2 ¢ , khi đó d là ước của (a+ b) 2 − a 2 + ab − b 2 = 3ab. Suy ra ( d|3b(a+ b)−3ab = 3b 2 d|3a(a+ b)−3ab = 3a 2 ⇒ d ¯ ¯ ¡ 3a 2 ,3b 2 ¢ = 3 ¡ a 2 ,b 2 ¢ = 3 . Suy ra d = 1,d = 3. Ví dụ 2.23. Cho a,a 6= 1 và m,n là các số nguyên dương. Chứng minh rằng ¡ a m −1,a n −1 ¢ = a (m,n) −1. Lời giải. Đặt d = (m,n) ⇒ m = d.s, n = d.p. Khi đó a m −1 = a d.s −1 . . .a d −1 và a n −1 = a d.p −1 . . .a d −1 Do đó a d −1 ¯ ¯ ¡ a m −1,a n −1 ¢ (1). Theo định lí Bơzu, ta có mx+ n y = d với x, y ∈ Z. Vì d 6 m,d 6 n nên x, y không thể cùng là số nguyên dương. Ta giả sử x > 0, y 6 0. Đặt t = (a m −1,a n −1). Suy ra t ¯ ¯a mx −1 , t ¯ ¯a −n y −1 ⇒ t ¯ ¯ ¯a mx −1− a d ¡ a −n y −1 ¢ = a d −1 (2). Từ (1) và (2) ta có đpcm. Nguyễn Tất Thu 2.3. Ước chung lớn nhất - Bội chung nhỏ nhất 39 Ví dụ 2.24. Chứng minh rằng nếu m,n là các số tự nhiên và m lẻ thì ¡ 2 m −1,2 n +1 ¢ = 1. Lời giải. Đặt d = ¡ 2 m −1,2 n +1 ¢ ⇒ 2 m −1 = ad,2 n +1 = bd Suy ra 2 mn = (ad +1) n = kd +1, 2 mn = (bd −1) m = td −1 Do đó: kd +1 = td −1 ⇔ d(k − t) = 2 ⇒ 2 . . .d. Mà d lẻ nên ta có d = 1. Ví dụ 2.25. Chứng minh rằng a.(a,b, c) > (a,b).(a, c). Lời giải. Đặt d1 = (a, c); d2 = (a, c) Ví dụ 2.26. Cho n là số nguyên dương và đặt an = n(n+1) 2 . Chứng minh rằng trong dãy các số a1,a2,...,an,... tồn tại vô hạn các số đôi một nguyên tố cùng nhau. Lời giải. Ta có a1 = 1,a2 = 3,a4 = 10 là các số đôi một nguyên tố cùng nhau. Giả sử ta đã tìm được m số t1,t2,...,tm đôi một nguyên tố cùng nhau. Đặt t = t1t2...tm. Ta xét a2t+1 = (t+1)(2t+1). Vì (2t+1;t) = (t+1;t) = 1 nên (a2t+1;t) = 1 ⇒ (a2t+1;ti) = 1 với i = 1,2,...,m. Và a2t+1 > t, suy ra dãy t1,t2,...,tm,a2t+1 gồm các số đôi một nguyên tố cùng nhau. Ví dụ 2.27. Cho các số nguyên dương a,bthỏa a+1 b + b +1 a là số nguyên, đặt d = (a;b). Chứng minh rằng d 6 p a+ b. Lời giải. Ta có a = md,b = nc, khi đó a+1 b + b +1 a = md +1 nd + nd +1 md = (m2 + n 2 )d + m+ n mnd là số nguyên. Suy ra m+ n . . .d ⇒ d 6 m+ n ⇒ d 6 p d(m+ n) = p a+ b. Nguyễn Tất Thu 40 Chương 2. Lý thuyết chia hết Ví dụ 2.28. Tìm các số nguyên dương a,b, c sao cho a 3 + b 3 + c 3 chia hết cho a 2b, b 2 c và c 2a. Lời giải. Gọi d = (a;b), suy ra a 3 + b 3 + c 3 . . .d 3 ⇒ c . . .d hay d = (a,b, c). Xét bộ (x; y; z) = µ a d ; b d ; c d ¶ ⇒ x, y, z đôi một nguyên tố cùng nhau và bộ (x; y; z) thỏa bài toán. Vì x 3 + y 3 + z 3 . . .x 2 , y 2 , z 2 ⇒ x 3 + y 3 + z 3 . . .x 2 y 2 z 2 Giả sử x > y > z. Khi đó 3x 3 > x 3 + y 3 + z 3 > x 2 y 2 z 2 ⇒ y 2 z 2 6 3x ⇒ x > y 2 z 2 3 . Mặt khác y 3 + z 3 . . .x 2 ⇒ 2y 3 > y 3 + z 3 > x 2 > y 4 z 4 9 ⇒ yz4 6 18 +) z = 2 ⇒ 16y 6 18 ⇒ y = 1 vô lí. +) z = 1, ta thấy x = y = 1 là một bộ thỏa bài toán. Xét y > 2, khi đó 2x 3 > x 3 + y 3 +1 > x 2 y 2 ⇒ x > y 2 2 Mà y 3 +1 . . .x 2 ⇒ y 3 +1 > x 2 > y 4 4 ⇒ y 6 4. Kiểm tra ta thấy chỉ có x = 3, y = 2 thỏa bài toán. Vậy (a,b, c) ∈ {(k;k;k), (3k,2k,k)}. Bài tập 2.36. Cho (a,b) = 1. Tìm 1. (3a+5b,8a+13b) 2. (a+ b,a− b) 3. (18a+5b,11a+3b) 4. ¡ a 2 + b 2 ,a 3 + b 3 ¢ . Lời giải. 1) Ta có (3a+5b,8a+13b) = (3a+5b,a+2b) = (b,a+2b) = (b,a) = 1. 2) Ta có (a+ b,a− b) = (a+ b,2b) = 2 hoặc 1. 3) Ta có (18a+5b,11a+3b) = (4a+ b,11a+3b) = (4a+ b,a) = (b,a) = 1. 4) Ta có (a+ b)(a 2 + b 2 ) = a 3 + b 3 + a 2b + b 2a nên: d = (a 2 + b 2 ,a 3 + b 3 ) = (a 2 + b 2 ,ab2 + a 2 b) = ¡ (a+ b) 2 −2ab,ab(a+ b) ¢ Vì (ab,a+ b) = (a 2 ,a+ b) = (a 2 ,b) = 1 nên d|ab hoặc d|a+ b. +) d|ab, suy ra d|a hoặc d|b. Mà d|(a+ b) 2 nên d = 1. +) d|a+ b, suy ra d|2ab nên d = 1 hoặc d = 2. Bài tập 2.37. Chứng minh rằng các phân số sau là tối giản Nguyễn Tất Thu 2.3. Ước chung lớn nhất - Bội chung nhỏ nhất 41 1. 21n+4 14n+3 2. 3n+2 8n+5 . Lời giải. 1) Ta có 3(14n+3)−2(21n+4) = 1 nên nếu d = (14n+3,21n+4) thì d|1 hay d = 1. Vậy 21n+4 14n+3 là phân số tối giản. 2) Ta có 8(3n+2)−3(8n+5) = 1 nên 3n+2 8n+5 là phân số tối giản. Bài tập 2.38. Tìm các số nguyên dương a,b biết 1. a+ b = 128 và (a,b) = 16 2. (a,b) = 12 và [a,b] = 432. Lời giải. 1) Ta có a = 16a1, b = 16b1, (a1,b1) = 1 và a1 + b1 = 8. Do đó, ta tìm được các cặp (a,b) là (16,112), (48,80), (112,16), (80,48). 2) Ta có a = 12a1, b = 12b1, (a1,b1) = 1 và ab = (a,b).[a,b] = 12.432. Suy ra a1b1 = 36 = 1.36 = 4.9. Từ đó, ta tìm được (a,b) = (12,432), (48,108), (432,12), (108,48). Bài tập 2.39. Chứng minh rằng dãy an = 2 n −3 với n > 3 chứa vô hạn cặp số nguyên tố cùng nhau. Lời giải. Ta có a2n = 2 2n −3 = ¡ 2 n −3 ¢ ¡2 n +3 ¢ +6 = ¡ 2 n +3 ¢ an +6. Suy ra (a2n,an) = (an,6) = 1. Bài tập 2.40. Chứng minh rằng dãy Mersen Mn = 2 n − 1, n ∈ N ∗ chứa vô hạn số hạng đôi một nguyên tố cùng nhau. Lời giải. Bài tập 2.41. Chứng minh rằng dãy Fermat Fn = 2 2 n + 1 là dãy có các số hạng nguyên tố cùng nhau. Bài tập 2.42. (Anbania TST 2012 Tìm các cặp số tự nhiên (a;b) không nguyên tố cùng nhau thỏa mãn (a,b)+9[a,b]+9(a+ b) = 7ab. Lời giải. Đặt d = (a,b) ta có a = dx,b = d y với (x, y) = 1, d > 1. Ta có [a,b] = dx y nên 1+9x y+9(x+ y) = 7dx y Suy ra 7dx y 6 x y+9x y+9(x y+ x y) = 28x y ⇒ 2 6 d 6 4. Nguyễn Tất Thu • d = 2 ta có 9(x+ y)+1 = 5x y ⇔ x = 2, y = 19. Suy ra (a,b) = (4,38). • d = 3 ta có 1+9(x+ y) = 12x y tường hợp này vô nghiệm. • d = 4 ta có x = y = 1 hay a = b = 4. Vậy (a,b) = (4,38), (38,4), (4,4). Bài tập 2.43. (Germany 2008) Cho a,b, c là các số nguyên dương thỏa mãn a + b|ab và a+ c|ac. Chứng minh rằng (a,b, c) > 1 Bài tập 2.44. Tìm tất cả các bộ 3 số nguyên dương {m,n,l} thỏa    m+ n = (m,n) 2 m+ l = (m,l) 2 n+ l = (n,l) 2 Bài tập 2.45. (Baltic Way 2014) Cho m,n là các số nguyên dương và nguyên tố cùng nhau. Xác định các giá trị có thể có của (2m −2 n ,2 m2+mn+n 2 −1). Bài tập 2.46. (1998 Indian MO) Tìm các số nguyên dương (x, y,n) thỏa (x,n+1) = 1 và x n +1 = y n+1 . Bài tập 2.47. Cho dãy các số tự nhiên a1,a2,... thỏa mãn (ai ,aj) = (i, j) ∀i 6= j. Chứng minh rằng ai = i với mọi i. Bài tập 2.48. Tìm ước chung lớn nhất của các số an = 2 3n +3 6n+2 +5 6n+2 với n = 0,1,2,...,1999. (2001 Junior Balkan Olympic toán) Bài tập 2.49. Chứng minh rằng [1,2,...,n] = [n+1,n+2,...,2n]. Bài tập 2.50. Cho các số nguyên dương lẻ a1,a2,...,an. Chứng minh rằng (a1,a2,...,an) = ³a1 + a2 2 , a2 + a3 2 ,..., an + a1 2 ´ . Bài tập 2.51. Cho n là số nguyên dương chẵn và a,b là hai số nguyên dương và nguyên tố cùng nhau. Tìm a,b biết a+ b là ước của a n + b n . Chương 3 Lý thuyết đồng dư 3.1 Các khái niệm cơ bản Định nghĩa 3.1. Cho a, b, m là các số nguyên, m 6= 0. Nếu a–b chia hết cho m thì a được gọi là đồng dư với b modulo m, ký hiệu a ≡ b (mod m). Trong trường hợp ngược lại, ta kí hiệu a 6≡ b (mod m). Vậy a ≡ b (mod m) ⇔ a = b + km với k ∈ Z. Định lí 3.1. Cho a,b, c,d là các số nguyên, khi đó ta có các tính chất sau: 1. Nếu a ≡ b (mod m) thì b ≡ a (mod m) 2. Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m) 3. Nếu a ≡ b (mod m) và c ≡ d (mod m) thì a+ c ≡ b + d (mod m) 4. Nếu a ≡ b (mod m) và c ≡ d (mod m) thì ac ≡ bd (mod m). Chứng minh. Ta chứng minh tính chất thứ 3 và 4. Ta có a ≡ b (mod m) và c ≡ d (mod m) nên a = b + km và c = d + tm, k,t ∈ Z. 3. Suy ra a+ c = b + d +(k + t)m ⇒ a+ c ≡ b + d (mod m). 4. Suy ra ac = (b + km)(d + tm) = bd +(bt+ kd)m+ ktm2 Do đó ac ≡ bd (mod m). Định lí 3.2. Cho các số nguyên a,b. Khi đó: 1. Nếu a ≡ b (mod m), k nguyên dương thì a k ≡ b k (mod m) 43 44 Chương 3. Lý thuyết đồng dư 2. Nếu a ≡ b (mod m) và d|m thì a ≡ b (mod d) 3. Nếu a ≡ b (mod m) thì ac ≡ bc (mod cm) với mọi c 6= 0. 4. Nếu ab ≡ ac (mod m) và (a,m) = d thì b ≡ c (mod m d ) Chứng minh. Ta chứng minh tính chất 4. Đặt a = da1, m = dm1 với (a1,m1) = 1. Ta có ab − ac = da1(b − c) . . .m = dm1 ⇒ a1(b − c) . . .m1 Do (a1,m1) = 1 nên suy ra b − c . . .m1 hay b ≡ c (mod m1). Định nghĩa 3.2. Cho số nguyên m, tập a = {b|b ≡ a (mod m)} được gọi là một lớp đồng dư môđunlô m. Do vậy, ta chia các số nguyên thành m lớp theo môđunlô m là {0,1,...m−1}. Định lí 3.3. Cho các số nguyên a,b. Khi đó: 1. Nếu a ≡ b (mod mi) với ( i = 1,2,...,n) thì a ≡ b (mod [m1,m2,...,mn]) 2. Cho P(x) là đa thức hệ số nguyên, khi đó nếu a ≡ b (mod m) thì P(a) ≡ P(b) (mod m). Chứng minh. 1. Ta có a− b . . .m1, a− b . . .m2, ..., a− b . . .mn nên a− b . . .[m1,m2,...,mn]. Hay a ≡ b (mod [m1,m2,...,mn]). 2. Giả sử P(x) = anx n + an−1x n−1 +...+ a1x+ a0 với ai ∈ Z. Khi đó P(a)− P(b) = Xn i=1 ai(a i − b i ). Vì a i − b i ≡ a− b ≡ 0 (mod m) nên ta có P(a)− P(b) ≡ 0 (mod m). Ví dụ 3.1. Tìm số dự của phép chia 6 2015 cho 37. Lời giải. Ta có 6 2 ≡ −1 (mod 37) nên ta có 6 2015 = 6.(62 ) 1007 ≡ 6(−1)1007 ≡ −6 (mod 37) Vậy số dư trong phép chia 6 2015 cho 37 là 31. Ví dụ 3.2. Chứng minh rằng 641|2 32 +1. Nguyễn Tất Thu 3.1. Các khái niệm cơ bản 45 Lời giải. Ta có 641 = 5.2 7 +1 = 2 4 +5 4 . Do đó, ta suy ra 5.2 7 ≡ −1 (mod 641) và 5 4 ≡ −2 4 (mod 641) Suy ra 5 4 .2 28 ≡ 1 (mod 641) hay −2 4 .2 28 ≡ 1 (mod 641). Vậy 641 ¯ ¯2 32 +1. Ví dụ 3.3. Tìm chữ số tận cùng của 7 7 7 . Lời giải. Ta có 7 7 ≡ −1 (mod 4) nên 7 7 = 4k +3. Khi đó 7 7 7 = 7 4k+3 = (72 ) 2k+1 .7 ≡ (−1)2k+1 .7 ≡ −7 (mod 10) Vậy chữ số tận cùng của 7 7 7 là 3. Ví dụ 3.4. Chứng minh rằng với mọi n là số tự nhiên thì 133 ¯ ¯11n+2 +122n+1 . Lời giải. Ta có 11n+2 +122n+1 = 133.11n +12¡ 144n −11n ¢ . Mà 144n −11n ≡ 144−11 ≡ 133 ≡ 0 (mod 133) nên ta suy ra 133 ¯ ¯11n+2 +122n+1 . Ví dụ 3.5. Chứng minh rằng 19.8 n +17 luôn là hợp số với mọi số tự nhiên n. Lời giải. Ta xét các trường hợp sau • n = 2k, khi đó 19.8 n +17 ≡ 1.(−1)2k +2 ≡ 3 ≡ 0 (mod 3) Hay 19.8 n +17 . . .3. • n = 4k +1, ta có 19.8 n +17 = 19.8 4k+1 +17 = 19.8.642k +17 ≡ 6.8.(−1)2k +17 ≡ 9+17 ≡ 26 ≡ 0 (mod 13) Suy ra 19.8 n +17 . . .13. Nguyễn Tất Thu 46 Chương 3. Lý thuyết đồng dư • n = 4k +3, tuong tự ta có 19.8 n +17 . . .5. Và do 19.8 n +17 > 36 nên 19.8 n +17 là hợp số. Ví dụ 3.6. Cho p là số nguyên tố và {r1, r2,..., rm} là dãy tăng gồm các số nguyên dương thỏa r m i ≡ 1 (mod p) với i = 1,2,...,m. Chứng minh rằng x m −1 ≡ (x− r1)(x− r2)...(x− rm) (mod p) với mọi x ∈ Z. Lời giải. Ta có f (x) = x m −1 = Xm i=1 ai(x− r1)(x− r2)...(x− ri)+ a0. Ta có am = 1. Vì f (ri) = r m i −1 ≡ 0 (mod p) với mọi i = 0,1,...,m−1 nên ta suy ra ai ≡ 0 (mod p) với mọi i = 0,1,...,m−1. Vậy x m −1 ≡ (x− r1)(x− r2)...(x− rm) (mod p). Ví dụ 3.7. Cho các số nguyên a,b, c thỏa mãn 9 ¯ ¯a 2 + b 2 + c 2 . Chứng minh rằng 9 ¯ ¯ (a 2 − b 2 )(b 2 − c 2 )(c 2 − a 2 ). Lời giải. Xét số nguyên n. • Nếu n = 9k thì n 2 ≡ 0 (mod 9) • Nếu n = 9k ±1 thì n 2 ≡ 1 (mod 9) • Nếu n = 9k ±2 thì n 2 ≡ 4 (mod 9) • Nếu n = 9k ±3 thì n 2 ≡ 0 (mod 9) • Nếu n = 9k ±4 thì n 2 ≡ 7 (mod 9) Đặt a 2 ≡ r1 (mod 9), b 2 ≡ r2 (mod 9), c 2 ≡ r3 (mod 9), ta có r1, r2, r3 ∈ {0,1,4,7}. Do đó a 2 + b 2 + c 2 . . .9 nên r1 + r2 + r3 ≡ 0 (mod 9). Do đó, ta có các trường hợp sau: • r1 = r2 = r3 = 0. • Trong ba số r1, r2, r3 có một số bằng 1 và hai số bằng 4. • Trong ba số r1, r2, r3 có một số bằng 7 và hai số bằng 1. • Trong ba số r1, r2, r3 có một số bằng 4 và hai số bằng 7. Tất cả các trường hợp trên ta đều suy ra 9 ¯ ¯ (a 2 − b 2 )(b 2 − c 2 )(c 2 − a 2 ). Bài tập 3.1. Chứng minh rằng Nguyễn Tất Thu 3.1. Các khái niệm cơ bản 47 1. 5 8 2004 +23 . . .24 2. 6 2n +10.3 n . . .11 3. 5 2n+1 .2 n+2 +3 n+2 .2 2n+1 . . .19 4. 2 2n +15n−1 . . .9. Bài tập 3.2. Cho n,k là các số tự nhiên. Chứng minh rằng 2n+1 ¯ ¯1 2k+1 +2 2k+1 +...+(2n) 2k+1 . Bài tập 3.3. Chứng minh rằng 222555 +555222. . .7. Bài tập 3.4. Chứng minh rằng 333222 +222333. . .13. Bài tập 3.5. Chứng minh rằng 11101967 −1 . . .101968 . Bài tập 3.6. Tìm chữ số hàng đơn vị của số 141414 . Bài tập 3.7. Tìm chữ số hàng đơn vị của số 777777 . Bài tập 3.8. Chứng minh rằng 103n+1 không thể phân tích thành tổng của 3 số lập phương. Bài tập 3.9. Cho 11 sô nguyên dương a1, a2, ..., a11. Chứng minh rằng luôn tôn tại các sô xi ∈ −1,0,1 , i = 1,2,...,11 không đồng thời bằng 0 sao cho: x1a1 + x2a2 + ... + x11a11 chia hêt cho 2047. Bài tập 3.10. (Nga 2000) Tìm các số nguyên tố p và q sao cho p + q = (p − q) 3 . Bài tập 3.11. Cho a là số nguyên dương lẻ. Chứng minh rằng ³ a 2 n +2 2 n ,a 2 m +2 2 m ´ = 1 với m 6= n là các số nguyên. Bài tập 3.12. Tìm các số nguyên dương n để 7 2000|5 n +1. Bài tập 3.13. Tìm các số nguyên dương x, y, z thỏa mãn 2 x .3 y +1 = 17z . Bài tập 3.14. Chứng minh rằng nếu 9|a 3 + b 3 + c 3 thì 3|abc. Nguyễn Tất Thu 48 Chương 3. Lý thuyết đồng dư 3.2 Định lí Fermat nhỏ - Định lí Wilson 3.2.1 Đồng dư tuyến tính Định nghĩa 3.3. Cho các số nguyên a,b,m. Khi đó phương trình ax ≡ b (mod m) (1) được gọi là phương trình đồng dư tuyến tính. Định lí 3.4. Cho a,b,m là các số nguyên, m > 0 và (a,m) = d. Khi đó • Nếu d 6 | b thì (1) vô nghiệm. • Nếu d|b thì (1) có đúng d nghiệm không đồng dư môđunlô m. Chứng minh. Số nguyên x là nghiệm của (1) khi và chỉ khi tồn tại số nguyên y sao cho ax− m y = b (2) Do đó, nếu d 6 | b thì (2) vô nghiệm. Xét d|b. Vì (a,m) = d nên tồn tại các số nguyên s,t sao cho d = at+ ms. Mà d|b nên b = ud = a(ut)+(us)m. Do đó x0 = ut là một nghiệm của (1). Ta chứng minh x = x0 + m d .k (3) với k ∈ Z đều là nghiệm của (1). Thật vậy ax ≡ ax0 + m a d k ≡ b (mod m). Ngược lại, mọi nghiệm của (1) đều có dạng (3). Gọi x là nghiệm của (1), ta có ax− m y = b ⇔ a(x− ut) = m(y− us) ⇔ a d (x− ut) = m d (y− us). Do ³ a d , m d ´ = 1 nên m d ¯ ¯x− ut hay x = ut+ m d k với k ∈ Z. Ta chứng minh được (1) có đúng d nghiệm không đồng dư theo môđunlô m. Ví dụ 3.8. Giải phương trình 3x ≡ 5 (mod 7). Lời giải. Ta có (3,7) = 1 nên phương trình luôn có nghiệm.Ta thấy x = 4 là một nghiệm của phương trình. Do đó, nghiệm của phương trình đã cho là x = 4+7t,t ∈ Z. Nhận xét. Nếu (a,m) = 1 thì phương trình ax ≡ 1 (mod m) luôn có nghiệm. Nghiệm đó được gọi là nghịch đảo của a thỏa môđunlô m. ♦ Nguyễn Tất Thu 3.3 Định lí Phecma nhỏ Định lí 3.5. Giả sử p là số nguyên tố và a là số nguyên dương mà p 6 | a. Khi đó, ta có a p−1 ≡ 1 (mod p). Chứng minh. Xét các số a,2a,3a,...,(p−1)a. Ta thấy,trong dãy số trên không có số nào chia hết cho p và không có hai số nào có cùng số dư khi chia cho p. Do đó, tập các số dư khi chia cho p của các số trên là tập {1,2,3,..., p −1}. Suy ra a.2a.3a.....(p −1)a ≡ 1.2.3.....(p −1) (mod p). Hay (p −1)!.a p−1 ≡ (p −1)! (mod p). Mà ((p −1)!, p) = 1 nên ta có a p−1 ≡ 1 (mod p). Nhận xét. Cho số nguyên tố p và số nguyên a. Khi đó a p ≡ a (mod p). ♦ Ví dụ 3.9. Chứng minh rằng 2 340 ≡ 1 (mod 341). Lời giải. Ta có 341 = 11.31 Theo định lí Phecma nhỏ thì 2 10 −1 . . .11 nên 2 340 −1 . . .11. Mặt khác, cũng theo định lí Phecma thì 2 31 ≡ 2 (mod 31) nên 2 341 = (231) 11 ≡ 2 11 ≡ 2.2 10 ≡ 2 (mod 31) Mà (2,31) = 1 nên 2 340 ≡ 1 (mod 31). Từ đó, suy ra 2 340 ≡ 1 (mod 341). Chú ý 3.1. Tương tự như cách chứng minh bài toán trên, ta có kết quả tổng quát sau: Cho hai số nguyên tố phân biệt p và q. Nếu a p ≡ a (mod q) và a q ≡ a (mod p) thì a pq ≡ a (mod pq).

Dành cho gia sư

Cập nhật hồ sơ gia sư

Cách lấy mã số gia sư