Tuyển tập một số bài toán sơ cấp chọn lọc

Nội dung text: Tuyển tập một số bài toán sơ cấp chọn lọc

1. Tuyển tập một số bài toán sơ cấp chọn lọc
2. Tuyển tập một số vấn đề chọn lọc www.diendantoanhoc.net 05 - 08 - 2006
3. Lời nói đầu Cuốn sách nhỏ "Tuyển tập một số bài toán sơ cấp chọn lọc trên www.diendantoanhoc.net" là món quà đặc biệt mà BTC kỳ thi VMEO II dành tặng cho các bạn thành viên đã tham gia và đoạt giải. Đây cũng là một món quà mùa hè mà Nhóm Quản Lý muốn dành tặng cho tất cả các bạn học sinh chuyên toán nói riêng và các bạn yêu thích toán sơ cấp nói chung. Trong cuốn sách này chúng tôi giới thiệu với các bạn 250 bài toán thuộc 5 chủ đề lớn của toán phổ thông bao gồm Số Học, Tổ Hợp, Hình Học, Giải Tích và Đại Số. Kèm theo các đề toán là khoảng 20 bài viết chuyên đề nhỏ xoay quanh các bài toán Số Học, Tổ Hợp. Trong mỗi bài viết chúng tôi đã cố gắng thể hiện đầy đủ những thảo luận của các bạn trên diễn đàn về những bài toán đó. Một số bài viết chưa được post lên diễn đàn mà mới chỉ là những trao đổi riêng giữa các thành viên cũng được giới thiệu trong tài liệu này. Chúng tôi rất vui mừng vì biết được rằng, những trao đổi riêng như thế là khá phổ biến giữa các bạn thành viên. Đây thực sự là một mong muốn lớn nhất của những người điều hành diễn đàn như chúng tôi. Số Học và Tổ Hợp đều là những chủ đề thú vị và đẹp đẽ của toán sơ cấp. Tuy nhiên để viết một tài liệu về hai chủ đề này là điều không dễ. Đối với Số Học chúng tôi lựa chọn nhiều chủ để nhỏ dựa trên bộ khung là các bài toán đã có trên diễn đàn, và các kiến thức cơ bản nhất của Số Học lần lượt được đưa vào các bài viết nhỏ, các bạn có thể đọc qua các bài viết này và tìm hiểu kỹ hơn về lý thuyết số sơ cấp trong các cuốn sách chuyên khảo hơn, chúng tôi giới thiệu hai cuốn sách: An introduction to the theory of number của G.H.Hardy & E.M.Wright và Elementary theory of number của Sierpinsky. Bản điện tử của hai cuốn sách này đều đã được giới thiệu trên diễn đàn. Về Tổ Hợp, chúng tôi chủ trương lựa chọn các chủ đề một cách tương đối rời rạc, vì cho rằng không nên khiến các bạn phải tiếp thu các kiến thức tổ hợp một cách quá giáo khoa. Đối với các bài toán tổ hợp chúng tôi cho rằng vẻ đẹp của từng bài toán có ý nghĩa cao hơn tới việc nhận thức của mỗi người. Do đó chúng tôi cố gắng lựa chọn những bài toán tổ hợp đẹp đẽ để kích thích tính tìm tòi của các bạn đọc. Hai cuốn sách sơ cấp về tổ hợp không nên bỏ qua là 102 combinatorial problem của Titu Andrecscu & Zuming Feng và Extrenal combinatorics của Stasys Jukna. Tất nhiên các chủ đề về Hình Học, Giải Tích và Đại Số cũng rất thú vị, nhưng đó sẽ là nội dung của các ấn phẩm tiếp theo của diễn đàn. Và bởi vì các ấn phẩm của diễn đàn chủ yếu được xây dựng dựa trên những thảo luận của chính các bạn nên hi vọng trong thời gian tới chúng ta sẽ còn có nhiều chủ đề thú vị và chất lượng ngày càng cao. Cuốn sách nhỏ này ra đời dựa trên sự cộng tác của rất nhiều bạn thành viên. Đó là các bạn K09, TuanTS, lehoan, NDTPX, clmt, anhminh, neverstop, bk2004, chuyentoan, camum, 3
4. 4 hungkhtn và lovepearl_maytrang. Bạn camum lựa chọn hầu hết các bài toán giải tích, mục tổ hợp do lehoan tuyển chọn với sự cộng tác của NDTPX, các bài toán hình học do MrMATH soạn cùng với sự giúp đỡ nhiệt tình của bk2004, chuyentoan và đã nhận được nhiều ý kiến của bạn neverstop. Cuối cùng các bài toán số học được lựa chọn bởi K09 và lehoan, sau đó TuanTS và MrMATH đã có nhiều thảo luận để hoàn thiện bản thảo. Trong quá trình tuyển chọn chúng tôi nhận ra rằng có rất nhiều bài toán được sáng tạo bởi chính các bạn thành viên. Trong thời gian tới mong rằng điều này sẽ được phát huy hơn nữa. Cuốn sách này được soạn bằng phần mềm PCTEX version 5.0, gói vntex được giới thiệu bởi bạn tamnd. File cài đặt chương trình và gói lệnh các bạn có thể dowload trên mạng không quá khó khăn. Nếu có thắc mắc về việc sử dụng TEX các bạn có thể giải quyết bằng các tham khảo các cuốn sách của tác giả Nguyễn Hữu Điển (sách cho Viện Toán Học ấn hành), ngoài ra các bạn có thể tham gia các diễn đàn về TEX như www.viettug.com hoặc trao đổi với các thành viên có kinh nghiệm soạn thảo trên diễn đàn. Mặc dù đã cố gắng trong việc kiểm tra bản thảo, nhưng rất có thể chúng tôi vẫn bỏ sót một số lỗi. Mọi ý kiến đóng góp cả về nội dung lần hình thức xin gửi về địa chỉ mail nqk_mrmath@yahoo.com. Chúng tôi xin chân thành cám ơn và hứa sẽ cố gắng hơn trong việc thiết kế các ấn phẩm tiếp theo. Thay mặt Ban Biên Tập a MrMATH www.diendantoanhoc.net Nguyễn Quốc Khánh SV K9 Hệ Đào Tạo CNKHTN ĐHKHTN ĐHQG Hà Nội
5. Cộng tác viên Trong thời gian hoàn thành bản thảo, thực ra những gì được giới thiệu trong cuốn sách nhỏ không hoàn toàn là tất cả những gì nhóm CTV làm được. Trên thực tế nhóm CTV đã hoàn thiện được hầu hết các đề mục cho ba nội dung Hình Học, Giải Tích và Đại Số. Tuy nhiên việc giới thiệu đồng thời tất cả 5 chủ đề có lẽ là không phù hợp lắm với mục đích chính. Bản liệt kê dưới đây không nêu lên hết được các CTV và công việc của họ, nhưng dù sao cũng là một tra cứu đủ dùng cho các bạn đọc.Trong ấn phẩm tiếp nối của cuốn sách nhỏ này, công việc của các CTV sẽ được giới thiệu một các đầy đủ và chi tiết hơn. a 1. Trần Nam Dũng (namdung) GV ĐHKHTN ĐHQG TP Hồ Chí Minh: [1]. a 2. Trần Quốc Hoàn (K09) SV K50 CA Đại Học Công Nghệ Hà Nội: [2], [3.6], [3.8]. a 3. Trần Mạnh Tuấn (TuanTS) SV K9 CNTN ĐHKHTN ĐHQG Hà Nội: [2], [3.2], [3.3],[3.4]. a 4. Lê Hồng Quý (lehoan) HS lớp 12 chuyên toán ĐHSP Vinh: [6], [7.2], [7.3], [7.7]. a 5. Trần Đức Anh (camum) SV năm nhất hệ CLC ĐHSP Hà Nội: [10]. 5
6. Mục lục I Một số chủ đề Số Học 9 1 Tổng hai bình phương 11 2 Các đề toán số học chọn lọc 17 3 Một số chủ đề số học chọn lọc 23 3.1Sốbậpbênh 23 3.2 Định lý F ermat nhỏ và một ứng dụng đẹp . . . . . . . . . . . . . . . . . . . . 26 3.3 Một số tính chất của hàm tổng các chữ số . . . . . . . . . . . . . . . . . . . . 27 3.4 Hai ứng dụng của phương trình Pell 30 3.5 Định lý phần dư Trung Hoa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.6Biểudiễnsố 34 3.7 Một dạng phương trình Diophante đặcbiệt 37 3.8Sốnguyênphức 40 3.8.1 Các khái niệm mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.8.2 Thuật toán Euclid và ước chung lớn nhất của hai số nguyên phức . . . 41 3.8.3 Số phức nguyên tố và vấn đề phân tích các số nguyên phức . . . . . . . 43 3.8.4 Sử dụng số nguyên phức để giải một số bài toán . . . . . . . . . . . . . 44 3.9 Phương trình Carmichael 45 3.10Mộtsốbàitoánkhác 47 4 Tổng nghịch đảo 53 II Một số chủ đề Tổ Hợp 59 5 Bổ đề Sperner 61 5.1Baolồi 63 5.2BổđềKKM 64 5.3 Chứng minh định lý điểm bất động Brower . . . . . . . . . . . . . . . . . . . . 64 6 Các đề toán tổ hợp chọn lọc 65 7 Một số chủ đề tổ hợp chọn lọc 71 7.1 Bài toán Rubik lục lăng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.2 Nguyên lý bất biến và nửa bất biến . . . . . . . . . . . . . . . . . . . . . . . . 73 7
7. 8 MỤC LỤC 7.2.1 Bấtbiến 73 7.2.2 Nửabấtbiến 75 7.3 Phương pháp phân nhóm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.4 Vai trò của các bộ số đặc biệt . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 7.5 Hai bài toán về phủ các hình vuông . . . . . . . . . . . . . . . . . . . . . . . . 84 7.6 Câu hỏi mở về một tính chất của chùm các đường tròn . . . . . . . . . . . . . 86 7.7 Định lí Konig-Hall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 7.8 Định lý Erdos - Skerezes 90 7.9Mộtsốbàitoánkhác 92 8 Góc cùng màu 95 8.1 Khái niệm góc cùng màu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 8.2 Mở rộng bài toán 6 người 99 8.3 Phương pháp hàm đếm và vài ứng dụng . . . . . . . . . . . . . . . . . . . . . 103 8.4 Mở rộng một đề thi IMO 1992 105 III Một số bài toán khác 109 9 Hình Học 111 10 Giải Tích 117 11 Đại Số 125
8. Phần I Một số chủ đề Số Học 9
9. Chương 1 Tổng hai bình phương Trần Nam Dũng Giới thiệu. Định lý F ermat Euler là một viên ngọc tuyệt vời của Toán Học thế kỷ 17 − 18. Từ thời phổ thông khi đọc được chứng minh (của Lagrange) dưới đây, tôi đã từng ngây ngất trước vẻ đẹp của nó. Nhiều năm nay đọc lại bài viết của GS.T ikhomirov trên tạp chí Kvant, tôi lại tiếp tục bất ngờ với những chứng minh mới của một kết quả cũ. Quá thích thú với bài báo, tôi đã dịch ra Tiếng Việt và nhiều lần truyền vẻ đẹp của các phép chứng minh thần diệu trong bài đến các thế hệ học sinh của tôi. Hôm nay, tôi xin dành tặng các bạn thành viên diễn đàn www.diendantoanhoc.net bản dịch này. Các bạn hãy để ý xem những số nguyên tố đầu tiên 3, 5, 7, 11, 13, 17, 19. Các số 5, 13 và 17 có thể biểu diễn được dưới dạng tổng của hai bình phương: 5=12 +22 13=22 +32 17=12 +42. Còn các số còn lại 3, 7, 11, 19 thì không thể biểu diễn như vậy được. Có thể bằng cách nào đó giải thích điều đó hay không? Có, và đúng hơn là ta có định lý sau đây: Định lý F ermat Euler. Điều kiện cần và đủ để một số nguyên tố lẻ có thể biểu diễn được dưới dạng tổng hai bình phương là số dư trong phép chia số ấy cho 4 là 1. Trong các trường hợp ban đầu của p có thể kiểm tra tính đúng đắn của định lý này 5=4.1+1, 13 = 4.3+1, 17 = 4.4+1còn 3=4.0+3, 7=4.1+3, 11 = 4.2+3và 19 = 4.4+3. Đôi chút về lịch sử định lý. Ai là người đầu tiên phát hiện ra điều này, và khi nào? Vào dịp Noel năm 1640 (trong thư đề ngày 25.12.1640) nhà toán học vĩ đại P ierre de F ermat (1601-1665) đã thông báo cho Mersenne, bạn thân của Descartes và là "liên lạc viên" chính của các nhà bác học đương thời rằng "Mọi số nguyên tố có số dư trong phép chia cho 4 bằng 1 đều có thể biểu diễn một cách duy nhất dưới dạng tổng của hai bình phương". Thời đó chưa có các tạp chí toán học, tin tức được trao đổi qua các lá thư và các kết quả thông thường chỉ được thông báo mà không kèm theo chứng minh. 11
10. 12 CHƯƠNG 1. TỔNG HAI BÌNH PHƯƠNG Thực ra thì sau gần 20 năm sau bức thư đó, trong bức thư gửi cho Carcavi, được gửi vào tháng 8 năm 1659, F ermat đã tiết lộ ý tưởng của phép chứng minh định lý trên. Ông viết rằng ý tưởng chính của phép chứng minh là dùng phương pháp xuống thang, cho phép từ giả thiết rằng định lý không đúng với p =4k +1, suy ra nó không đúng với một số nhỏ hơn, cuối cùng ta sẽ đi đến số 5, mà khi đó rõ ràng là mâu thuẫn. Những cách chứng minh đầu tiên được Euler (1707-1783) tìm ra trong khoảng 1742-1747. Hơn nữa, để tỏ rõ vị trí của F ermat, người mà ông hết sức kính trọng, Euler đã tìm ra phép chứng minh dựa theo đúng ý tưởng trên đây của F ermat. Vì vậy, ta gọi định lý này là định lý F ermat Euler. Những kết quả toán học thường có một tính chất chung ta có thể đến được bằng nhiều con đường khác nhau, có thể tấn công chúng từ nhiều hướng, và mỗi một con đường như vậy sẽ đem đến cho những người không biết sợ khó khăn những khoái cảm tuyệt vời. Tôi muốn chứng tỏ điều này trên ví dụ định lý F ermat Euler. Ta sẽ đi đến đỉnh cao, được phát minh vào thế kỷ XVII bằng ba con đường khác nhau. Một trong chúng được tìm ra vào thế kỷ XVIII, con đường khác - thế kỷ XIX và con đường thứ ba - ở thế kỷ XX. 1. Cách chứng minh của Lagrange. Cách chứng minh này (có thay đổi đôi chút) hiện nay được trình bày trong hầu hết các cuốn sách về lý thuyết số. Nó dựa trên bổ để W ilson nói rằng nếu p là số nguyên tố thì số (p−)!+1chia hết cho p. Để không quá đi sâu vào chứng minh kết quả phụ này ta chỉ tường minh ý tưởng chính của phép chứng minh trên ví dụ số 13. Với một số nằm giữa 2 và 11 (kể cả những số này) ta tìm một số mà tích của chúng khi chia cho 13 dư 1. Ta có: (13 − 1)! = 12! = (2.7).(3.9).(4.10).(5.8).(6.11).12. Rõ ràng từng cặp hai số trong dấu ngoặc đơn có tích chia 13 dư 1. Từ đó suy ra 12! khi chia cho 13 có số dư là 12, nghĩa là 12! + 1 chia hết cho 13. Trường hợp tổng quát cũng có thể chứng minh tương tự như vậy. Từ bổ đề W ilson ta rút ra hệ quả là nếu p =4n +1 là một số nguyên tố thì ((2n)!)2 +1 chia hết cho p. Thật vậy, bởi vì (bổ đề W ilson) (4n)!+1chia hết cho p, bằng những phép biến đổi cơ bản ta thu được: (4n)!+1=1.2.3 (2n).(2n +1) (4n)+1 =1.2 (2n).(p − 2n).(p − 2n +1) (p − 1) + 1 =(2n)!.(−1)2n.(2n)! ≡ ((2n)!)2 +1 modp. Suy ra điều phải chứng minh. Đặt N =(2n)!, ta đã chứng minh N 2 ≡−1modp. Bây giờ ta √ phải vượt qua khó khăn chính, xét tất cả các cặp số nguyên (m, s) sao cho 0 ≤ m, s ≤ [ p] √ (ở đây [x] chỉ phần nguyên của x). Số các cặp như vậy bằng ([ p]+1)2 >p.
11. 13 Do đó với ít nhất hai cặp số (m1,s1) và (m2,s2) số dư trong phép chia m1 + Ns1 và m2 + Ns2 cho p sẽ giống nhau, nghĩa là số a + Nb trong đó a = m1 − m2 và b = s1 − s2 sẽ chia hết cho p. Nhưng khi đó a2 − N 2b2 =(a + Nb)(a − Nb) chia hết cho p và chú ý rằng N 2 ≡−1 mod p ta thu được a2 + b2 chia hết p, nghĩa là a2 + b2 = rp với r nguyên dương. Mặt khác a2 + b2 2y0 và nghĩa là phải tính B(x0,y0,z0) theo công thức thứ ba. Nghĩa là: x00 = x0 − 2y0 = x +2z − 2z = x  y00 = x0 − y0 + z0 = x +2z − z + y − x − z = y 00 0 z = y = z. Bây giờ ta giả sử rằng p là số nguyên tố có dạng 4n +1. Khi đó, thứ nhất phương trình x2 +4yz = p có ít nhất hai nghiệm (x =1,y = n, z =1)và (x =1,y =1,z = n). Và thứ hai là phương trình này có hữu hạn nghiệm (nguyên dương). Nếu như giả sử rằng trong các nghiệm của phương trình này không có nghiệm mà y = z (nếu như có nghiệm như vậy thì p = x2 +(2y)2 và định lý được chứng minh), ta thu được rằng phép biến đổi B chia tất cả các nghiệm thành các cặp ((x, y, z),B((x, y, z))), nếu như, tất nhiên (x, y, z) =6 B((x, y, z)). Ta thử tìm xem có những cặp như vậy không, hay như người ta thường nói, tồn tại chăng những điểm bất động của phép biến đổi B.
12. 14 CHƯƠNG 1. TỔNG HAI BÌNH PHƯƠNG Nếu nhìn vào công thức xác định B ta sẽ dễ dàng nhận thấy rằng những điểm bất động của B là những điểm mà x = y. Nhưng khi x = y>1 thì phương trình x2 +4yz = p không có nghiệm (vì p không chia hết cho y). Nghĩa là chỉ có một điểm bất động duy nhất (1, 1,n). Từ tất cả các lý luận trên ta suy ra rằng số nghiệm của phương trình x2 +4yz = p là số lẻ và có một điểm bất động (1, 1,n) còn tất cả các nghiệm khác được chia thành từng cặp. Nhưng, ta lại có một phép biến đổi nữa, ký hiệu là J, J thay đổi chỗ của y và z nghĩa là J(x, y, z)=(x, z, y). Phép biến đổi này tất nhiên cũng giữ nguyên dạng x2 +4yz và cũng xoắn. Ta thử xem, những bộ ba số nào trong những nghiệm của phương trình x2 +4yz = p được J giữ nguyên. tức là những bộ nào mà J(x, y, z)=(x, y, z). Ta đã giả sử từ trước là y =6 z. Nhưng khi đó thì không thể có điểm bất động. Tất cả các nghiệm được chia thành từng cặp. Như vậy số các nghiệm là chẵn. Nhưng ta vừa khẳng định rằng số nghiệm này là lẻ. Mâu thuẫn. Vậy phải tồn tại nghiệm của phương trình x2 +4yz = p mà y = z, như thế p là tổng của hai bình phương. Định lý được chứng minh. 3. Cách chứng minh thứ ba. Cách chứng minh của Minkowsky được sửa đổi đôi chút mà chúng ta sẽ nói đến bây giờ, sẽ còn làm chúng ta ngạc nhiên gấp bội. Đáng tiếc là cách chứng minh này không sơ cấp lắm, cụ thể là ta cần thế nào là elippse và công thức tính diện tích của nó. Tất cả bắt đầu từ một kết quả của Minkowsky mà tưởng chừng không có liên hệ gì với định lý F ermat Euler mà chúng ta đang quan tâm. Định lý. Cho a, b, c là các số nguyên, a>0 và ac − b2 =1. Khi đó phương trình ax2 +2bxy + cy2 =1 có nghiệm nguyên. Chứng minh. Ta xét hệ tọa độ Descartes vuông góc và cho trên đó tích vô hướng bằng công thức: ((x, y), (x0,y0)) = axx0 + byy0 + czz0. Tích vô hướng này cho ta khoảng cách từ gốc tọa độ đến điểm (x, y) là: d((0, 0), (x, y)) = p((x, x), (y,y)) = pax2 +2bxy + cy2. Ta tìm khoảng cách ngắn nhất từ gốc tọa độ đến một điểm khác nó của lưới nguyên (m, n) (m, n là những số nguyên). Gọi khoảng cách này là d∗ và đạt được tại điểm (m∗,n∗), như thế: 2 2 2 am∗ +2bm∗n∗ + cn∗ = d∗ . Tập hợp tất cả những điểm (x, y) của mặt phẳng thỏa mãn bất đẳng thức: ax2 +2bxy + cy2 ≤ d∗2
13. 15 là một ellipse. Từ cách xây dựng của ta suy ra rằng nếu vị tự ellipse này theo tỷ số 1/2 rồi đưa ellipse "co" này đến các tâm nằm trên các điểm nguyên (tịnh tiến) thì tất cả các ellipse thu được nếu có cắt nhau thì chỉ cắt nhau theo những điểm biên. Dễ thấy rằng diện tích phần giao của các ellipse với tam giác có đỉnh ở (0, 0), (1, 0), (1, 1) bằng nửa diện tích của toàn ellipse. Mà diện tích này thì bằng (chỗ không sơ cấp duy nhất): πd∗2 πd∗2 · (ac − b2)= . 4 4 πd∗2 Như vậy diện tích phần mà các ellipse chiếm trong tam giác bẳng và đây chỉ là một 8 nửa diện tích tam giác, nghĩa là: ∗2 πd 1 2 4 0, 0 ≤ B ≤ b − 1. Sử dụng giả thiết quy nạp ta suy ra mệnh đề đúng với b và do đó định lý được chứng minh. K09 www.diendantoanhoc.net Trần Quốc Hoàn K50 CA Đại Học Công Nghệ Hà Nội
14. 16 CHƯƠNG 1. TỔNG HAI BÌNH PHƯƠNG
15. Chương 2 Các đề toán số học chọn lọc Bài toán 2.1. Tìm tất cả các số nguyên dương nguyên tố cùng nhau với mọi phần tử của dãy: n n n an =2 +3 +6 − 1 n ≥ 1. Bài toán 2.2. Giải phương trình nghiệm nguyên dương x2 − (a2 + b2) · y4 =1. Bài toán 2.3. Cho k số tự nhiên 1 ≤ a1 ≤ a2 ≤ ≤ ak ≤ n thỏa mãn [ai,aj] >nvới mọi 1 ≤ i ≤ j ≤ k. Chứng minh rằng: k 1 3 k 1 6 (i) X 1 nào đó. Chứng minh rằng a có thể viết thành tổng của hai số chính phương. 17
16. 18 CHƯƠNG 2. CÁC ĐỀ TOÁN SỐ HỌC CHỌN LỌC Bài toán 2.9. Một số tự nhiên là bập bênh nếu khi đem nó nhân với 9 ta được chính số đó nhưng viết theo thứ tự ngược lại của các chữ số. Chẳng hạn số 1089 là một số bập bênh có 4 chữ số bởi vì 1089.9 = 9801. Vấn đề của chúng ta là tìm tất cả các số bập bênh có n chữ số. Hơn nữa hãy tính số tất cả các số bập bênh có n chữ số. Bài toán 2.10. Chứng minh rằng với số tự nhiên n bất kỳ đều tồn tại hai số nguyên x, y thoả mãn n|x2 − 34y2 +1. Bài toán 2.11. Tìm tất cả các số tự nhiên k sao cho tồn tại số thực dương ck thoã mãn: S(kn) ≥ c ∀n ∈ N. S(n) k Bài toán 2.12. Tìm tập giá trị của N để phương trình sau có nghiệm nguyên dương: 2 2 2 x1 + x2 + + xn = N(x1x2 xn − 1). Bài toán 2.13. Dãy số p1.p2, , pn, là dãy tất cả các số nguyên tố. Chứng minh rằng tồn tại ba số hạng liên tiếp trong dãy trên thoả mãn tính chất mỗi số trong chúng đều lớn hơn bình phương chỉ số của chính số đó. Bài toán 2.14. Chứng minh rằng tồn tại số tự nhiên n để số 2n +3n có đúng 23 ước số nguyên tố. Bài toán 2.15. Cho dãy tăng các số tự nhiên {an} có tính chất tồn tại hằng số M sao cho an+1 − an a>c  z = ab = cd x + y = a + b. Bài toán 2.20. Cho các số nguyên a1,a2, , an và b1,b2, , bn trong đó ai ≥ 2 ∀i = 1,n. Chứng minh rằng tồn tại vô hạn các bộ số nguyên (c1,c2, , cn) sao cho ta có tính chất sau: a1 a2 an b1c1 + b2c2 + bncn|c1 + c2 + + cn . Bài toán 2.21. Tìm tất cả các số tự nhiên n sao cho nếu với mọi hoán vị (a1,a2, , an) của {1, 2, , n} thì ta luôn tìm được chỉ số i mà a1 + a2 + + ai là một số chính phương.
17. 19 Bài toán 2.22. Tìm tất cả các số nguyên dương n sao cho n3 − 1 là số chính phương. Bài toán 2.23. Chứng minh rằng với hai số nguyên dương s, a (s) không chia hết cho 3) luôn tồn tại số tự nhiên n thoả mãn S(ns)=a với S(x) là tổng các chữ số của x. Bài toán 2.24. Cho số nguyên dương n>1. Tìm số nguyên dương nhỏ nhất không có dạng na − nb với bất kỳ các số nguyên dương a, b, c, d nào đó. nc − nd Bài toán 2.25. Cho số nguyên không âm a và số nguyên dương d. Chứng minh rằng trong 73 số a, a + d, , a +72d có ít nhất một số mà trong biểu diễn thập phân của nó có chữ số 9. Bài toán 2.26. Chứng minh rằng với mọi số thực δ ∈ [0, 1] và với mọi ε>0 bất đẳng thức: ϕ(n) − δ 2. Chứng minh rằng: n 1989|nnn − nnn .
18. 20 CHƯƠNG 2. CÁC ĐỀ TOÁN SỐ HỌC CHỌN LỌC Bài toán 2.34. Sắp xếp dãy các số nguyên tố theo thứ tự tăng dần p1,p2, Chứng minh rằng p ! n ∈ Z ∀n ∈ Nn>2. pn(pn + 1)(pn +2) (pn+1 − 1) Bài toán 2.35. Giả sử S là tập hợp tất cả các số nguyên tố bé hơn 40. Tìm số k nhỏ nhất sao cho với mọi tập con k phần tử của S đều tồn tại 3 phần tử đôi một phân biệt a, b, c sao cho a + b + c cũng là một số nguyên tố. Bài toán 2.36. Số nguyên dương n được gọi là đáng ghét nếu tồn tại số nguyên dương m mà trong tập hợp {1, 2, , 28011980} có đúng n số x1 <x2 < <xn không đồng dư với nhau theo mod n. Nếu điều này không xảy ra thì n được gọi là đáng yêu. Xác định số nguyên dương đáng yêu bé nhất. Bài toán 2.37. Cho các số nguyên dương a, b. Chứng minh rằng tồn tại bộ số nguyên dương (n1,n2, , nk) thoả mãn tính chất ni + ni+1|nini+1 ∀i = 0,k trong đó quy ước n0 = a, nk+1 = b. Bài toán 2.38. Chứng minh rằng mọi số nguyên lớn hơn 17 đều có thể biểu diễn thành tổng của 3 số nguyên lớn hơn 1 đôi một nguyên tố cùng nhau. Chứng minh tính chất đó không đúng với 17. Bài toán 2.39. Cho số nguyên tố p ≥ 3 và a1,a2, , ap−2 là các số tự nhiên sao cho p không k chia hết ak và ak − 1 với mọi k. Chứng minh rằng có thể chọn ra một số để tích các số đó có số dư là 2 khi chia cho p. Bài toán 2.40. Với số nguyên dương n gọi S(n) là tổng các chữ số của n. Chứng minh rằng tồn tại k số tự nhiên a1,a2, , ak sao cho: an + S(an)=am + S(am) ∀ 1 ≤ n, m ≤ k Bài toán 2.41. Chứng minh rằng phương trình x3 + y3 + z3 − t3 =42có vô hạn nghiệm nguyên. Số nghiệm nguyên dương của phương trình này là bao nhiêu, hữu hạn hay vô hạn? a c Bài toán 2.42. Giả sử n, a, b, c, d là các số tự nhiên (n ≥ 2) thoả mãn + < 1 và a+c<n. b d a c Cố định n, tìm giá trị lớn nhất của + . b d Bài toán 2.43. Tập hợp S gồm k + m − 1 số nguyên bất kỳ, m ≥ k ≥ 2,k|m. Chứng minh rằng tồn tại m số trong các số đó có tổng chia hết cho k. √ Bài toán 2.44. Giả sử rằng biểu diễn thập phân của 5 có dạng √ 5=2,a1a2 an bbb bbban+1 | m{zsố b } Biết rằng b =6 an,b=6 an+1. Chứng minh rằng n ≥ m − 2. Bài toán 2.45 (Open Question). Giả sử P là một tập con khác rỗng của tập các số nguyên tố sao cho với mọi p1,p2, , pk ∈ P (không nhất thiết phân biệt) thì mọi ước số nguyên tố của số p1p2 pk +1 cũng thuộc vào P . Hỏi tập hợp P có trùng với tập hợp tất cả các số nguyên tố hay không.
19. 21 Bài toán 2.46. Tìm tất cả các hàm số f : Z → Z thoả mãn đẳng thức: f(x3)+f(y3)+f(z3)=(f(x))3 +(f(y))3 +(f(z))3 ∀x, y, z ∈ Z. Bài toán 2.47. Giả sử m là một số nguyên dương lớn hơn 1 cho trước. Tìm hằng số C lớn nhất sao cho: 1 n 1 X ≥ C X ∀n ∈ N. k k 1≤k≤n,(k,m)=1 k=1 Bài toán 2.48. Chứng minh hai mệnh dề sau đây: i) Nếu n>49 thì tồn tại hai số nguyên a, b > 1 sao cho a + b = n và: ϕ(a) ϕ(b) + 4 thì tồn tại hai số nguyên a, b > 1 sao cho a + b = n và: ϕ(a) ϕ(b) + > 1. a b Bài toán 2.49. Với mỗi số tự nhiên n = at a2a1 xét hàm số: T (n)=10 X ai + X ai. i chẵn i lẻ Hãy tìm số nguyên dương A nhỏ nhất sao cho tồn tại các số tự nhiên n1,n2, , n148 và m1,m2, , m149 thoả mãn hai điều kiện: A = n1 + n2 + + n148 = m1 + m2 + m149  T (n1)=T (n2)= = T (n148) T (m1)=T (m2)= = T (m149). Bài toán 2.50. Ký hiệu ϕ(n) là số các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n và π(n) là số các số nguyên tố không vượt quá n. Chứng minh rằng với mọi số tự nhiên n>1 ta có: π(n) ϕ(n) ≥ . 2 a
20. 22 CHƯƠNG 2. CÁC ĐỀ TOÁN SỐ HỌC CHỌN LỌC
21. Chương 3 Một số chủ đề số học chọn lọc 3.1 Số bập bênh Bài toán 3.1.1 (Số bập bênh). Một số tự nhiên là bập bênh nếu khi đem nó nhân với 9 ta được chính số đó nhưng viết theo thứ tự ngược lại của các chữ số. Chẳng hạn số 1089 là một số bập bênh có 4 chữ số bởi vì 1089.9 = 9801. Vấn đề của chúng ta là tìm tất cả các số bập bênh có n chữ số. Hơn nữa hãy tính số tất cả các số bập bênh có n chữ số. lời giải. Xét dãy số F ibonaci {fn} xác định bởi công thức truy hồi sau f0 =0,f1 =1,fn+2 = fn+1 + fn ∀n ∈ N. Ngoài ra gọi số các số bập bênh có n chữ số là Sn. Ta sẽ chứng minh rằng số có 4 chữ số 1089 là số bập bênh nhỏ nhất và với số tự nhiên n ≥ 4 thì ta có: Sn = f[n/2]−1. Thật vậy, kết luận thứ nhất là dễ dàng thu được khi ta xét trực tiếp khi n =1, 2, 3. Xét n ≥ 4. Giả sử a1a2 an là một số bập bênh có n chữ số, điều đó có nghĩa là: 9.a1a2 an = an a2a1. (3.1) Suy ra a1 =1,an =9. Thay lại vào (3.1) thì 80 + 9.a2a3 an0=an−1 a20=⇒ a2 7. Như vậy a3 nhận 1 trong 2 giá trị 8 hoặc 9. Gọi số nghiệm trong hai trường hợp này lần lượt là Kn và Tn tương ứng. Khi đó rõ ràng ta có Sn = Kn + Tn. 23
22. 24 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC 2.1. Bước 1. Tính Kn. Dễ thấy K5 = K6 =0. Xét n ≥ 7. Ta có: n−6 9.a4 an−3 =8.10 + an−3 a4. (3.2) Suy ra a4 ≥ 8. Xét trực tiếp dễ thấy a4 =8=6 ⇒ a4 =9=⇒ K7 =0,K8 =1(số 108981089). Xét n>9, khi đó 9.a5 an−4 = an−4 a5. Đây chính là công thức xác định một số bập bênh có không quá n − 8 chữ số (theo (3.1)) nên: [n/2] Kn = X Sn−2k. k=4 2.2. Bước 2. Tính Tn. Dễ thấy T5 =1(số 10989). Xét n ≥ 6,lấy(3.1) theo mod 1000 suy ra an−2 =9. Thay lại vào (3.1): n−3 n−3 9.(109.10 + 989 + a4 an−300) = 901 + 989.10 + an−3 a400 n−6 =⇒ 9.a4 an−3 =8.10 − 8+an−3 a4. (3.3) T6 =1(số 109909). Xét n ≥ 7 suy ra a4 ≥ 8, lại xét hai trường hợp. Nếu a4 =8,lấy(3.1) n−8 theo mod 1000 thu được an−3 =0, thay lại vào (3.1) ta có 9.a5 an−4 =8.10 + an−4 a5. Theo (3.2) thì số nghiệm của phương trình này là Kn−2. Nếu a4 =9thay lại vào (3.1) suy ra n−8 a5 an−4 =8.10 − 8+an−4 a5. Theo (3.3) thì số nghiệm của phương trình này là Tn−2. Vậy ta có: Tn = Kn−2 + Tn−2 = Sn−2. Tóm lại chúng ta đã chứng minh được công thức sau đây của dãy các số Sn: [n/2] Sn = Kn + Tn = Sn−2 + X Sn−2k. k=4 Đặc biệt là với các xác định như đã nói ở trên thì dãy các số F ibonaci cũng thoả mãn: [n/2] fn = fn−2 + X fn−2k. k=4 Việc chứng minh công thức này không quá khó khăn và dành cho bạn đọc như một bài tập nhỏ. Bây giờ để ý rằng các giá trị ban đầu của hai dãy {Sn} và {f[n/2]−1} là hoàn toàn trùng nhau. Và do đó ta có thể kết luận rằng Sn = f[n/2]−1 với mọi số tự nhiên n ≥ 4. Đây chính là điều ta cần chứng minh. Xét dãy các số bập bênh dạng đặc biệt sau đây: p1 = 1089  p2 = 10989 pn = 10 999 999 89 n là số tự nhiên bất kì.   |n −{z1 số 9}
23. 3.1. SỐ BẬP BÊNH 25 Khi đó với sơ đồ chứng minh như trên chúng ta dễ dàng thu được dạng tổng quát như sau của tất cả các số bập bênh: pm1 pm2 pmnpmn+1 pmn pm2pm1 . Trong đó m1,m2, , , mn và mn+1 là các số tự nhiên tuỳ ý. Lời Bình. Đây là một bài toán hay, vấn đề đặt ra là khảo sát một loại số đặc biệt. điều thú vị là xuất xứ của từ bập bênh. Có thể thấy rõ qua công thức tổng quát xác định một số bập bênh bất kỳ nêu trên, cấu trúc của các số có tính chất (3.1) có thể chính là nguồn gốc của tên gọi thú vị này. Một điểm đặc biệt nữa là trong chứng minh trên chúng ta đã dựa vào (3.2), (3.3) để thu được công thức truy hồi đặc biệt của dãy {Sn}. Cần phải quan sát một cách tỉnh táo thì mới tránh được những suy luận thừa, không cần thiết và có thể lạc đề. Để cho chính xác ta có thể gọi các số bập bênh kiểu này là các số 9 − bập bênh. Một vấn đề nữa là có các số bập bênh kiểu khác không, tức là với số a như thế nào thì tồn tại số a − bập bênh, với giả thiết là số a − bập bênh là số mà khi đem nhân nó với a ta được chính số đó nhưng viết theo thứ tự các chữ số ngược lại. Đây là một bài toán không quá khó, thậm chí rất cũ nhưng cần phải xét tất cả các trường hợp a là chữ số. Kết quả là a chỉ có thể là 1, 9 hoặc 4. Đặc biệt nếu a =4thì kết quả vẫn rất tương tự, sự khác biệt có chăng chỉ là ở cách xác định dãy {pn}. Khi a =4vai trò của số 2178 sẽ thay thế vai trò của số 1089 (chú ý là 2178.4 = 8712). Chính xác hơn chúng ta có kết quả sau đây: Bài toán 3.1.2. Chứng minh rằng có bao nhiêu số 4 − bập bênh thì cũng có bấy nhiêu số 9 − bập bênh. Chứng minh trực tiếp kết quả này thực sự là một việc rất khó (!!) Thay cho lời kết. Trong số học còn vô vàn những loại số đáng chú ý khác và chúng ta sẽ sớm trở lại chủ đề này với những khảo sát chi tiết hơn. Dưới đây là một số bài toán về các loại số đặc biệt khác đã xuất hiện trong các kỳ thi học sinh giỏi gần đây và trước kia: Bài toán 3.1.3 (Số đong đưa). Một số nguyên dương được gọi là đong đưa nếu trong biểu diễn thập phân của nó, hai chữ số bất kỳ đứng cạnh nhau có một số bằng 0 và một số khác 0, chữ số hàng đơn vị khác 0. Tìm tất cả các số nguyên dương n sao cho n không có bội số nào là số đong đưa. Bài toán 3.1.4 (Số luân phiên). Một số nguyên dương được gọi là luân phiên nếu trong biểu diễn thập phân của nó, hai chữ số bất kỳ đứng cạnh nhau có một số chẵn và một số lẻ. Tìm tất cả các số nguyên dương sao cho nó không có bội số luân phiên nào cả. Bài toán 3.1.5 (Số bướng bỉnh). Cho các số tự nhiên đôi một nguyên tố cùng nhau a, b, c. Một số tự nhiên gọi là bướng bỉnh nếu nó không biểu diễn được dưới dạng xab + ybc+ zca với các số tự nhiên x, y, z. Hỏi có bao nhiêu số bướng bỉnh. Bài toán 3.1.6 (Số kim cương). Một số nguyên dương được gọi là kim cương 2005 nếu trong biểu diễn thập phân của nó có 2005 chữ số 9 đứng cạnh nhau liên tiếp. Dãy {an} tăng ngặt các số nguyên dương thoả mãn an <nCvới hằng số thực dương C nào đó. Chứng minh rằng dãy số {an} chứa vô hạn các số kim cương 2005.
24. 26 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC 3.2 Định lý F ermat nhỏ và một ứng dụng đẹp Bài toán 3.2.1 (Định lý F ermat nhỏ). Với số nguyên tố p cho trước và số tự nhiên n tuỳ ý thì np − n chia hết cho p. Định lý này đã quá quen thuộc với các bạn, cách chứng minh truyền thống là sử dụng phép ghép cặp và hệ thặng dư. Tuy nhiên chúng tôi muốn mời các bạn thưởng thức lại một cách chứng minh tuyệt đẹp của bài toán (3.2.1). Cách chứng minh này khác với cách chứng minh thông thưởng sử dụng hệ thặng dư, mặc dù trong hai cách thì cách thứ hai có thể mở rộng để chứng minh kết quả mạnh hơn của định lý F ermat (định lý Euler) dễ dàng hơn. Chứng minh bài toán (3.2.1). Sử dụng phép đếm. Ta chia một vòng tròn thành p phần đều nhau 1, 2, , p và tô các phần đó bằng 1 trong n màu cho trước. Hai cách tô được gọi là đồng dạng nếu qua một phép quay chúng trở thành một hình duy nhất. Đếm số các lớp mà mỗi lớp bao gồm tất cả các cách tô đồng dạng với nhau. Ta có số cách tô là np, nếu trong một lớp các cách tô đồng dạng với nhau có 2 cách tô khác nhau thì lớp đó có đúng p phần tử (nghĩa là p cách tô sai khác nhau một phép quay). Chỉ có đúng p lớp mà mỗi lớp chứa đúng n phần tử giống hệt nhau (tương ứng với n cách tô toàn bộ vòng tròn bằng một màu duy nhất). Vậy số lớp sẽ là: np − n . p Biểu thức này dĩ nhiên phải là một số nguyên. Điều đó chứng tỏ np − n chia hết cho p. Về tầm quan trọng của định lý này có lẽ nên dành hẳn một chuyên khảo để viết về nó, tuy nhiên trong bài viết này chúng tôi chỉ muốn giới thiệu một bài toán "nhỏ" và khá thú vị, có thể chứng minh trực tiếp đẹp mắt bằng định lý này nhờ kết hợp với đẳng thức thú vị: 1 1 1 = + . (3.4) 2 3 6 Bài toán 3.2.2 (IMO 2005). Tìm tất cả các số nguyên dương nguyên tố cùng nhau với mọi phần tử của dãy: n n n an =2 +3 +6 − 1 n ≥ 1. Chứng minh bài toán (3.2.2). Ta sẽ chứng minh rằng với số nguyên tố p bất kì đều tồn tại bội số của p là phần tử của dãy {an}. Thật vậy, rõ ràng là 2|a1 =10và 3|a2 =48, xét một số nguyên tố p>3 bất kì. Sử dụng định lý F ermat nhỏ ta có biến đổi sau: 2p−1 3p−1 6p−1 a =2p−2 +3p−2 +6p−2 − 1= + + − 1 p−2 2 3 6 1 1 1 ≡ + + − 1modp ≡ 0modp. 2 3 6 Biến đổi thứ 3 đúng vì chúng ta có đẳng thức (3.4). Đây là một đẳng thức rất đơn giản nhưng nó lại có nhiều ứng dụng rất thú vị, không chỉ riêng trong bài toán này.
25. 3.3. MỘT SỐ TÍNH CHẤT CỦA HÀM TỔNG CÁC CHỮ SỐ 27 3.3 Một số tính chất của hàm tổng các chữ số Đối với số tự nhiên n = a1a2 an ta xét S(n)=a1 + a2 + + an và gọi S là hàm tổng các chữ số. Trong mục này chúng tôi sẽ trình bày một số tính chất cùa hàm số này. Bài toán 3.3.1. Chứng minh 3 tính chất cơ bản của hàm S(n): (1) S(a) ≤ a với mọi số tự nhiên a (2) S(a + b) ≤ S(a)+S(b) với mọi số tự nhiên a,b (3) S(ab) ≤ S(a)S(b) với mọi số tự nhiên a,b. Ba tính chất này là những hiểu biết ban đầu về hàm S(n), mặc dù đơn giản nhưng đều rất quan trọng. Chứng minh không quá khó khăn vì vậy các bạn hãy tự chứng minh chúng. Bây giờ mời các bạn đến với 2 kết quả đẹp đẽ sau đây: Bài toán 3.3.2. Giả sử 10k − 1|M với k ∈ N khi đó S(M) ≥ 9k. lời giải. Đặt M = at a1a0. Với mọi i ∈{0, 1, , k − 1} ký hiệu: Si = X aj. j≡i mod k Theo giả thiết 10k − 1|M =⇒ 10k − 1|10lM với mọi l =0, 1, , k − 1. Do đó ta có: k−1 k−2 1 0 k Sk−110 + Sk−210 + + S110 + S010 chia hết cho 10 − 1  0 k−1 2 1 k − Sk−110 + Sk−210 + + S110 + S010 chia hết cho 10 1  k−2 k−3 0 1 k Sk−110 + Sk−210 + + S110 + S010 chia hết cho 10 − 1. k−1 k−1 k Suy ra (Sk−1 + + S0)(10 + +10+1)≥ k(10 − 1) =⇒ S(M)=P Si ≥ 9k. i=0 Bài toán 3.3.3. S((10k − 1)m)=9k với mọi 1 ≤ m ≤ 10k. t lời giải. Đặt m = a1a2 as10 với as =06 ,s≤ k. Ta có: k S((10 − 1)m)=S(a1a2 as−1 99 9 (9 − a1) (9 − as−1)(10 − as)) k|−{zs số}9 s−1 s−1 = X ai +9+9+ +9+ X (9 − ai)+(10− as) i=1 | k −{zs số 9 } i=1 =9k Điều phải chứng minh. Lời Bình. Hai kết quả trên là những tính chất đẹp của hàm S(n), trong đó đẳng thức ở bài toán (3.3.3) là một đẳng thức tuyệt vời. Với hai kết quả này, ta có thể giải quyết một loạt các bài toán, trong đó có một bài toán đẹp đẽ sau:
26. 28 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC Bài toán 3.3.4 (USAMO 2005). Đặt A = {1, 2, , n}. Gọi f(n) là giá trị nhỏ nhất của số tự nhiên k có tính chất tồn tại n số nguyên dương phân biệt x1,x2, , xn thoả mãn:   S X xi = k với mọi I ∈ A, I =6 φ. i∈I Chứng minh rằng tồn tại 0 1 và nguyên tố cùng nhau với 10. Rõ ràng nếu k thoả mãn bài toán thì t cũng vậy. Sử dụng định lý Euler ta có: 10ϕ(t) − 1 t|10ϕ(t) − 1=⇒ = a a a . t 1 2 ϕ(t)
27. 3.3. MỘT SỐ TÍNH CHẤT CỦA HÀM TỔNG CÁC CHỮ SỐ 29 Trong cách viết trên các chữ số ai có thể bằng 0. Ta lại có: 10mϕ(t) − 1 B = m t 10ϕ(t) − 1 = (10ϕ(t))m−1 + +10ϕ(t) +1 t = B1B1 B1 | {zm } 10mϕ(t) + t − 1 =⇒ B +1= = B B B +1. m t 1 1 1 | {zm } Vì t>1 nên a1a2 aϕ(t) t− 1 ta có ngay: S(10mϕ(t) + t − 1) = 1 + S(t − 1). (3.6) 10mϕ(t) + t − 1 Tóm lại ta đã xét dãy các số tự nhiên sau đây A = . m t S(tAm) 1+S(t − 1) Giả sử phản chứng, từ (3.5) và (3.6) ta suy ra ct ≤ ≤ . Cho m →∞suy S(Am) m − 1 ra ct =0. Mâu thuẫn. Vậy ta có điều phải chứng minh. Một câu hỏi mở là đánh giá: S(kN) inf  | k ∈ N. S(N) Bài toán 3.3.6. Chứng minh rằng tồn tại k số tự nhiên a1,a2, , ak sao cho: an + S(an)=am + S(am) ∀1 ≤ n, m ≤ k. lời giải. Ta chứng minh bằng quy nạp theo n rằng tồn tại n số tự nhiên khác nhau đôi một a1,a2, , an thoả mãn a1 + S(a1)=a2 + S(a2)= = an + S(an). Thật vậy, với n =2chọn a1 =98, a2 = 107 thì 98 + S(98) = 115 = 107 + S(107). Giả sử rằng khẳng định đã đúng tới n và a1 + S(a1)=a2 + S(a2)= = an + S(an)=ls. Rõ ràng tồn tại l ∈{1, 2, , 9} để 9|s +2l, đặt s +2l =9m. Dễ thấy m lớn hơn số chữ số của các số ai, i =1, 2, , n. Xét các số sau đây: 0 m (ai =10 + ai i =1, 2, , n 0 m an+1 =10 − l. 0 0 m Khi đó ai + S(ai)=10 +1+s với i =1, 2, , n +1. Vậy ta có điều phải chứng minh. Các tính chất về hàm tổng các chữ số còn nhiều, nhưng chúng tôi tạm kết thúc bài viết bằng hai bài toán. Một bài là đề thi của Nga, còn bài kia là một bài toán "mới":
28. 30 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC Bài toán 3.3.7. Giả sử a, b, c là các số tự nhiên thoả mãn S(a + b),S(b + c),S(c + a) đều nhỏ hơn 5. Hãy tìm giá trị lớn nhất của S(a + b + c). Bài toán 3.3.8. Với mỗi số tự nhiên n = at a2a1 xét hàm số T (n)=10 X ai + X ai. i chẵn i lẻ Hãy tìm số nguyên dương A nhỏ nhất sao cho tồn tại các số tự nhiên n1,n2, , n148 và m1,m2, , m149 thoả mãn ba điều kiện: A = n1 + n2 + + n148 = m1 + m2 + m149  T (n1)=T (n2)= = T (n148) T (m1)=T (m2)= = T (m149). 3.4 Hai ứng dụng của phương trình Pell Phương trình Pell cổ điễn là phương trình có dạng x2 − Dy2 =1trong đó D là số nguyên dương không là bình phương của một số tự nhiên. Bằng cách sử dụng lý thuyết liên phân số, dùng bổ đề Dirichlet hay phương pháp hình học với các đường hypecbol người ta đã chứng minh được rằng phương trình Pell luôn có ít nhất một nghiệm. Từ việc có nghiệm ta có thể thấy ngay rằng phương trình Pell có vô hạn nghiệm. Thật vậy, nếu (x, y) là một nghiệm thì (2x2 − 1, 2xy) cũng là một nghiệm, các bạn có thể kiểm tra điều này bằng các phép biến đổi tương đối đơn giản. Vấn đề là tìm công thức tổng quát của tất cả các nghiệm. Để làm điều đó cần đến khái niệm nghiệm cơ sở. Trong số các nghiệm, ta lấy ra một nghiệm (x0,y0) có tổng x0 + y0 nhỏ nhất có thể, khi đó (x0,y0) gọi là một nghiệm cơ sở. Khi đó tất cả các nghiệm của phương trình Pell sẽ là: √ √ (a + b D)n +(a − b D)n  √ xn =  √ 2 D √ (a + b D)n − (a − b D)n yn = √ .  2 D Việc chứng minh chi tiết định lý này không thuộc phạm vi bài viết, các bạn có thể sử dụng phương pháp gen (sẽ được dẫn ra trong một ví dụ ở phần sau) để thực hiện công việc này. Mục đích của chúng tôi là trình bày với các bạn hai ứng dụng đặc sắc của những hiểu biết về phương trình Pell vào các bài toán số học. Bài toán 3.4.1 (TST VMO 2005). Tìm tất cả các hàm số f : Z → Z thoả mãn đồng nhất thức sau với các số nguyên x, y, z bất kỳ: f(x3 + y3 + z3)=(f(x))3 +(f(y))3 +(f(z))3.
29. 3.4. HAI ỨNG DỤNG CỦA PHƯƠNG TRÌNH PELL 31 lời giải. Ta sẽ tìm một đẳng thức dạng a3 + b3 + c3 = d3 + e3 + f 3 đúng với n bất kỳ, trong đó các biến a, b, c, d, e, f đều phụ thuộc n. Đây là ý tưởng chính và việc thực hiện nó sẽ dẫn ta tới với phương trình Pell. Thật vậy, ta có: (x+l)3 −(x−l)3 =(y +h)3 −(y −h)3 +(z −t)3 −(z +t)3 ⇐⇒ 3lx2 +l3 =3hy2 +h3 −3tz2 −t3. Vì mục đích của ta là tìm một công thức truy hồi có chứa n nên ta có thể chọn x = n, l =1 khi đó đẳng thức trên trở thành: 3n2 +1=3hy2 + h3 − 3tz2 − t3. (3.7) Từ (3.7) suy ra h − t ≡ 1mod3, chọn h =2,t =1vậy (3.7) tương đương với 3n2 +1= 6y2 +8− 3z2 − 1 ⇐⇒ 3n2 − 6=6y2 +8− 3z2 − 1 ⇐⇒ n2 − 1=2y2 − z2. Ta lại có: (2.12 − n2 =2− n2 2.52 − 72 =1 =⇒ 2 − n2 =(2.12 − n2)(2.52 − 72) √ √ √ √ =( 2.1 − n)( 2.1+n)( 2.5 − 7)( 2.5+7) √ √ √ √ =[( 2.1 − n)( 2.5 − 7)][( 2.1+n)( 2.5 + 7)] √ √ =[7n +10− 2(5n + 7)][7n +10+ 2(5n + 2)] =(7n + 10)2 − 2(5n +7)2. Và như thế 2(5n +7)2 − (7n + 10)2 = n2 − 2, ta có thể chọn y =7n +10,z =5n +7.Cuối cùng ta có đẳng thức: (n + m)3 − (n − m)3 =(5n +9)3 − (5n +5m)3 +(7n +9m)3 − (7n +11m)3. Đến đây thì bằng phép quy nạp đơn giản (các bạn tự thực hiện) ta có: 0 với mọi x ∈ Z nếu f(1) = 0  f(x)=x với mọi x ∈ Z nếu f(1) = 1 −x với mọi x ∈ Z nếu f(1) = −1. Bài toán 3.4.2 (TST VMO 2002). Tìm tất cả các đa thức P (x) hệ số nguyên sao cho đa thức sau là bình phương của một đa thức hệ số nguyên: Q(x)=(x2 +6x + 10)(P (x))2 − 1. lời giải. Giả sử tồn tại đa thức hệ số nguyên R(x) ∈ Z[x] thoả mãn Q(x)=(R(x))2.Do x2 +6x +10=(x +3)2 +1> 0 và (R(x))2 ≥ 0 nên P (x) =06 với mọi x ∈ R. Có thể giả sử P (x) > 0 với mọi x ∈ R và như thế bậc của P là chẵn, đặt deg(P )=2n. Từ giả thiết ta có (m2 + 1)(P (m − 3))2 − 1 là số chính phương với mọi giá trị m nguyên, nên theo định lý về phương trình Pell suy ra tồn tại f : N → N sao cho với mọi m ∈ N thì: 1 √ √ P (m − 3) = √ (m + m2 +1)2f(m)+1 − (m − m2 +1)2f(m)+1. 2 m2 +1
30. 32 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC P (x) Gọi a là hệ số bậc cao nhất của P (x), a =06 và vì deg(P )=2n nên lim = a =06 . Từ đó x→∞ x2n suy ra tồn tại 2n +1số nguyên dương phân biệt x1,x2, , x2n+1 sao cho 2f(xi)+1=2n +1 với 1 ≤ i ≤ 2n +1. Xét đa thức: 1 √ √ A(x)=P (x − 3) − √ (x + x2 +1)2n+1 − (x − x2 +1)2n+1. 2 x2 +1 Ta có deg(A) ≤ 2n mà A(xi)=0với mọi i = 1, 2n +1 suy ra A(x)=0(một đa thức bậc k không có quá k nghiệm) 1 √ √ =⇒ P (x − 3) = √ (x + x2 +1)2n+1 − (x − x2 +1)2n+1. 2 x2 +1 Đổi biến, ta thu được: 1 √ √ P (x)= √ (x +3+ x2 +6x + 10)2n+1 − (x +3− x2 +6x + 10)2n+1. 2 x2 +6x +10 3.5 Định lý phần dư Trung Hoa Bài toán Hàn Tín điểm binh là một bài toán nổi tiếng đến mức hầu như học sinh tiểu học nào cũng đã từng nghe nói đến. Đó cũng là xuất phát điểm cho định lý Trung Hoa về phần dư mà chúng tôi sẽ phát biểu và chứng minh ngay bây giờ. Bài toán 3.5.1. Xét hệ phương trình đồng dư bậc nhất một ẩn: x ≡ b1 mod m1  x ≡ b2 mod m2 (H)   x ≡ bn mod mn. Chứng minh rằng (H) có nghiệm nếu và chỉ nếu (mi,mj)=dij|bi − bj với 1 ≤ i<j≤ n. lời giải. Ta chứng minh hai chiều của định lý. Chiều thuận làn hiển nhiên, vì ta có: (x = timi + bi x = tjmj + bj =⇒ dij =(mi,mj)|tjmj − timi = bi − bj. Ngược lại, ta xét trường hợp {mi} đôi một nguyên tố cùng nhau (đây chính là định lý Trung Hoa). Ta đã biết với số nguyên x điều kiện cần đủ để tồn tại số nguyên y mà xy ≡ 1modn là (x, n)=1. Thật vậy, nếu (x, n)=1thì theo định lý Bezout ta có tồn tại các số nguyên u, v sao cho ux + vn =1suy ra ux ≡ 1modn. Chiều ngược lại là điều hiển nhiên. n M Bây giờ đặt M = Q mi và Mi = . Theo nhận xét thì với mỗi i =1, 2, , n đều tồn i=1 mi
31. 3.5. ĐỊNH LÝ PHẦN DƯ TRUNG HOA 33 n tại ci sao cho Mici ≡ 1modmi.Lấyx = P Mibici, đây rõ ràng là nghiệm của hệ (H). i=1 k βci Bây giờ xét trường hợp (mi,mj)=dij|bi − bj với mọi 1 ≤ i 0. Ta có 52 − 34.12 +32 =0và tồn tại j để 3j ≡ 1modm =⇒ m|(5j)2 − 34j2 +1. Ta lại có 32 − 34.12 +52 =0, và theo định lý Euler thì 5ϕ(3α) ≡ 1mod3α 2 2 α ϕ(3α)−1  ϕ(3α)−1 =⇒ 3 3 · 5 − 34 5 +1. Theo bài toán (3.5.1) tồn tại x, y thoả mãn hai hệ đồng dư: (x ≡ 5j mod m (y ≡ j mod m x ≡ 3 · 5ϕ(3α)−1 mod 3α x ≡ 5ϕ(3α)−1 mod 3α.
32. 34 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC Khi đó rõ ràng là n|x2 − 34y2 +1. Đây là điều phải chứng minh. Cuối cùng, mời các bạn sử dụng định lý phần dư Trung Hoa để giải một số bài toán sau đây: Bài toán 3.5.3. Tìm tất cả các số tự nhiên n có tính chất tồn tại số nguyên m mà 2n − 1 là ước số của m2 +9. Bài toán 3.5.4. Cho đa thức hệ số nguyên P (x) và tập hợp hữu hạn các số nguyên p1,p2, , pr khác 0 thoả mãn với mọi số nguyên n thì P (n) là bội của số pi nào đó. Chứng minh rằng khi đó tồn tại chỉ số i mà pi|P (n) với mọi n ∈ Z. Bài toán 3.5.5. Giả sử a1,a2, , an là n số nguyên đôi một khác nhau và b1,b2, , bn là n số nguyên tuỳ ý. Chứng minh rằng với số tự nhiên t cho trước tồn tại duy nhất một đa thức với các hệ số là ±0, ±1, , , ±(t − 1) sao cho f(ai) ≡ bi mod t với mọi i =1, 2, , n. Lời Bình. Hãy chú ý đến dạng của bài toán (3.5.5) trong trường số thực, khi đó có duy nhất một đa thức hệ số thực P (x) thoả mãn P (ai)=bi với i =1, 2, , n. Chứng minh điều này các bạn có thể sử dụng công thức nội suy Lagrange quen thuộc. 3.6 Biểu diễn số Các bài toán thuộc dạng toán biểu diễn số rất đa dạng và phong phú. Có nhiều bài trong số chúng thuộc loại kinh điển như bài toán biểu diễn một số thành tổng các bình phương, lập phương, . Đó đều là những bài toán rất thú vị nhưng trong bài viết này chúng tôi không có ý định tổng kết lại các kết quả kinh điển đó mà xét đến các bài toán về biểu diễn các số hữu tỉ. Vấn đề thứ nhất chúng tôi đặt ra ở đây là tìm hiểu việc phân tích một số hữu tỉ dương dưới dạng tổng các lập phương của k số hữu tỉ dương. Rõ ràng định lý F ermat đã nói lên rằng k không thể bằng 2.Vậyk nhỏ nhất có thể bằng bao nhiêu. Câu trả lời là 3, chính xác hơn ta có bài toán sau đây: Bài toán 3.6.1. Mọi số hữu tỉ dương đều có thể biểu diễn vô hạn cách thành tổng các lập phương của ba số hữu tỉ dương. lời giải. Xét số hữu tỉ dương r. Luôn tồn tại số hữu tỉ v sao cho: r3r √ 3 1,mà3u(1 − u2) 0. 3 Vậy x, y, z đều là các số hữu tỉ dương. Lại có: (x3 + y3 + z3 =(s − t)3 +(t − z)3 + z3 = s3 − 3(s2 − z2)t +3(s − z)t2 3(s2 − z2)t =3s2(1 − u2)t = s3
33. 3.6. BIỂU DIỄN SỐ 35 s3(1 − u) s3 v3(1 + u)2 v3(1 + u) =⇒ x3+y3+z3 =3s(1−u)t2 = = = = = r. 3(1 − u2)2 3(1 + u)(1 − u2) 3(1 − u2) 3(1 − u) Do đó r là tổng các lập phương của√3 số hữu tỉ dương. Để chứng minh số cách biểu diễn này là vô hạn ta có thể chọn v đủ gần 3 3r. Khi đó z = su sẽ đủ nhỏ. Do vậy ta có thể tạo ra vô hạn cách biểu diễn theo cùng cách như trên. Từ đây ta có các hệ quả sau: Hệ quả 3.6.1. Mọi số hữu tỉ đều là tổng các lập phương của 3 số hữu tỉ. Hệ quả 3.6.2. Với số nguyên dương n bất kỳ, phương trình x3 + y3 + z3 = nt3 có vô hạn nghiệm nguyên dương nguyên tố cùng nhau. Hệ quả 3.6.3. Với số nguyên dương k ≥ 3, bất kỳ số hữu tỉ dương nào cũng có thể biểu diễn vô hạn cách dưới dạng tổng các lập phương của k số hữu tỉ dương. Từ hệ quả 3.6.3 vấn đề đặt ra ở trên đã được giải quyết trọn vẹn. Ngoài ra lời giải trên còn cho ta phương pháp phân tích một số hữu tỷ thành tổng các lập phương của 3 số hữu tỉ. Chẳng hạn như với r =3/5 thì: 3 86 3 73 3 18 3 = r =   +   +   . 5 105 735 49 √ Bây giờ ta cải tiến cách chứng minh định lý trên bằng cách chọn v đủ nhỏ và v> 3 3r sao 2 cho u2 0, y>0,và 3 x>0. Kết quả này dẫn ta tới với định lý sau: Bài toán 3.6.2. Bất kỳ số hữu tỉ dương nào cũng có thể biểu diễn vô hạn cách dưới dạng x3 + y3 − z3 trong đó x, y, z là các số hữu tỉ dương. Hệ quả của bài toán 3.6.2 thu được bằng cách áp dụng cho số r + t3 với t là số thực dương: Hệ quả 3.6.4. Bất kỳ số hữu tỉ dương nào cũng có thể biểu diễn dưới dạng x3 + y3 − z3 − t3 trong đó x,y,z,t là các số hữu tỉ dương. Chúng ta xét đến vấn đề thứ hai, biểu diễn một số hữu tỉ r dương dưới dạng: a3 + + a3 r = 1 n 3 3 b1 + + bn với a1, , an và b1, , bn là các số nguyên dương. Câu hỏi đặt ra là với n bằng bao nhiêu thì có thể biểu diễn được như vậy. Trước hết hiển nhiên thấy rằng n>1. Ta xét các trường hợp đơn giản của n. Trường hợp n =2. Xét a1,a2,b1,b2 là các số nguyên dương sao cho a1 = b1. Khi đó: 3 3 2 2 a1 + a2 (a1 + a2) (a1 − a1a2 + a2) 3 3 = 2 2 . b1 + b2 (b1 + b2) (b1 − b1b2 + b2)
34. 36 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC 2 2 2 2 Ta chọn các số sao cho a1 − a1a2 + a2 = b1 − b1b2 + b2, chẳng hạn chọn a1 = a2 + b2 a3 + a3 2a + b ⇒ 1 2 2 2 = 3 3 = . b1 + b2 a2 +2b2 Nếu 1/2 1. Khi đó mọi số hữu tỉ dương đều biểu diễn được dưới dạng: 3 3 a1 + + an 3 3 b1 + + bn trong đó a1, , an và b1, , bn là các số nguyên dương. Như vậy vấn đề thứ hai cũng đã được giải quyết trọn vẹn. Bây giờ tương tự hóa dạng biểu diễn trong vấn đề thứ hai ta có bài toán sau: Bài toán 3.6.4. Chứng minh rằng với mọi số hữu tỷ dương r đều tồn tại các số nguyên dương a, b, c, m, n, p thỏa mãn: a2 + b3 + c5 r = . (3.8) m7 + n11 + p13 lời giải. Giả sử p là một số nguyên tố, với số tự nhiên n ký hiệu vp(n) là số mũ của p trong phân tích chính tắc của n. Ta chứng minh một nhận xét: Nhận xét. Với các số tự nhiên t, s, m, n trong đó (m, n)=1, khi đó tồn tại các số tự nhiên a, b thỏa mãn amt = bns.
35. 3.7. MỘT DẠNG PHƯƠNG TRÌNH DIOPHANTE ĐẶC BIỆT 37 Chứng minh. Giả sử p là số nguyên tố, sử dụng định lý Bezout ta có thể tìm các số nguyên không âm αp,βp thỏa mãn αpm − βpn = vp(s)=vp(t). Dễ dàng chứng minh rằng: a = Y pαp ,b= Y pβp  thỏa mãn điều kiện trên. Nhận xét được chứng minh. Với số thực dương r chúng ta chọn các số tự nhiên a, b, c, m, n, p thỏa mãn a2 = rm7, b3 = rn11 và c5 = rp13. Khi đó rõ ràng (3.8) được thỏa mãn. Điều phải chứng minh. Bài toán 3.6.4 là một bài toán dễ, nhưng nếu có một chút thay đổi nhỏ, chẳng hạn thay đổi vai trò của dấu cộng và dấu trừ, ta sẽ có những bài toán khó. Mà dưới đây là một ví dụ: Bài toán 3.6.5. Cho số nguyên dương n>1. Tìm số nguyên dương nhỏ nhất không có dạng na − nb với bất kỳ các số nguyên dương a, b, c, d nào đó. nc − nd Các bạn hãy tự giải bài toán này xem như một bài tập. 3.7 Một dạng phương trình Diophante đặc biệt Trong mục này chúng tôi muốn ghi chép lại lời giải của ba phương trình Diophante nghiệm tự nhiên sau đây: 4xy − x − 1=z2 (3.9) 4xy − x − y = z2 (3.10) 4xyz − x − y = t2. (3.11) Trong đó (3.9) và (3.10) là những phương trình của Euler, Golbach đã cho (3.9) một lời giải đẹp đẽ. Euler đã mô phỏng cách chứng minh đó để giải quyết (3.10). Công việc cuối cùng là sử dụng các ký hiệu Jacobi (mở rộng của ký hiệu Legendre) và luật thuận nghịch bậc hai để giải quyết trọn vẹn (3.11). Bài toán 3.7.1. Chứng minh rằng phương trình (3.9) không có nghiệm tự nhiên. lời giải. Giả sử phản chứng, gọi a là số nhỏ nhất có tính chất tồn tại m, n tự nhiên mà: 4mn − m − 1=a2. (3.12) Cộng 4m2 − 4ma vào cả hai vế của (3.12) ta được: 4m(n − a + m) − m − 1=(a − 2m)2. (3.13) Dễ dàng chứng minh được: a mthì
36. 38 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC n − a + m 2a. (3.15) Thật vậy, cộng 4(n − 1)2 − 2a(4n − 1) vào hai vế của (3.13) ta được: (4n − 1)(m − 2a +4n − 1) − 1=(a − (4n − 1))2 ⇐⇒ 4n(m − 2a +4n − 1) − (m − 2a +4n − 1)+1=(a − (4n − 1))2. Do đó z = |a−(4n−1)| thỏa mãn (3.9), theo cách xác định của số a ta dễ dàng suy ra (3.15). Từ (3.12), (3.14), (3.15) ta suy ra a2 +1 = (4n − 1)m>2a.a =2a2 =⇒ a2 (4n − 1)(4m − 1) =⇒ 4n − 1 > 2a. Vì (3.16) là đối xứng với m, n nên cũng với lý luận tương tự như trên ta có 4m − 1 > 1. Đặt: (4m − 1=2a + p 4n − 1=2a + q. Trong đó p, q là các số tự nhiên. Như vậy (4n − 1)(4m − 1)=4a2 +2a(p + q)+pq, do đó từ (3.17) suy ra 2a(p + q)+pq =1với các số tự nhiên a, p, q. Điều này là vô lý. Bài toán được chứng minh xong. Bài toán 3.7.3. Chứng minh rằng (3.11) không có nghiệm tự nhiên.
37. 3.7. MỘT DẠNG PHƯƠNG TRÌNH DIOPHANTE ĐẶC BIỆT 39 lời giải. Ta sử dụng ký hiệu Jacobi trong chứng minh, bạn đọc nào chưa rõ lý thuyết này có thể đọc phần chú thích ngay sau đây. Giả sử phản chứng rằng (x,y,z,t) là nghiệm tự nhiên của (3.11). Thế thì: 4zt2 +1 =4zx − 1 4yz − 1 là một số nguyên, tức là: (2zt)2 ≡−z mod (4yz − 1). (3.19) Giả sử rằng z =2αz0 với a là số nguyên không âm, z0 là số tự nhiên lẻ. Khi đó sử dụng các tính chất của ký hiệu Jacobi ta có: −z −1 2α z0   =    . 4yz − 1 4yz − 1 4yz − 1 4yz − 1 z0 − 1 z0 − 1 4yz − 1 −1 Thừa số thứ nhất bằng −1, thừa số thứ ba bằng  (−1) 2 =  (−1) 2 = z0 z0 1. Nếu a =2k +1 với số nguyên không âm k và z =2z00 thì thừa số thứ hai bằng 2 2   =   =1. Nếu a =2k với số nguyên không âm k thì nó bằng 4yz − 1 8yz00 − 1 2 −z   =1=⇒   = −1. Điều này mâu thuẫn với đồng dư thức (3.19). Bài 4yz − 1 4yz − 1 toán được chứng minh xong. Luật thuận nghịch bậc 2. (The law of reciprocity) Đối với số nguyên tố p và số nguyên a nguyên tố cùng nhau với p ta xét ký hiệu Legendre như sau: a (1 nếu tồn tại x ∈ Z mà x2 ≡ a mod p   = p −1 nếu không tồn tại x ∈ Z mà x2 ≡ a mod p. Chứng minh tiêu chuẩn Euler: p − 1 a   ≡ a 2 mod p. p  p − 1 Tiếp theo chứng minh bổ đề Gauss: gọi s là số phần tử của tập hợp ia1 ≤ i ≤ mà 2 khi chia cho p số dư nhận được lớn hơn p/2.Vớia>1, (a, p)=1, khi đó: a   =(−1)s. p Chứng minh tiếp đẳng thức Cayley: với hai số nguyên tố lẻ p, q khác nhau ta có: p − 1 q − 1 2 2 iq jq p − 1 q − 1 X   + X   = · . p q 2 2 i=1 j=1
38. 40 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC Suy ra luật thuận nghịch bậc hai: với hai số nguyên tố lẻ p, q khi đó ta có: p − 1 q − 1 p q ·   ·   =(−1) 2 2 . q p ti Ký hiệu Jacobi được định nghĩa như sau: với số tự nhiên lẻ n = Q pi và số nguyên a nguyên tố cùng nhau với n, khi đó: a a ti   = Y   . n pi Trong đó ở vế phải là các ký hiệu Legendre. Khi đó cũng có luật thuận nghịch bậc hai cho ký hiệu Jacobi: với hai số tự nhiên lẻ nguyên tố cùng nhau m và n ta có: m − 1 n − 1 m n ·   ·   =(−1) 2 2 . n m 3.8 Số nguyên phức Giới thiệu. Các số nguyên phức Gauss lần đầu tiên được sử dụng bởi Gauss trong bài nghiên cứu của ông về sự tương hỗ bậc hai, ông được coi là người đầu tiên sử dụng số phức trong số học một cách rất rõ ràng và mạch lạc. Lớp các số này có tầm quan trọng nhất định trong số học sơ cấp. Trong mục này chúng tôi sẽ đề cập đến những khái niệm và tính chất cơ bản của số nguyên phức Gauss (mà sau này ta sẽ gọi là số nguyên phức) đồng thời cũng đưa ra một số ví dụ để minh họa cho các tính chất đó. 3.8.1 Các khái niệm mở đầu Số nguyên phức là các số có dạng a + bi trong đó i là đơn vị ảo, a, b là các số nguyên. Khi đó hiển nhiên thấy rằng với các phép toán cộng và nhân trong trường số phức giữa các số phức Gauss ta cũng thu được một số phức Gauss. Với một số phức z = a + bi (a, b ∈ R) thì số z0 = a − bi được gọi là số phức liên hợp của z. Như vậy một số là số nguyên phức khi và chỉ khi số phức liên hợp của nó cũng là số nguyên phức. Ta có thể dễ dàng chứng minh các tính chất cơ bản sau của số phức liên hợp: (z0)0 = z  0 0 0 Nếu z = u + v thì z = u + v Nếu z = u − v thì z0 = u0 − v0  0 0 0 Nếu z = uv thì z = u v . Ta nói rằng một số nguyên phức z chia hết cho một số nguyên phức t nếu và chỉ nếu tồn tại số nguyên phức u sao cho z = tu, khi đó viết là t|z. Rõ ràng nếu a + bi, c + di là các số nguyên phức trong đó c + di khác 0 thì ta có thương số: a + bi (a + bi)(c − di) ac + bd bc − ad = = + · i. c + di c2 + d2 c2 + d2 c2 + d2
39. 3.8. SỐ NGUYÊN PHỨC 41 Như vậy c + di|a + bi nếu và chỉ nếu c2 + d2|ac + bd và c2 + d2|bc − ad. Hơn nữa ta có các tính chất cơ bản sau: (Nếu u|t và t|z thì u|z Nếu t|zi với i =1, 2, , n thì t|z1u1 + z2u2 + + znun với mọi u1,u2, , un. Bây giờ ta sẽ làm quen với khái niệm chuẩn của một số phức. Chuẩn của một số phức là tích giữa nó và số phức liên hợp của nó. Nếu kí hiệu chuẩn của số phức z là N(z) thì N(z)=zz0. Hơn nữa nếu z = a + bi trong đó a, b là các số thực thì N(z)=a2 + b2. Các bạn đọc có thể dễ dàng chứng minh các tính chất sau: N(z)=N(z0)  N(uv)=N(u)N(v) z|t =⇒ N(t)|N(z). Hai số nguyên phức khác 0 thỏa mãn số này chia hết cho số kia được gọi là hai số nguyên phức liên kết. Như vậy z,t là hai số nguyên phức liên kết nếu và chỉ nếu z|t và t|z. Từ đây N(z)|N(t) và N(t)|N(z) do đó N(t)=N(z) suy ra hai số nguyên phức liên kết với nhau thì chuẩn của chúng bằng nhau. Ta còn có thêm một số tính chất cơ bản: (Nếu z liên kết với t thì z0 cũng liên kết với t0 Nếu z chia hết cho t thì mọi số liên kết với z đều chia hết cho mọi số liên kết với t. Bây giờ ta sẽ tìm các số nguyên phức u liên kết với một số nguyên phức z cho trước. Theo định nghĩa thì z = tu vàdođóN(z)=N(t)N(u). Theo tính chất ở trên ta có N(z)=N(t) =06 suy ra N(u)=1. Viết u = a + bi thì N(u)=a2 + b2 =1. Điều này chỉ xảy ra trong các trường hợp (a, b) ∈{(0, 1), (0, −1), (1, 0), (−1, 0)}. Kiểm tra đơn giản chiều ngược lại ta có 4 số phức liên kết của z là z,−z,iz,−iz. Ta có định lý sau: Định lý 3.8.1. Bất kì số nguyên phức z khác 0 nào cũng có đúng 4 số nguyên phức liên kết với nó là z,−z,iz,−iz. 3.8.2 Thuật toán Euclid và ước chung lớn nhất của hai số nguyên phức Định lý 3.8.2. Nếu z và t là các số nguyên phức khác 0 thì tồn tại số nguyên phức c và r 1 sao cho z = ct + r và N(r) ≤ N(t). 2 z Chứng minh. Ta có thể viết = x + yi trong đó x, y là các số hữu tỉ. Gọi α và β là các t số nguyên gần x, y nhất. Đặt x1 = x − α và y1 = y − β. Khi đó x1,y1 là các số hữu tỉ và 1 |x |, |y |≤ . Ta chọn c = α + βi, r = z − ct =(x + y i). Không khó khăn để kiểm tra các 1 1 2 1 1 số này thỏa mãn các điều kiện của định lý.
40. 42 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC Từ định lý này ta có thuật toán Euclid tìm được dãy các số nguyên phức r0,r1, sao cho các số ti là các số nguyên phức thỏa mãn: r0 = t, r1 = r  ri = tiri+1 + ri+2 với mọi i =0, 1, 2, N(ri+1) <N(ri) Dãy này còn tiếp tục chừng nào ri còn khác 0. Nhưng chú ý rằng dãy chuẩn N(ri) là dãy các số tự nhiên giảm dần nên dãy ri không thể kéo dài vô hạn. Do đó bắt buộc phải tồn tại số nguyên n sao cho rn−2 = tn−2rn−1 hay có thể qui ước rằng rn =0. Dễ dàng nhận thấy từ kết quả này rn−1 sẽ là số cùng chia hết z và t hơn nữa nó chia hết cho mọi ước số chung của hai số này. Như vậy ta có hệ quả (định nghĩa): Hệ quả 3.8.1. Với hai số nguyên phức khác 0 cho trước thì có ít nhất một ước số chung chia hết cho mọi ước số chung khác của hai số đấy. Các ước số chung như vậy được gọi là các ước số chung lớn nhất của hai số này. Từ đây ta cũng có khái niệm uớc chung lớn nhất cho nhiều số và các số nguyên phức nguyên tố cùng nhau . Các số nguyên phức được gọi là nguyên tố cùng nhau nếu chúng không có ước chung nào khác ±1, ±i. Một định lý rất quan trọng khi nghiên cứu vấn đề về ước số chung lớn nhất, là mở rộng của định lý Bezout cho các số nguyên. Định lý 3.8.3. Hai số nguyên phức nguyên tố cùng nhau nếu và chỉ nếu tồn tại các số nguyên phức x, y sao cho ax + by =1. Chứng minh. Chiều ngược lại là dễ dàng. Ta sẽ chứng minh chiều thuận. Giả sử (a, b)=1. Ta gọi S là tập hợp các số có dạng az + bt trong đó z,t cũng là các số nguyên phức không đồng thời bằng 0. N(S) được kí hiệu là tập hợp các chuẩn của các phần tử trong S. Rõ ràng luôn tồn tại phần tử nhỏ nhất trong N(S). Giả sử phần tử này bằng n. Khi đó tồn tại α ∈ S sao cho N(α)=n. Do α ∈ S nên luôn tồn tại z1,t1 là các số nguyên phức không đồng thời bằng 0 sao cho α = az1 + bt1. Ta chứng minh mọi phần tử s ∈ S đều chia hết cho α. Thật vậy, với s = az + bt ∈ S ta viết s = cα + r trong đó N(r) <N(α). Mặt khác r = a(z − cz1)+b(t − ct1) nên nếu r =06 thì r ∈ S. Điều này mâu thuẫn với cách chọn α vì N(r) <N(α). Vậy r =0hay ta có nếu s ∈ S thì s chia hết cho α. Vì a, b ∈ S do đó a, b đều chia hết cho s.Vì(a, b)=1nên suy ra N(s)=1. Không giảm tổng quát ta có thể giả sử s =1. Khi đó sẽ tồn tại x = z1; y = z2 là các số nguyên phức không đồng thời bằng 0 sao cho ax + by =1. Định lý được chứng minh. Từ định lý này ta có thể rút ra các hệ quả sau:
41. 3.8. SỐ NGUYÊN PHỨC 43 Hệ quả 3.8.2. Với bất kỳ các số nguyên phức a, b, c sao cho (a, b)=1và b|ac thì b|c. Hệ quả 3.8.3. Nếu (a, b)=1và (a, c)=1thì (a, bc)=1. 3.8.3 Số phức nguyên tố và vấn đề phân tích các số nguyên phức Chúng ta đã biết rằng bất kỳ số nguyên phức z nào không liên kết với 1 cũng có ít nhất 8 ước số là 1, −1,i,−i, z, −z,iz,−iz. Từ đây người ta định nghĩa một số nguyên phức là số nguyên phức nguyên tố nếu nó có đúng 8 ước số phân biệt. Điều này tương đương với khẳng định một số nguyên phức là số nguyên phức nguyên tố nếu nó có chuẩn lớn hơn 1 và không biểu diễn được thành tích của hai số phức có chuẩn lớn hơn 1. Như vậy các số phức liên kết và liên hợp với một số phức nguyên tố cũng là các số phức nguyên tố. Như vậy số nguyên phức nguyên tố là mở rộng của khái niệm số nguyên tố trong Z. Vấn đề bây giờ được đặt ra (tương tự như trong Z) là phân tích một số nguyên phức thành tích các số nguyên phức nguyên tố. Dễ thấy rằng các số nguyên phức nguyên tố chỉ có một cách phân tích duy nhất (là chính nó). Vậy thì với các số nguyên phức trong trường hợp tổng quát thì sao. Ta có định lý sau: Định lý 3.8.4. Bất kỳ một số nguyên phức nào có chuẩn lớn hơn 1 cũng là tích của hữu hạn các số nguyên phức nguyên tố. Chứng minh. Ta dùng phản chứng để chứng minh định lý này. Gọi M là tập hợp các số có chuẩn lớn hơn 1 nhưng không phân tích được thành tích của hữu hạn các số nguyên phức nguyên tố và N là tập hợp các chuẩn của các số phức trong M. Nếu M khác rỗng, suy ra N khác rỗng. Do N là tập các số nguyên dương nên luôn tồn tại phần tử nhỏ nhất. Ta gọi phần tử này là m. Khi đó tồn tại số phức z ∈ M sao cho N(z)=m. Hiển nhiên z không là số nguyên tố và N(z)=m>1. Do đó theo định nghĩa về số nguyên tố ta suy ra tồn tại các số nguyên phức u, v sao cho u, v 6∈ {1, −1,i,−i, z, −z,iz,−iz} thỏa mãn z = uv. Khi đó N(u)N(v)=N(z)=m.Dou và v khác tám giá trị nêu trên nên N(u),N(v) > 1=⇒ 1 <N(u),N(v) <m. Theo cách chọn m ta có u, v 6∈ M.Màu, v có chuẩn lớn hơn 1 nên chúng phân tích được thành tích hữu hạn các số nguyên phức nguyên tố. Từ đó z cũng phân tích được thành tích hữu hạn các số phức nguyên tố. Mâu thuẫn với cách chọn z. Vậy giả sử của ta là sai hay M phải là tập rỗng. Do vậy ta có điều phải chứng minh. Các bạn có thể chứng minh được rằng nếu ta quy ước các cách phân tích một số nguyên phức thành các nhân tử nguyên tố là giống nhau nếu tập các chuẩn của nó không thay đổi thì mỗi số nguyên phức có chuẩn lớn hơn 1 đều phân tích được duy nhất thành tích các số nguyên phức nguyên tố.
42. 44 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC Định lý 3.8.4 và chú ý ở trên là rất quan trọng. Nó đem lại cho số nguyên phức các tính chất gần gũi với số nguyên trong dạng phân tích thành tích các số phức nguyên tố. Có thể khám phá nhiều tính chất tương tự với những tính chất quen thuộc trong Z. Chẳng hạn: Định lý 3.8.5. Cho các số nguyên phức z1,z2, , zn đôi một nguyên tố cùng nhau và có tích là lũy thừa cấp n của một số nguyên phức. Khi đó mỗi số zi cũng là lũy thừa của một số nguyên phức. Lý thuyết về các số nguyên phức còn rất nhiều điều thú vị, những nghiên cứu chi tiết và sâu sắc hơn chúng ta sẽ còn quay trở lại trong một bài viết khác. Bây giờ, với những hiểu biết ban đầu trên đây, chúng ta thử vận dụng để giải một số bài toán tương đối quen thuộc. 3.8.4 Sử dụng số nguyên phức để giải một số bài toán Bài toán 3.8.1. Cho a, b, c là các số nguyên dương sao cho (b, c)=1. Biết rằng tồn tại n nguyên dương lớn hơn 1 sao cho an = b2 + c2. i) Chứng minh rằng a là tổng của hai số chính phương. p +1 ii) Biết rằng n = trong đó p là số nguyên tố lẻ có dạng 4k +3 (trong đó k nguyên 2 dương). Chứng minh rằng tích bc chia hết cho p. lời giải. Ta có phân tích an =(b + ci)(b − ci). Gọi d =(b + ic, b − ic) suy ra: d|(b + ic) − (b − ic)=2ic =⇒ N(d)|N(2ic)=4c2. (3.20) Tương tự d|(b + ic)+(b − ic)=2b =⇒ N(d)|4b2. (3.21) Lại có N(d)|N(b + ic)=b2 + c2. Chú ý rằng b, c nguyên tố cùng nhau do đó b2 + c2 lẻ suy ra N(d) lẻ. Vậy N(d)|b2 và N(d)|c2. Cũng do (b, c)=1và N(d) nguyên không âm nên ta có N(d)=1.Vậyb + ic, b − ic nguyên tố cùng nhau. n Từ tính chất này suy ra tồn tại các số nguyên x, y sao cho b + ic = t1(x + iy) và b − ic = n 2 2 t2(x−iy) trong đó t1,t2 ∈{1, −1,i,−i} và t1t2 =1. Hệ quả của công thức trên là a = x +y là tổng hai số chính phương. Đây là nội dung cần chứng minh của (i). p +1 Với n = trong đó p là số nguyên tố dạng 4k +3 (k>1). Khi đó có hai trường 2 hợp sau xảy ra: Trường hợp 1: (b + ic)2 =(x + iy)p+1, (b − ic)2 =(x − iy)p+1. Trường hợp 2: (b + ic)2 = −(x + iy)p+1, (b − ic)2 = −(x − iy)p+1. Trong cả hai trường hợp sau khi đem hai biểu thức trừ cho nhau và đồng nhất phần thực phần ảo ta đều có |2bc| =(p + 1)(xpy − ypx). Theo định lý nhỏ Fermat ta có bc chia hết cho p. Đây là yêu cầu của (ii). Bài toán được chứng minh hoàn toàn. Bài toán 3.8.2. Tìm tất cả các số nguyên dương n sao cho n3 − 1 là số chính phương.
43. 3.9. PHƯƠNG TRÌNH CARMICHAEL 45 lời giải. Giả sử n3 −1=k2. Lý luận như bài toán 3.8.1, từ phân tích n3 =(k −i)(k +i) ta có k − i và k + i nguyên tố cùng nhau. Do đó tồn tại các số nguyên a, b sao cho k − i =(a − bi)3 và k + i =(a + bi)3. Đồng nhất phần thực và phần ảo ta suy ra 3a2b − b3 = −1. Dễ dàng thấy a =0,b=1. Do đó giá trị duy nhất của n thỏa mãn là n =1. Một ứng dụng đặc sắc nữa của số nguyên phức Gauss là chứng minh định lý tổng hai bình phương đã được giới thiệu ở phần trước của tài liệu, các bạn hãy tìm lại chứng minh đó. Bài toán 3.8.3. Ký hiệu d1(n) và d3(n) lần lượt là số các thừa số nguyên tố đồng dư 1 mod 4 và đồng dư 3 mod 4 trong phân tích chính tắc của số tự nhiên n, gọi số cách biểu diễn n dưới dạng tổng hai bình phương, khi đó: (0 nếu d (n) ≤ d (n) f(n)= 1 3 4(d1(n) − d3(n)) nếu d1(n) >d3(n). Ngoài loại số nguyên phức này ra còn có các G− số, là các số√ có dạng xJ +√yO trong đó x, y 1+i 3 1 − i 3 là số nguyên và J, O là các căn bậc 3 của đơn vị âm J = , I = . Sử dụng loại 2 2 số này ta có thể chứng minh định lý F ermat trong trường hợp n =3, chính xác hơn là chứng minh định lý đó trên tập các G− số. Chứng minh chi tiết và việc khảo sát các tính chất của các G− số hẹn các bạn một dịp khác thích hợp hơn. 3.9 Phương trình Carmichael Phương trình Carmichael là phương trình nghiệm nguyên có dạng x2 + y2 + z2 = t2. Phương trình này có vô hạn nghiệm nguyên xác định bởi đẳng thức: d2(m2 − n2 − p2 + q2)2 + d2(2mn − 2pq)2 + d2(2mn +2pq)2 = d2(m2 + n2 + p2 + q2)2. Bài toán sau đây cho ta hiểu biết về cấu trúc nghiệm của phương trình này: Bài toán 3.9.1 (Định lý Carmichael). Bởi vì không có số chính phương nào chia 4 dư 3 nên trong 3 số x, y, z phải có ít nhất 2 số chia chết cho 2, giả sử đó là y và z. Chứng minh rằng tất cả các nghiệm của phương trình Carmichael có dạng: y =2l, z =2m  l2 + m2 − n2 x = n l2 + m2 + n2 t = .  n √ Trong đó n|l2 + m2 và 0 x, đặt u = t − x>0 suy ra: =⇒ x2 +4l2 +4m2 =(x + u)2 =⇒ u2 =4l2 +4m2 − 2xu l2 + m2 − n2 =⇒ u =2n)=⇒ n2 = l2 + m2 − nx =⇒ x = n l2 + m2 + n2 =⇒ t = (Điều phải chứng minh.) n
44. 46 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC Chiều ngược lại là dễ dàng kiểm tra. Vấn đề của đặt ra là tình hình sẽ như thế nào nếu x,y,z,t không còn quá thoải mái, chính xác hơn, nếu cho các biến đó thêm một ràng buộc thì kết quả sẽ thay đổi như thế nào, chẳng hạn bài toán sau: Bài toán 3.9.2. Giải phương trình nghiệm nguyên dương x2 − (a2 + b2) · y4 =1. Theo chúng tôi được biết bài toán này chưa có câu trả lời trọn vẹn, chúng ta sẽ khảo sát nó trong một trường hợp đặc biệt, khi a = b =2bài toán đã có lời giải. Nhưng trước hết chúng ta cần điểm lại một số hiểu biết về các phương trình dạng P ythagore. Bài toán 3.9.3 (Phương trình P ythagore). Tất cả các nghiệm nguyên thủy của phương trình nghiệm nguyên dương x2 + y2 = z2 đều cho bởi công thức (x = m2 − n2,y =2mn, z = m2 + n2) (không tính các hoán vị), trong đó (m, n)=1và m, n khác tính chẵn lẻ, m>n. Bài toán 3.9.4. Chứng minh rằng trong tập các số nguyên không âm, nếu có đẳng thức x4 + y4 = z2 thì trong hai số x, y có một số bằng 0. Chứng minh bài toán 3.9.3 đã quá quen thuộc với các bạn, dựa vào kết quả của bài toán ấy và sử dụng phương pháp xuống thang có thể chứng minh bài toán 3.9.4 không quá khó khăn. Một dạng tương tự của bài toán 3.9.4 là: Bài toán 3.9.5. Chứng minh rằng trong tập các số nguyên không âm, nếu có đẳng thức x4 − y4 = z2 thì y =0. Lời giải bài toán này không có liên hệ cụ thể với bài toán trên, mà là hệ quả trực tiếp của một định lý đẹp đẽ sau của F ermat: Bài toán 3.9.6. Chứng minh rằng y =0nếu x,y,z,t là các số nguyên không âm thỏa mãn: (x2 + y2 = z2 x2 − y2 = t2. lời giải. Nếu y>0, giả sử (x, y)=1và z là nhỏ nhất có thể được. Ta có 2x2 = z2 + t2 suy z + t z + t 2 z − t 2 z + t z + t ra ∈ Z =⇒ x2 =   +   .Mà ,  =1. Từ bài toán 3.9.3 suy 2 2 2 2 2 ra tồn tại các số tự nhiên m, n nguyên tố cùng nhau sao cho: z − t z + t  = m2 − n2  = m2 − n2  2  2 z + t hoặc z − t =2mn =2mn  2  2 =⇒ 2y2 = z2 − t2 =2.4mn(m2 − n2) =⇒ y2 =4(m2 − n2)mn, y =2k =⇒ k2 =(m2 − n2)mn. Mà (m, n)=1, (m2 − n2,mn)=1suy ra m2 − n2 = c2, m = a2,n= b2 nhưng như thế a2 ± b2 đều là số chính phương. Do m + n<z2, điều này trái với giả thiết về tính cực tiểu của z.
45. 3.10. MỘT SỐ BÀI TOÁN KHÁC 47 Mẫu thuẫn chứng tỏ y =0. Các bài toán về phương trình dạng P ythagore rất đa dạng và phong phú, trong trường hợp này những kết quả nho nhỏ ở trên lại rất có ích trong việc giải phương trình Carmichael ở trường hợp rất đặc biệt sau đây: Bài toán 3.9.7. Chứng minh rằng phương trình x2 −8y4 =1chỉ có hai nghiệm nguyên không âm là (x =1,y =0)và (x =3,y =1). lời giải. Viết phương trình dưới dạng x2 =(2y2)2 +(2y2)2 +1. Nếu x =1thì y =0, xét x =16 . Theo định lý Carmichael (bài toán 3.9.1) suy ra l = m = y2 và 2l2 = n(n +1).Ta xét hai trường họp sau đây. Nếu n =2α4 và n +1 = β4 suy ra β4 − 2α4 =1=⇒ β4 +(α2)4 =(α4 +1)2. Theo bài toán 3.9.4 suy ra α =0suy ra n =0. Loại. Nếu n = α4 và n +1 = 2β4 suy ra α4 − 2β4 = −1=⇒ (β2)4 − α4 =(β4 − 1)2. Theo bài toán 3.9.5 suy ra α = β =1và như thế n =1.Vậyx =3,y =1. 3.10 Một số bài toán khác Bài toán 3.10.1. Giả sử p là một số nguyên tố. Chứng minh rằng trong 2p − 1 số nguyên bất kì đều tồn tại p số có tổng là bội số của p. lời giải. Ký hiệu S(X)= P x và |X| là số phần tử của tập hợp X bất kì. Giả sử phản x∈X chứng rằng tồn tại tập hợp S gồm 2p − 1 số nguyên a1,a2, , a2p−1 nào đó có tính chất tổng của p phần tử bất kì của S đều không phải bội số của p. Như vậy ∀A ⊂ S, |A| = p thì S(A) 6≡ 0modp từ đây ta suy ra (S(A))p−1 ≡ 1modp: 2p − 1 =⇒ S = X (S(A))p−1 ≡   6≡ 0modp. p |A|=p Để chỉ ra mâu thuẫn ta sẽ chứng minh rằng S ≡ 0modp. Thật vậy, biến đổi như sau: − p−1 p−1 (p 1)! α1 α2 αp (S(A)) =(ai + ai + + ai ) = X .a a a . 1 2 p α !α ! α ! i1 i2 ip α 1 2 p p Các tổng được lấy trên tất cả các bộ α =(α1,α2, , αp),αi ≥ 0, P αi = p − 1 i=1 (p − 1)! (p − 1)! =⇒ S = X X .aα1aα2 aαp = X X .aα1aα2 aαp. α !α ! α ! i1 i2 ip α !α ! α ! i1 i2 ip α 1 2 p α 1 2 p (ai1 ,ai2 , ,aip) (ai1 ,ai2 , ,aip) Ta chứng minh với mỗi bộ α =(α1,α2, , αp) cố định tổng sau là bội số của p: X α1 α2 αp X α1 α2 αp T = ai1 ai2 aip = av(1)av(2) av(p). v (ai1 ,ai2 , ,aip)
46. 48 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC Tổng được lấy trên tất cả các đơn ánh v : {1, 2, , p}→{1, 2, , 2p − 1}. Gọi αj1 ,αj2 , , αjm với m ≤ p − 1 là các phần tử có giá trị dương trong các số α1,α2, , αp. Rõ ràng ta chỉ cần 2p−1−m quan tâm tới các giá trị v(j1)=v1,v(j2)=v2, , v(jm)=vm. Vì có đúng p−m
    đơn ánh như thế này nên chúng ta có: 2p − 1 − m   αj1 αj2 αj T = X av av a m . p − m 1 2 vm v Mặt khác ta có: 2p − 1 − m (2p − 1 − m)!   = . p − m (p − m)!.(p − 1)! Biểu thức này trước hết là một số nguyên, hơn nữa vì 1 ≤ m ≤ p − 1 nên trên tử số ít nhất một nhân tử là bội của p (chính là p) còn dưới mẫu thì không do đó biểu thức này là bội số của p.VậytacóT cũng là một bội số của p. Đây là điều ta đang cần chứng minh. Nếu thay số nguyên tố p bởi một số tự nhiên n bất kì thì kết quả của bài toán vẫn đúng, các bạn có thể chứng minh điều đó theo hai cách. Trong đó một cách sử dụng kết quả vừa chứng minh ở trên, còn cách thứ hai, các bạn hãy thực hiện một phép quy nạp trực tiếp theo ước số nguyên tố lớn nhất của các số đó. Tuy nhiên cách đơn giản và đẹp đẽ nhất có lẽ là cách chứng minh dựa trên bổ đề nhỏ sau: Bổ đề. Trong n số nguyên bất kỳ đều tồn tại một số số có tổng chia hết cho n. Chứng minh bổ đề này khá đơn giản, các bạn hãy tự thực hiện (bằng cách sử dụng nguyên lý Dirichlet). Công việc của chúng ta là áp dụng bổ đề vào bài toán sau: Bài toán 3.10.2. Chứng minh rằng trong 2n − 1 số nguyên bất kỳ đều tồn tại n số có tổng chia hết cho n. lời giải. Gọi m là số lớn nhất thoả mãn tính chất có m số đồng dư với nhau theo modun n. Nếu m ≥ n thì chỉ cần chọn n số đồng dư với nhau modun n, bộ số này có tổng chia hết cho n. Nếu m ≤ 2 thì tồn tại n số phân biệt theo modun n.Vớin lẻ ta chọn n số phân biệt theo modun n,vớin chẵn ta chọn n − 1 số phân biệt modun n và không chia hết cho n. Trong các trường hợp còn lại ta có thể giả sử m số này đều chia hết cho n, nếu không ta có thể đem tất cả 2n − 1 số trừ đi số dư chung modun n của m số này. Xét 2n − 1 − m số còn lại, do 2n − 1 − m ≥ n nên tồn tại k số (k ≤ n) có tổng chia hết cho n (theo bổ đề). Nếu k + m ≥ n thì hiển nhiên chỉ cần chọn k số này và n − k số chia hết cho n. Nếu k + m 0 ta có bất đẳng thức: ϕ(n) − δ <ε n đúng với số tự nhiên n nào đó.
47. 3.10. MỘT SỐ BÀI TOÁN KHÁC 49 lời giải. Ký hiệu pk là số nguyên tố thứ k. Đặt ak =1− 1/pk.Dopk >knên: lim ak =1. k→+∞ Giả sử rằng p1,p2, , pk là tất cả các số nguyên tố không vượt quá n khi đó: k k pi  1 1  Y = Y 1+ + 2 + >ln(n) pi − 1 pi p i=1 i=1 i 1 =⇒ 0 thì ta có: 0 1 − δ 1 1 ak0 =1− > 1 − > 1 − (1 − δ)=δ. (3.23) pk0 k0 Từ (3.22), (3.23) suy ra tồn tại số nguyên không âm n sao cho: λ = ak0 ak0+1 ak0+n >δ>ak0 ak0+1 ak0+n+1 =⇒ 0 1+δ/ε. Cuối cùng để ý rằng: ϕ(p .p p ) λ = k0 k0+1 k0+n . pk0 .pk0+1 pk0+n Bài toán được chứng minh xong. Bài toán này là một tính chất rất kì lạ của phi hàm Euler, về hàm số này, bài toán sau cũng đẹp đẽ không kém: Bài toán 3.10.4. Ký hiệu ϕ(n) lần lượt là số các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n và π(n) là số các số nguyên tố không vượt quá n. Chứng minh rằng với mọi số tự nhiên n>1 ta có: π(n) ϕ(n) ≥ . 2 Bài toán 3.10.5. Cho số nguyên N và tập hợp A gồm hữu hạn các số nguyên dương. Chứng minh rằng tồn tại tập các số nguyên dương B chứa A sao cho: Y x − X x2 = N. x∈B x∈B
48. 50 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC lời giải. Ta chứng minh kết quả này bằng hai cách. 2 Cách 1. Đặt M = Qx∈A x và P = Px∈A x . Ta sẽ tìm tập hợp C các số nguyên dương phân biệt sao cho: M Y x = N + P + X x2. x∈C x∈C Trước hết để thử lý luận chọn C gồm m số 1 và k số 2. Khi đó ta có M.2k = N + P +4k. k k Chú ý rằng lim (M.2 − 4k)=+∞ nên tồn tại k0 sao cho M.2 − 4k>N+ P với mọi k→∞ k k ≥ k0. Với mỗi k ≥ k0, ta chọn số m = M.2 − 4k − N − P . Ta luôn chọn được nghiệm có dạng (1, 1, 1, , 1, 2, 2, 2). Thực hiện quy tắc sinh nghiệm như sau, nếu (x1,x2, , xn) là nghiệm thì (x1,x2, , xi−1,Mx1x2 xi−1xi+1, , xn − xi,xi+1, , xn) sẽ là nghiệm mới. Sử dụng quy tắc sinh nghiệm này ta có: (1, 1, 1, , 1, 2, 2, , 2) −→ (1, 1, 1, , 1, 2, 2, , 2,M.2k−1 − 2) −→ (1, 1, 1, , 1, 2, 2, , 2, 2k−2(M.2k−1 − 2) − 2,M.2k−1 − 2) −→ Từ đó ta sẽ tạo được nghiệm (x1,x2, , xn) mà các thành phân của nó là đôi một phân biệt. Bây giờ ta chọn C =(x1,x2, , xn) và B = A ∪ C. Bài toán được chứng minh. Cách 2. Với tập S bất kì ta ký hiệu d(S)= Q x − P x2. x∈S x∈S Chọn S0 = {1, 2, , m} sao cho S ⊂ X. Ta chọn m đủ lớn sao cho: m! − 1 − 2 − − m>N+ P. Xét dãy S0 = m! − 1, xn+1 = m!x1x2 xn − 1 và Sk = {1, 2, , m, x1,x2, , xk}. Dễ thấy d(Sk+1)=d(Sk) − 1 từ đó tồn tại k sao cho d(Sk)=N + P . Bài toán lại được chứng minh. Lời Bình. Lời giải 1 của bài toán trên là minh họa cho phương pháp gen trong phép giải phương trình nghiệm nguyên. Phương pháp gen là quy tắc xây dựng nghiệm phát sinh từ nghiệm ban đầu nhờ một phép gen hóa nào đó. Từ việc tạo được các nghiệm mới đó ta có thể nghiên cứu được tính chất các họ nghiệm dựa vào nghiệm cơ sở. Hai ứng dụng khá cơ bản của phương pháp gen là phương trình Pell và phương trình Markov (mà bài toán 3.10.5 đã thể hiện một biến thể của phương trình dạng Markov). Nhờ bài toán này ta có cách giải bài toán sau vốn là đề chọn đội tuyển Việt Nam dự thi toán quốc tế năm 2002, trong đó lời giải bài này chỉ là hệ quả bài trên hoặc sử dụng phương pháp trực tiếp như cách 1. Bài toán 3.10.6. Chứng minh rằng tồn tại số nguyên m0 sao cho với mọi số nguyên m ≥ m0 luôn tồn tại m số nguyên dương phân biệt a1,a2, , am sao cho N là số chính phương với: m 2 N = Y ai − 4 X ai . i=1 i=1 Bài toán 3.10.7. Cho k số tự nhiên 1 ≤ a1 ≤ a2 ≤ ≤ ak ≤ n thỏa mãn [ai,aj] >nvới mọi 1 ≤ i ≤ j ≤ k. Chứng minh rằng: k 1 3 k 1 6 (i) X < (ii) X < . a 2 a 5 i=1 i i=1 i
49. 3.10. MỘT SỐ BÀI TOÁN KHÁC 51 lời giải. Rõ ràng câu (i) là hệ quả của câu (ii), nên ta chỉ chứng minh câu (ii), tuy nhiên nếu đứng độc lập thì câu (i) cũng rất thú vị. Có thể giả sử rằng ak = n vì nếu ak <nthì khi thay n cho ak thì ta vẫn có các kết quả sau đây. Đặt Sn = {1, 2, , n}.Vớii =1, 2, 3 đặt ri là các số thuộc vào tập S[n/i] không là bội của bất kỳ số aj nào. Với m =2, 3, , n +1ta xét các tập hợp sau:  n n  Bm = ai <ai ≤ . m m − 1 n n Ký hiệu b là số các phần tử của tập B . Với mỗi số thuộc  ,  có đúng m − 1 bội m m m m − 1 số thuộc vào Sn suy ra Bm có đúng (m − 1)bm bội số thuộc vào Sn =⇒ b2 +2b3 + +(n − 1)bn = nr1. (3.24) Tương tự ta có các đẳng thức n b + b +2b +2b +3b + =   − r . (3.25) 3 4 5 6 7 2 2 n b + b + b +2b +2b +2b + =   − r . (3.26) 4 5 6 7 8 9 3 3 Từ các đẳng thức (3.24, 3.25, 3.26) ta suy ra 1 1 2(b − 1) 3b S = X ≤ + 2 + 3 + ai n n n 1 2b +3b + ≤− + 2 3 n n 1 2(n − r ) b +2b +3b +,,, = − + 1 − 3 4 5 n n n 1 2r [n/2] − r +[n/3] − r ≤ 2 − − 1 − 2 3 n n n 1 r + r − 2r [n/2] + [n/3] =2− + 2 3 1 − n n n 1 5 1/2+1/3 7 1 6 ≤ 2 − − + = + ≤ . n 6 n 6 6n 5 Đánh giá cuối cùng đúng với n ≥ 5 và thế là đủ để hoàn thành chứng minh. Thay cho lời kết. Như vậy là các bạn đã trải qua 9 bài viết nho nhỏ và một bài viết sau cùng tổng hợp khoảng 5 bài toán cùng với lời giải chi tiết của nó. Các bài toán nhỏ trên diễn đàn còn rất nhiều và có rất nhiều bài đáng để suy nghĩ, nghiền ngẫm, công việc đó sẽ dành cho các bạn ngay sau khi các bạn có trong tay cuốn tài liệu này. Còn bây giờ, trong phần cuối của tập Số Học này chúng tôi xin dẫn ra một bài viết chuyên đề về các tính chất của tổng các nghịch đảo tự nhiên.
50. 52 CHƯƠNG 3. MỘT SỐ CHỦ ĐỀ SỐ HỌC CHỌN LỌC
51. Chương 4 Tổng nghịch đảo Trần Mạnh Tuấn & Trần Quốc Hoàn Giới thiệu. Với mỗi số nguyên dương n tồn tại các số tự nhiên an và bn nguyên tố cùng nhau thoả mãn đẳng thức: 1 1 a S(n)=1+ + + = n . 2 n bn Vấn đề đặt ra là khảo sát tính chất của các số {an} và {bn}. Một cách cụ thể hơn mối quan hệ của các số đó với số nguyên tố p cho trước là như thế nào. Đây là một câu hỏi hay và rất khó! Một trường hợp riêng (quan trọng), đó là với n như thế nào thì an chia hết cho p. Theo chúng tôi được biết thì đây là một bài toán chưa có lời giải. Bài viết nhỏ này cũng chỉ thực hiện một vài khảo sát trong một số trường hợp đặc biệt. Để cho thống nhất, từ bây giờ nếu không có gì đặc biệt chúng ta quy ước p dùng để chỉ một số nguyên tố và với hai phân số tối giản a/b, c/d nếu có a ≡ c mod p và b ≡ d =06 a c mod p thì ta cũng viết ≡ mod p. Nếu a chia hết cho số nguyên x khác 0 thì ta cũng nói b d a/b chia hết cho x. Các ký hiệu đồng dư vẫn được sử dụng theo nghĩa mới này. Chúng ta bắt đầu với một vài kết quả nhỏ và quen thuộc. Mệnh đề 1. Chứng minh rằng ta có hai tính chất sau với số nguyên tố p ≥ 5: 2 (i) ap−1 chia hết cho p . (ii) ap2−p và ap2−1 chia hết cho p. lời giải. Sử dụng phép ghép cặp để chứng minh (i) và sử dụng (i) để chứng minh (ii). (i) p − 1 p − 1 p−1 2 2 1 1 1 1 Ta có S(p − 1) = X = X  +  = p · X . (4.1) k j p − j j(p − j) k=1 j=1 j=1 53
52. 54 CHƯƠNG 4. TỔNG NGHỊCH ĐẢO p − 1 p − 1 Nhận xét rằng với mỗi j ∈{1, 2, , } đều tồn tại x ∈ 1, 2, ,  sao cho (jx )2 ≡ 2 j 2 j 1modp với 1 ≤ j ≤ p − 1, và khi đó ta có: p − 1 {x ,x , , x }≡{1, 2, , }. 1 2 p − 1 2 2 Sử dụng nhận xét ta được: p − 1 p − 1 1 − p p +1 2 1 2 · · p X ≡ X (−x2)= 2 2 ≡ 0modp. (4.2) j(p − j) j 6 j=1 j=1 2 Đồng dư cuối cùng đúng với p ≥ 5. Kết hợp (4.1), (4.2) suy ra p |ap−1. Điều phải chứng minh. (ii) p−2 1 1 1 1 S(p2 − p)=X  + + +  + · S(p − 1). kp +1 kp +2 kp + p − 1 p k=0 Một hệ quả của câu (i) là p|ap−1 do đó ta có: 1 1 1 1 1 1  + + + ≡ + + + ≡ 0modp kp +1 kp +2 kp + p − 1 1 2 p − 1 1 p2|S(p − 1) =⇒ · S(p − 1) ≡ 0modp.  p Vậy S(p2 − p) ≡ 0modp. Tiếp tục biến đổi: 1 1 1 S(p2 − 1) − S(p2 − p)= + + + p2 − p +1 p2 − p +2 p2 − p + p − 1 1 1 1 ≡ + + + ≡ 0modp. 1 2 p − 1 Mệnh đề 2. Giả sử k là số nguyên không âm. Chứng minh rằng an không chia hết cho số nguyên tố lẻ p với mọi số tự nhiên n ∈ [pk, 2pk − 1]. lời giải. Trước hết ta phát biểu và chứng minh một nhận xét: Nhận xét. Với p là số nguyên tố lẻ và n là số nguyên dương, nếu an không chia hết cho p thì anp,anp+1, , anp+p−1 đều không chia hết cho p. Chứng minh. Thật vậy, vẫn bằng cách ghép cặp tương tự như đã sử dụng trong mệnh đề 1 ta có với mọi m nguyên không âm và số nguyên tố lẻ p thì: 1 1 1 + + + mp +1 mp +2 mp + p − 1
53. 55 chia hết cho p. Do đó với mọi k =0, 1, 2, , p − 1 ta có thể viết: a pa a c np+k = + n + bnp+k b pbn d trong đó a/b và c/d là các phân số tối giản và b, c không chia hết cho p. Từ đẳng thức này ta dễ dàng suy ra nếu an không chia hết cho p thì với mọi k =0, 1, 2, , p − 1 ta cũng có anp+k không chia hết cho p. Nhận xét được chứng minh. Bây giờ ta chứng minh mệnh đề 2.Doa1 không chia hết cho p, theo nhận xét suy ra ap,ap+1, , a2p−1 đều không chia hết cho p. Tương tự ta cũng có ap2 , , a2p2−1 không chia hết cho p. Tiếp tục quá trình này bằng cách sử dụng nhận xét ta thu được apk , , a2pk−1 đều không chia hết cho p. Đây là điều phải chứng minh. Sử dụng mệnh đề 2 cùng với bổ đề Dirichlet ta có kết quả thú vị sau: Mệnh đề 3. Cho trước các số nguyên dương N và T . Chứng minh rằng tồn tại m nguyên dương sao cho với k = m, m +1, , m + T ta đều có ak và N nguyên tố cùng nhau. Với số nguyên tố p tuỳ ý, các kết quả mới thu được là rất hạn chế. Việc xét một số trường hợp riêng của p có thể sẽ dễ dàng hơn. Thật vậy, với p =2, p =3và p =5bài toán đã được giải quyết trọn vẹn trong định lý dưới đây. Định lý. Tử số an chia hết cho 3 nếu và chỉ nếu n =2hoặc n =7.Vàbn không chia hết cho 5 khi và chỉ khi n nhận một trong các giá trị: 1, 2, 3, 4, 20, 21, 22, 23, 24, 100, 101, 102, 103, 104, 121, 122, 123, 124. lời giải. Ta chứng minh lần lượt 2 nội dung được nhắc đến trong định lý. (i) Ta cần sử dụng một nhận xét sau đây: Nhận xét. Nếu an chia hết cho 3 thì a[n/3] cũng chia hết cho 3. Chứng minh. Thật vậy, đặt k =[n/3], ta có các đẳng thức: a k 1 1 k 1 a k 6i +3 3k = X  +  + X = k + X . b3k 3i +1 3i +2 3i 3bk (3i + 1)(3i +2) i=1 i=1 i=1 Lập các đẳng thức tương tự cho các chỉ số 3k +1, 3k +2suy ra nhận xét được chứng minh. Bây giờ chú ý rằng hệ quả của nhận xét này là nếu a[n/3] không chia hết cho 3 thì an cũng vậy. Khảo sát các trường hợp riêng ta có a1 =1,a2 =3,a3 =11do đó chỉ cần quan tâm đến tiếp theo là a6,a7,a8. Nhưng do a6,a8 không chia hết cho 3, chỉ có a7 = 363 chia hết cho 3 nên ta chỉ cần quan tâm đến các số tiếp theo là a21,a22,a23. Ta kiểm tra các số này như sau.
54. 56 CHƯƠNG 4. TỔNG NGHỊCH ĐẢO a a c 121 c Với n =21hoặc n =23thì a không chia hết cho 3, bởi vì ta có n = 7 +3· = +3· n b 3b d 140 d c n 7 trong đó là phân số tối giản có mẫu số d không chia hết cho 3. d a22 121 c 1 1401 c Với n =22, cũng như trên ta có = +3· + = +3· nên a22 b22 140 d 22 1540 d cũng không chia hết cho 3. Vậy an chia hết cho 3 nếu và chỉ nếu n =2hoặc n =7. (ii) [n/5] n 1 1 S0(n)=X − X . k 5i i=1 k=i Ta quy ước A là dạng các phân số tối giản có mẫu số không chia hết cho 5. B là dạng các phân số tối giản có mẫu số chia hết cho 5, C là dạng các phân số tối giản có cả mẫu số và tử số không chia hết cho 5 và D là dạng các phân số tối giản có tử số không chia hết cho 5. Các đẳng thức mang tính chất tượng trưng như A + A =25A có nghĩa là tổng hai phân số dạng A là 25 lần của một phân số dạng A nào đó. 3 11 25 Ta có S(1) = 1,S(2) = ,S(3) = và S(4) = . Chú ý rằng: 2 6 12 1 1 1 1 1 1 + + + = (10k+5) +  =25A. 5k +1 5k +2 5k +3 5k +4 (5k + 1)(5k +4) (5k + 2)(5k +3) Do đó S0(n)=25A. Với mọi số tự nhiên n chia hết cho 5 hoặc chia 5 dư 4. Ta xét các trường hợp sau đây: Với n =5, 6, , 19 thì vì S([n/5]) ∈{S(1),S(2),S(3)} nên: 1 n 1 S(n)=S0(n)+ · S  = A + C = B. 5 5 5 n 25 Với n =20, 21, 22, 23, 24 thì ta có S  = S(4) = 5 12 1 5 =⇒ S(n)=S0(n)+ S(4) = S0(n)+ = A. 5 12 n Với n =25, 26, , 99 ta có S  = C 5 1 n 1 n 1 1 =⇒ S(n)=S0(n)+ S  + S  = A + A + C = B. 5 5 25 25 5 25 Với n = 100, 101, 102, 103, 104 thì: 1 1 1 S(n)=S0(n)+ S0(20) + S0(4) = A +5A + = A. 5 25 12
55. 57 Với n = 105, 106, , 119 ta có: 1 n 1 S(n)=S0(n)+ S  + . 5 5 12 1 n 1 1 Mà .S  ∈{S0(21),S0(22),S0(23)} và S0(21) = S0(20) + =25A + = C, tương 5 5 21 21 1 1 tự S0(22),S0(23) đều là dạng C. Vậy ta có S(n)=A + C + = B. 5 12 1 1 Với n = 120, 121, 122, 123, 124 ta có S(n)=S0(n)+ S0(24) + = A. 5 12 Với n ≥ 125. Gọi k là số nguyên dương nhỏ nhất sao cho 5k ≥ n. Khi đó: 1 1 1 1 S(n)= X + X = S(u)+ A. x x 5k−2 5k−3 5k−2|x 5k−2 không chia hết x Trong đó 25 ≤ u ≤ 124. Kiểm tra với u = 100, 101, 102, 103, 104, 120, 121, 122, 123, 124 ta thấy các phân số: 1 1 1 1 1 1 1 1 1 + , + + . + + + 5k +1 12 5k +1 5k +2 12 5k +1 5k +2 5k +3 12 đều có tử sô không chia hết cho 5. Vậy với các giá trị đó của u ta đều có S0(u)=5A. Suy ra: 1 u 1 D A S(u)=S0(u)+ S  + =5A +5A + D = D =⇒ S(n)= + = B. 5 5 12 5k−2 5k−3 Trong đó phân số dạng D này có tử số không chia hết cho 5. Vậy các giá trị cần tìm của n là 1, 2, 3, 4, 20, 21, 22, 23, 24, 100, 101, 102, 103, 104, 121, 122, 123 và 124. Định lý được chứng minh hoàn toàn. Chứng minh trên là một chứng minh trọn vẹn, nhưng có lẽ chưa thể hiện được cái cốt lõi của vấn đề. Bằng chứng là các bạn có thể cho rằng chứng minh đó sử dụng quá nhiều kỹ thuật. Theo chúng tôi, định lý sau đây có thể sẽ giúp ích các bạn độc giả nhìn nhận kết quả trên một cách sâu sắc hơn. Định lý. Giả sử p là một số nguyên tố lẻ thoả mãn hai điều kiện: (i) p − 1 là số nguyên dương nhỏ nhất trong các số r thoả mãn p|ar 1 (ii) S(p − 1) + S(r) có tử số không chia hết cho p với 1 ≤ r ≤ p − 1. p2 Khi đó bn không chia hết cho p nếu và chỉ nếu: ([1,p− 1] ∪ [p2 − p, p2 − 1] nếu p =3 n ∈ [1,p− 1] ∪ [p2 − p, p2 − 1] ∪ [p3 − p2,p3 − p2 + p − 1] ∪ [p3 − p, p3 − 1] nếu p =36 .
56. 58 CHƯƠNG 4. TỔNG NGHỊCH ĐẢO Rõ ràng là nếu p|an thì bn không chia hết cho p. Do đó n phải là một trong các số nêu 3 trên, hệ quả là an không chia hết cho p nếu n ≥ p . Nhận xét rằng các số nguyên tố 3, 5, 7, 13, 17, 19, 23, 29 đều có tính chất trên, câu hỏi là với trường hợp p =11thì sao, có điều gì khác biệt. Câu hỏi này xin dành cho bạn đọc suy nghĩ thêm. Để kết thúc chuyên đề này mời các bạn thưởng thức một bài toán tuyệt đẹp sau đây, đây là một bài toán hay và theo chúng tôi là rất khó. Tuy nhiên bằng cách sử dụng một số kết quả đã được trình bày ở trên, mọi chuyện sẽ vô cùng trong sáng và vô cùng rõ ràng. Bài toán. Chứng minh rằng an không phải luỹ thừa của một số nguyên tố với vô hạn giá trị tự nhiên của n. lời giải. Bổ đề an >n+1 với mọi n =4, 5, 6, Chứng minh Gọi k là số tự nhiên thoả mãn 2k ≤ n . Ta có với mọi n ≥ 4 thì: n 2 n 1 n +1 4 1 n +1 a = b X ≥ X > 2 = n +1. n n i 2 i 2 i=1 i=1 Ta sẽ chứng minh rằng với số nguyên tố lẻ p tuỳ ý trong dãy các số n = p, p2 − p, p2 − 1,p3 − 3 p p, p − 1, , p − 1 có ít nhất một số có tính chất an không phải luỹ thừa của một số nguyên tố. Giả sử phản chứng. Theo mệnh dề 1 ta có S(p − 1) chia hết cho p. Ta dùng quy nạp theo n ≤ p để chứng minh rằng S(pn − p) và S(pn − 1) chia hết cho p. Thật vậy, theo bổ đề thì n apn−1 >p và apn−1 chia hết cho p (mệnh đề 1), mà apn−1 là luỹ thừa của một số nguyên tố 2 =⇒ ap2−1 chia hết cho p . (4.3) Ta có các đẳng thức sau: 1 1 S(pn+1 − 1) = pn+1 · X + S(pn − 1). (4.4) k(pn+1 − k) p 1≤k≤pn+1−1 p không chia hết k 1 1 S(pn+1 − p)= X + S(pn − 1). (4.5) k p (k,p)=1 Kết hợp các kết quả (4.3), (4.4), (4.5) ta suy ra kết luận quy nạp. Sử dụng vào bài toán ta có: n n n p |S(p − 1) với n =1, 2, và p |apn−p với n =2, 3,  p−1 1 n − − n − − n n S(p 1) S(p p)+S(p 1) = p P n chia hết cho p .  i=1 p(p − i) p−1 n 1 Từ đó suy ra S(p − 1) chia hết cho p với mọi n.MàS(p − 1) = P <pvà bp−1 ≤ (p − 1)! i=1 i p suy ra ap−1 <p! <p Mâu thuẫn. Vậy ta có điều phải chứng minh.
57. Phần II Một số chủ đề Tổ Hợp 59
58. Chương 5 Bổ đề Sperner Nguyễn Quốc Khánh Giới thiệu. Trong Toán Học rất thường khi xuất hiện những kết quả mặc dù có cách phát biểu rất giản dị, nhưng lại tỏ ra rất quan trọng trong nhiều lĩnh vực sâu sắc. Trong bài viết này, tôi muốn ghi chép lại một số hiểu biết của mình về một kết quả như thế, trong tổ họp, người ta gọi kết quả này là bổ để Sperner, và ứng dụng quan trọng nhất của nó là tham gia vào chứng minh tổ hợp - giải tích của định lý điểm bất động Brower. Bổ đề Sperner. Các đỉnh của một tam giác được đánh số bởi các chữ số 0, 1, 2.Tam giác đó được chia thành một số tam giác sao cho không có một đỉnh của tam giác nào nằm trên cạnh của tam giác khác. Các đỉnh của tam giác ban đầu vẫn giữ nguyên các số cũ còn các đỉnh mới được đánh số bằng 0, 1, 2 sao cho mỗi đỉnh nằm trên cạnh của tam giác ban đầu được đánh số bởi một trong các số dùng để đánh số các đỉnh của cạnh đó. Chứng minh rằng tồn tại một tam giác nhỏ được đánh số bởi 0, 1, 2. Chứng minh. Xét các đoạn thẳng được phân ra từ cạnh 01, gọi a là số đoạn thẳng dạng 00, b là số đoạn thẳng dạng 01. Đối với mỗi đoạn thẳng xét số các số 0 đứng ở các đầu của nó, và cộng tất cả các số đó ta được 2a + b. Mặt khác, tất cả các số 0 nằm trong đều được tính hai lần, và thêm một số 0 đứng ở đỉnh của tam giác ban đầu. Do đó số 2a+b lẻ, suy ra b là số lẻ. 61
59. 62 CHƯƠNG 5. BỔ ĐỀ SPERNER Bây giờ ta xét đến phép chia tam giác. Giả sử a1 là tổng số các tam giác dạng 001 và 011, còn b1 là số các tam giác dạng 012. Đối với mỗi tam giác xét số các cạnh của nó có dạng 01 và cộng tất cả các số đó lại. Tổng cộng ta được 2a1 + b1. Mặc khác tất cả các cạnh nằm trong đều được tính hai lần trong tổng đó, còn tất cả các cạnh biên đều nằm trên cạnh 01 của tam giác ban đầu và số đó là lẻ theo lập luận ở trên. Do đó 2a1 + b1 là số lẻ, suy ra b1 là số lẻ và đó là điều phải chứng minh. Bổ đề Sperner rõ ràng là rất đơn giản, và chứng minh cũng rất dễ dàng. Vậy đâu là ý nghĩa sâu sắc của nó. Để chuẩn bị cho việc trình bày chứng minh tổ hợp - giải tích của định lý điểm bất động Brower dựa trên bổ đề Sperner chúng ta cùng làm quen vói một vài khái niệm của tôpô đại cương. Đó là các khái niệm về ánh xạ liên tục và ánh xạ đồng phôi. Hãy tưởng tượng rằng chúng ta có một quả bóng, bây giờ hãy làm bẹp nó đi. Khi dó có thể nói chúng ta đang dùng một ánh xạ liên tục tác động vào quả bóng. Hãy chú ý rằng qua ánh xạ này thì một đoạn nối hai điểm M,N trên bề mặt quả bóng không hề bị cắt đứt, nó vẫn "liên tục" như lúc đầu tiên. Nhưng nếu các bạn lại lấy một cái kim để chọc thủng quả bóng thì sao, đây vẫn là một ánh xạ, nhưng liệu có liên tục hay không. Câu trả lời thực sự là không (nhưng để chứng minh được điều này thì không hề đơn giản). Vậy là có những ánh xạ không liên tục, chúng ta có thể lấy một ví dụ khác rõ ràng hơn. Các bạn hãy xét một sợi dây, nếu các bạn thắt nút và cuốn vòng nó một cách tuỳ ý thì rõ ràng đây là một ánh xạ liên tục, tuy nhiên nếu bạn lấy kéo để cắt đôi sợi dây ra thì rõ ràng đây là một ánh xạ không liên tục. Với hai vật thể A và B trong không gian, nếu có một ánh xạ liên tục f có thể biến A thành B thì ta nói A và B đồng phôi với nhau. Chẳng hạn một cái bánh qui hình tròn và một cái bánh qui hình vuông đương nhiên là đồng phôi với nhau. Tất nhiên, có thể nói ngược lại rằng hai vật A, B không đồng phôi với nhau nếu và chỉ nếu không thể dùng một ánh xạ liên tục để biến từ vật này thành vật kia. Những vật thể như thế là rất nhiều, chẳng hạn một hình cầu và một hình cầu khác sau khi đã đục thủng một lỗ là không đồng phôi với nhau: Khái niệm đồng phôi là nền tảng của tôpô học, có thể hiểu một cách trực quan rằng không gian tôpô là một không gian không quan tâm nhiều đến khái niệm khoảng cách, trong không gian này ta chỉ quan tâm tới dạng của vật thể chứ không quan tâm xem nó dài rộng ra sao, nặng nhẹ thế nào. Trong không gian này thì ánh xạ liên tục là "luật pháp" tối cao. Một tính chất đặc biệt thú vị của các ánh xạ liên tục được phát biểu trong định lý sau đây.