Chứng minh chia hết bằng phương pháp phân tích ra thừa số nguyên tố

A. Chứng minh chia hết bằng phương pháp phân tích ra thừa số nguyên tố 1. Giới thiệu Một trong những định lý quan trọng nhất của số học là định lý về phân tích một số tự nhiên ra thừa số nguyên tố. Định lý này được coi là nền tảng để nghiên cứu Lý thuyết số. Định lý cơ bản của số học. Mỗi số tự nhiên đều có thể biểu diễn duy nhất (nếu không tính đến thứ tự các thừa số) dưới dạng trong đó là các số nguyên tố Tiếp theo, ta đưa ra các mệnh đề có ý nghĩa và ứng dụng trong việc giải bài toán chia hết. Việc chứng minh các mệnh đề này có thể tìm thấy trong [1], [2]. Mệnh đề 1. Nếu hai số nguyên a và b cùng chia hết cho m thì a + b chia hết cho m, a - b chia hết cho m. Hệ quả 2. Nếu tổng của hai số chia hết cho m và một trong hai số ấy chia hết cho m thì số còn lại cũng chia hết cho m. Mệnh đề 3. Nếu một thừa số của một tích chia hết cho m thì tích chia hết cho m. Mệnh đề 4. Nếu a chia hết cho m và b chia hết cho n thì ab chia hết cho mn. Mệnh đề 5. Nếu số nguyên tố p thì . Mệnh đề 6. Nếu a chia hết cho 2 số nguyên tố cùng nhau m và n thì a chia hết cho tích mn. Mệnh đề 7. Nếu tích ab chia hết cho m trong đó b và m là hai số nguyên tố cùng nhau thì a chia hết cho m. 2. Sử dụng phương pháp phân tích ra thừa số nguyên tố để giải bài toán chia hết Dạng 1. Phân tích A thành tổng các số hạng Sử dụng tính chất chia hết của tổng (hoặc hiệu) và hệ quả: Nếu A = A1 + A2 + A3 + ... +An và thoả mãn điều kiện Ai ("i = ) thì A. Bài toán 1.Chứng minh rằng i) chia hết cho 11; ii) chia hết cho 9 với . Lời giải.i) , chia hết cho 11. ii) chia hết cho 9. Bài toán 2. Cho số chia hết cho 27.Chứng minh rằng số chia hết cho 27. Lời giải. Ta có Do nên Dạng 2. Phân tích A thành tích Sử dụng tính chất chia hết của tích: Nếu một thừa số của tích chia hết cho B thì tích chia hết cho B. Tức là: Nếu A = A1.A2.A3....An và () thì. Nếu A = A1.A2.A3....An và B = B1.B2.B3....Bn mà thì . Bài toán 3.Cho số tự nhiên .Chứng minh: chia hết cho tổng của n số tự nhiên đầu tiên Lời giải. Ta có: Mặt khác, sử dụng tính chất và n lẻ, Ta có Thêm vào đó, do ta suy ra: Tổng quát,ta có thể chứng minh được: chia hết cho 1+ 2 +…+ n, với mọi và k lẻ. Bài toán 4. Chứng minh rằng tích của ba số chẵn liên tiếp thì chia hết cho 48. Lời giải. Gọi ba số chẵn liên tiếp là 2a, 2a+2, 2a+4 . Xét tích: 2a(2a+2)(2a+4)=8a(a+1)(a+2). Chứng minh rằng a(a+1)(a+2) chia hết cho 3 và chia hết cho 2. Bài toán 5. Chứng minh rằng số gồm 27 chữ có chữ số 1 thì chia hết cho 27. Lời giải .Gọi A là số gồm 27 chữ số 1, B là số gồm 9 chữ số 1.Lấy A chia cho B ta được thương là Như vậy A= B.C trong đó B chia hết cho 9, còn C chia hết cho 3. Vậy A chia hết cho 27. Dạng 3. Phân tích B thành nhân tử: Nếu B = B1.B2.B3....Bn với () = 1, và thoả mãn điều kiện thì . Bài toán 6. Cho n.Chứng minh chia hết cho 24 với Lời giải .Ta có: 24=Do 3 và 8 nguyên tố cùng nhau, nên để chứng minh A,ta chứng minh A và A. Ta có : = = = Vì là tích của 4 số nguyên liên tiếp nên , ngoài ra, trong 4 số nguyên liên tiếp luôn có hai số chẵn liên tiếp, một số chia hết cho 4, số còn lại chia hết cho 2 nên ta có Vậy ta có điều phải chứng minh. Bài toán 7. Chứng minh: chẵn. Lời giải.Đặt A Vì n chẵn nên Vì là tích của 4 số nguyên liên tiếp nên chia hết cho 8 và 3. Mà (3,8)=1. Từ đó có .Vậy A(đpcm). Bài toán 8. Chứng minh: lẻ. Lời giải. Đặt . Vì n lẻ nên . Suy ra chia hết cho 4. Dạng 4. Nếu , trong đó thì . Bài toán 9. Chứng minh rằng nếu p là số ngyên tố lớn hơn 3 thì (p-1)(p+1) chia hết cho 24. Lời giải. Ta có (p-1)p(p+1) mà ( p,3 ) =1 nên (p-1)(p+1) (1) Vì p là số nguyên tố lớn hơn 3 nên p là số lẻ, p-1 và p+1 là hai số chẵn liên tiếp. Trong hai số chẵn liên tiếp, có một số là bội của 4 nên tích của chúng chia hết cho 8 (2). Từ (1) và (2) suy ra (p-1)(p+1) chia hết cho hai số nguyên tố cùng nhau 3 và 8. Vậy (p-1)(p+1) . B. Lý thuyết đồng dư và bài toán chia hết Tóm tắt. Lý thuyết đồng dư do nhà toán học Gauss xây dựng. Có thể nói lý thuyết đồng dư thức là một công cụ mạnh để giải quyết các bài toán số học nói chung và các bài toán chia hết nói riêng. Ngày nay, lý thuyết đồng dư có một vai trò rất quan trọng trong bài toán mật mã khoá công khai, một vấn đề có ý nghĩa thực tiễn cao. Bài viết này trình bày một số vấn đề về lý thuyết đồng dư và ứng dụng của nó trong bài toán chia hết. 1. Giới thiệu Lý thuyết đồng dư do nhà toán học lỗi lạc " Ông vua toán học " Gauss trình bày trong "Disquisitiones Arithmeticae". Phần chính của sách được viết khi còn là sinh viên và in xong khi ông mới 24 tuổi. Ngày nay lí thuyết được thừa nhận là một công cụ cơ bản đầy sức mạnh khi nghiên cứu lí thuyết số. Định nghĩa 1. Cho trước số nguyên dương . Hai số nguyên và được gọi là đồng dư với nhau theo modulo nếu hai số đó có cùng số dư khi chia cho , kí hiệu là . hoặc một định nghĩa khác tương đương Định nghĩa 2. Cho trước số nguyên dương . Hai số nguyên đồng dư theo modulo m khi và chỉ khi chia hết cho m. Sau này ta sẽ sử dụng định nghĩa 2 nhiều hơn. Việc phát hiện ra hai số đồng dư với nhau theo một modulo nào đó chủ yếu dựa vào định nghĩa 2. Định lý 3. Quan hệ đồng dư trên vành số nguyên là một quan hệ tương đương và với mỗi số nguyên dương m cho trước thì tập thương của nó là 2. Một số tính chất của đồng dư thức Dựa vào định nghĩa 2, ta có thể đưa ra các tính chất của đồng dư thức. Các tính chất sau đây xét trên tập các số nguyên và riêng modulo m là số nguyên dương nếu không có chú thích gì thêm. Tính chất 4. Nếu và thì . Tính chất 5. Nếu và thì Hệ quả 6. Nếu thì Tính chất 7. Nếu và thì Tính chẩt 8. Nếu và thì Tính chất 9. Nếu với thì với Tính chất 10. . Tiếp theo, ta sẽ đưa ra một vài định lý về đồng dư có ứng dụng quan trọng vào việc giải toán số học, đặc biết là trong các bài toán chứng minh chia hết. 3. Một số định lý quan trọng về đồng dư thức Định lý 10. Giả sử là một đa thức với hệ số nguyên; là các số nguyên thoả mãn điều kiện . Khi đó Định lý 11.( Định lý Fermat nhỏ) Giả sử là một số nguyên tố và a là một số tự nhiên tuỳ ý . Khi đó, . Nếu thì Sau đây ta sẽ đưa ra một cách chứng minh đơn giản nhất cho định lý Fermat nhỏ. Chứng minh. Ta chứng minh định lý Fermat nhỏ bằng quy nạp theo a. Rõ ràng bài toán đúng với Giả sử khẳng định bài toán đúng đến Ta chứng minh bài toán cũng đúng với , tức là Theo nhị thức Newton, ta có vì với thì là một số nguyên có chứa thừa số nên . Định lý 12. (Định lý Euler) Giả sử là các số nguyên nguyên tố cùng nhau. Khi đó trong đó là hàm Euler và nếu thì . Dễ thấy. định lý Fermat nhỏ là một trường hợp riêng của định lý Euler. Định lý 13. (Định lý Wilson) Giả sử là một số nguyên tố. Khi đó Chú ý là mệnh đề đảo của định lý Wilson cũng đúng tức là nếu ta có thì n phải là số nguyên tố. Sau đây, ta sẽ đưa ra một số ví dụ về phương pháp sử dụng lý thuyết đồng dư để chứng minh sự chia hết. ----------------------------------- Có thể xem các cách chứng minh của các định lý Fermat, Euler, Wilson trong [1], [2]. 4. Áp dụng đồng dư vào giải bài toán chia hết Bài toán 1. Chứng minh rằng chia hết cho 13. Lời giải. Ta có và Từ đây sử dụng tính chất 4 ta có điều phải chứng minh. Bạn đọc có thể đưa ra một bài toán tổng quát là tìm tất cả các số nguyên dương sao cho chia hết cho 13. Bài toán 2. Chứng minh rằng chia hết cho 2003. Lời giải. Sử dụng định lý Fermat nhỏ với chú ý 2003 là số nguyên tố, ta có . Do đó, . Từ đây ta suy ra đpcm. Bài toán 3. Chứng minh rằng chia hết cho 1729 với mọi nguyên dương n. Lời giải. Ta chú ý và 7, 13, 19 đều là các số nguyên tố nên theo định lý Fermat nhỏ, ta có . Do đó Vì 7, 13, 19 đôi một nguyên tố cùng nhau nên sử dụng tính chất 9 của đồng dư ta có tức là chia hết cho 1729. Bài toán 4. Chứng minh với mỗi số tự nhiên thì tồn tại vô hạn số tự nhiên sao cho với moị số tự nhiên nguyên tố cùng nhau với ta luôn có chia hết cho m. Lời giải. Theo định lý Euler ta có nên nếu chọn với thì hiển nhiên sẽ nhận vô hạn giá trị và ta có . Chứng minh hoàn tất. Bài toán 5. Cho Chứng minh nếu là một số nguyên tố thì là một hợp số. Lời giải. Vì là số nguyên tố nên theo định lý Wilson ta có hay một cách tương đương ta có chia hết cho Mặt khác, ta lại có nên suy ra chia hết cho . Hơn nữa do ta luôn có nên ta có ngay đpcm. Bài toán 6. Gọi là tổng các chữ số của số tự nhiên n khi n ghi trong hệ cơ số 10. Đặt với k lần xuất hiện chữ Chứng minh rằng chia hết cho 9. Lời giải. Rõ ràng ta chỉ phải chứng minh chia hết cho 9. Thật vậy, giả sử Sử dụng với mọi số tự nhiên k ta suy ra tức là chia hết cho 9. Sử dụng điều này, ta có Từ đây ta suy ra đpcm. C. Phương pháp quy nạp trong giải toán chia hết Ý tưởng.Trong nhiều lĩnh vực khác nhau của toán học ( số học, hình học, giải tích) ta thường gặp những bài toán chứng mệnh đề chứa biến là mệnh đề đúng với mọi giá trị nguyên dương của biến n. Để chứng minh mệnh đề chứa biến là đúng với mọi giá trị nguyên dương của n ta thực hiện các bước sau: Bước 1. ( Bước cơ sở hay bước mở đầu) Chứng minh đúng khi n = 1. Bước 2. ( Bước quy nạp hay bước di truyền). Với k là số nguyên dương, xuất phát từ giả thiết (được gọi là gia thiết quy nạp). đúng với n=k , ta chứng minh mệnh đề chứa biến là đúng với n=k+1. Với ứng dụng rộng rãi của phương pháp quy nạp đối với những bài toán chứng minh A(n) tự nhiên, ta vẫn thường dùng phương pháp quy nạp. Cụ thể lược đồ của cách giải này là: Giả sử , ta chứng minh . Nhưng để ý rằng nếu Vì vậy có thể xem đây là một biến dạng của phương pháp quy nạp, để chứng minh ta qua hai bước: Áp dụng phương pháp này, ta có thể giải được một loạt các bài toán chia hết khá cồng kềnh.Bài tập 1. Chứng minh có chia hết cho 125.Lời giải. Có .Xét nhưng nên (đpcm) Bài tập 2. Chứng minh thìchia hết cho 64.Lời giải.Có . Xét Đặt ta cần chứng minh Lại áp dụng phương pháp trên với  . Xét .Vậy (Đpcm). Bài tập 3. Chứng minh có: (1). Lời giải. Với n=1 ta có (đpcm)Giả sử (1) đúng với n ta cần chứng minh (1) cũng đúng với n+1 nghĩa là: . Thật vậy, ta có số 10n+2 có tổng các chữ số là 3, vì vậy theo dấu hiệu chia hết cho 3 thì 10n+2 hay (1) được chứng minh. Bài tập 4. Chứng minh có: (1). Lời giải. Với n=1 ta có (đpcm).Giả sử (1) đúng với n ta cần chứng minh (1) cũng đúng với n+1 nghĩa là: (đúng)Vậy (1) được chứng minh. D. Phương pháp phản chứng và bài toán chia hết Ý tưởng. Một mệnh đề toán học đúng hoặc sai mà ko thể vừa đúng lại vừa sai. Muốn chứng minh mệnh đề đúng, ta chứng minh cho nó không sai. Nói cách khác, nếu giả sử mệnh đề là sai thì sẽ dẫn đến 1 điều vô lí. Phương pháp chứng minh như vậy được gọi là Chứng minh phàn chứng. 1) Các bước của phép chứng minh phản chứngBước 1. Bước giả định: Giả sử mệnh đề cần chứng minh là saiBước 2.Bước truy nguyên:Xuất phát từ giả sử mệnh đề sai ta dẫn đến 1 điều vô lý(hoặc trài với giả thuyết, hoặc là mâu thuẫn với 1 định lí, tiên đề, 1 kết luận đã chứng minh là đúng, hoặc là dẫn tới 2 kết luận mâu thuẫn nhau)Bước 3.Bước kết luận: Điều vô lí chứng tỏ là mệnh đề ko sai tức là mệnh đề cần chứng minh là đúng. 2) Áp dụng phương pháp phản chứng vào giải toán chia hết Bài toán 1: Chứng minh rằng không tồn tại số nguyên dương n sao cho . Lời giải. Giả sử tồn tại số nguyên n để . Ta có . Vì là ba số nguyên liên tiếp nên có đúng một số chia hết 3. Nên Vậy suy ra (1). Mặt khác: mà nên chia cho 3 dư 2 (2) Từ (1) và (2) dẫn đến điều mâu thuẫn, tức là không có số nguyên dương n nào thoả mãn điều kiện của bài toán đã cho. Suy ra điều phải chứng minh. Bài toán 2: Chứng minh rằng với mọi số tự nhiên n thì không chia hết cho 15. Lời giải. Giả sử với mọi thì nên với . Khi đó phương trình có nghiệm nguyên n. Ta có không thể là số chính phương ( vì số chính phương chia cho 3 dư 0 hoặc 1) . Vậy phương trình không có nghiêm nguyên, do đó với mọi . Vậy điều giả sử trên là vô lý, suy ra điều phải chứng minh. Bài toán 3: Chứng minh rằng . Lời giải. Giả sử . Nên suy ra . Ta có: mà Nên và do đó (vô lý). Vậy Bài toán 4: Cho n là số tự nhiên d là ước nguyên dương của . Chứng minh rằng: . Lời giải. Bây giờ ta chứng minh rằng không là số chính phương. Giả sử với . Vì d là ước của nên với . Thay vào (1) ta được: . Từ đó suy ra là số chính phương. Nhưng (mâu thuẫn). Vậy không thể là số chính phương, nên (ĐPCM). Bài toán 5: Giả sử là số nguyên lẻ với . Với k là số tự nhiên lẻ. Khi đó nếu các số tự nhiên x,y sao cho thì x,y đồng thời chia hết cho p. Lời giải. Giả sử x không chia hết cho p , từ giả thiết suy ra y cũng không chia hết cho p. Theo định lý nhỏ Fecma ta có: Hay . Suy ra Mà theo giả thiết . Nên Do k lẻ. Nên mâu thuẫn. Suy ra điều phải chứng minh. Bài toán 6: Cho số nguyên tố có dạng Chứng minh rằng nếu x,y thảo mãn thì x,y đều chia hết cho p. Từ đó suy ra phương trình không có nghiệm nguyên dương. Lời giải. Ta có nên áp dụng ví dụ 4 với ta có ngay điều phải chứng minh. Ta có mà nên và suy ra ( vô lí). Vậy phương trình không có nghiêm nguyên dương. : Bài tập Bài 1. Cho .Chứng minh Bài 2. Chứng minh rằng số gồm 81 chữ số 1 thì chia hết cho 81. Bài 3. Chứng minh rằng số chia hết cho 3,7,13,37. Bài 4. Cho n Chứng minh: Bài 5. Chứng minh rằng nếu a,k là số nguyên, a lẻ thì. Bài 6. Chứng minh: lẻ. Bài 7. Chứng minh: lẻ. Bài 8. Chứng minh rằng với mọi ta có Bài 9. Chứng minh rằng với mọi ta có Bài 10. Cho p là số nguyên tố có dạng và a,b là các số nguyên, khi đó thì và . Áp dụng tìm nghiệm nguyên dương của phương trình . Bài 11. Chứng minh rằng thì . Bài 12. Chứng minh rằng thì . Bài 13. Chứng minh luôn chia hết cho trong đó là số nguyên tố và a, b là các số nguyên. Bài 14. Chứng minh rằng nếu n là số nguyên thì cũng là một số nguyên. Bài 15. Tìm tất cả các số hạng nguyên tố trong dãy số sau Bài 16. Chứng minh rằng chia hết cho 102. Bài 17. Chứng minh rằng nếu p là số nguyên tố thì với mọi số nguyên ta luôn có chia hết cho p. Bài 18. Cho số nguyên a và số tự nhiên n thoả mãn điều kiện thì chia hết cho n. Bài 19. Chứng minh rằng với mọi số tư nhiên n thì không chia hết cho 49. Bài 20. Chứng minh rằng chia hết cho 2008. Tài liệu tham khảo. [1] Hà Huy Khoái, Chuyên đề bồi dưỡng số học THPT, NXBGD, 2006. [2] N.V. Lương, N.L. Sơn, P.V. Hùng, N.N. Thắng, Các bài giảng về số học tập 1,2, NXB ĐHQG Hà Nội, 2006. [3] Tạp chí Toán học và tuổi trẻ, NXBGD. [4] Tạp chí Toán tuổi thơ 2, NXBGD.