Tài liệu Về tính chất đôi một nguyên tố cùng nhau

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ HẰNG VỀ TÍNH CHẤT ĐÔI MỘT NGUYÊN TỐ CÙNG NHAU LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ HẰNG VỀ TÍNH CHẤT ĐÔI MỘT NGUYÊN TỐ CÙNG NHAU Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8460113 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. TRẦN ĐỖ MINH CHÂU THÁI NGUYÊN - 2018 Mục lục Lời nói đầu 1 1 Giả thuyết Erdös về k số nguyên tố cùng nhau từng đôi một 3 1.1 Chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Về các số nguyên tố cùng nhau từng đôi một . . . . . . . . . . 6 1.3 Giả thuyết Erdös về k số nguyên tố cùng nhau từng đôi một . 9 1.4 Giả thuyết Erdös với k = 3 . . . . . . . . . . . . . . . . . . . . 14 2 Bộ các số nguyên tố cùng nhau từng đôi một 19 2.1 Bộ ba số không nguyên tố cùng nhau từng đôi một . . . . . . 19 2.2 Bộ các số nguyên tố cùng nhau từng đôi một 26 Kết luận . . . . . . . . . 44 Tài liệu tham khảo 45 1 Mở đầu Cho A là tập con của tập tích Đề Các {1, . . . , k}2 . Bộ (a1 , . . . , ak ) ∈ Zk được gọi là nguyên tố cùng nhau từng đôi một trên A nếu gcd(ai , aj ) = 1 với mọi (i, j) ∈ A. Trong trường hợp gcd(ai , aj ) = 1 với mọi 1 ≤ i < j ≤ k, bộ (a1 , . . . , ak ) ∈ Zk được gọi là nguyên tố cùng nhau từng đôi một. Nếu gcd(ai , aj ) 6= 1 với mọi 1 ≤ i < j ≤ k thì ta nói (a1 , . . . , ak ) không nguyên tố cùng nhau từng đôi một. Tính chất nguyên tố cùng nhau từng đôi một có vai trò quan trọng trong lý thuyết số. Nó là giả thiết không thể thiếu trong Định lý phần dư Trung Hoa nổi tiếng được chứng minh cách đây 750 năm (xem [11]). Cho đến nay, Định lý này vẫn được áp dụng rất nhiều trong các lĩnh vực khác nhau của toán học hiện đại như nhân đồng dư; tính toán bắc cầu; lý thuyết mã hóa và mật mã ... (xem [6]). Ngày nay, việc tính toán các bộ nguyên tố cùng nhau từng đôi một là rất cần thiết để xác định được số các bộ không nguyên tố cùng nhau từng đôi một (xem [8], [14]). Chính vì các lý do này, tôi đã chọn đề tài "Về tính chất đôi một nguyên tố cùng nhau". Mục đích thứ nhất của luận văn là trình bày lại một số kết quả về giả thuyết của Erdös cho trường hợp k = 1, 2, 3, 4, dựa theo các bài báo [3] và [4]. Giả thuyết phát biểu rằng, số lớn nhất các số nguyên dương không vượt quá số nguyên dương n, sao cho từ các số này không thể trích ra k + 1 số nguyên nguyên tố cùng nhau từng đôi một đúng bằng số các số nguyên dương không vượt quá n và là bội của ít nhất một trong k số nguyên tố đầu tiên. Mục đích thứ hai của luận văn là trình bày lại kết quả của Randell 1 Heyman trong bài báo [9] về xây dựng các công thức gần đúng với sai số thích hợp để tính số bộ gồm ba số nguyên dương nhỏ hơn số H cho trước, không nguyên tố cùng nhau từng đôi một và số bộ gồm v số nguyên dương nhỏ hơn số H cho trước, nguyên tố cùng nhau từng đôi một trên một tập A xác định. Ngoài phần mở đầu và kết luận, luận văn gồm 2 chương. Chương 1 trình bày một số bài toán liên quan đến các số nguyên tố cùng nhau từng đôi một và chứng minh khẳng định cho giả thuyết của Erdös trong các trường hợp k ≤ 4. Chương 2 trình bày kết quả và chứng minh chi tiết các công thức tính gần đúng các bộ số nguyên dương nhỏ hơn số H và không nguyên tố cùng nhau từng đôi một hoặc nguyên tố cùng nhau từng đôi một trên một tập A dựa trên lý thuyết đồ thị và một số công cụ giải tích. Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên, dưới sự hướng dẫn tận tình của cô giáo TS. Trần Đỗ Minh Châu. Cô đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc mắc của tôi trong suốt quá trình làm luận văn. Tôi xin bày tỏ lòng biết ơn sâu sắc tới cô. Tôi xin chân thành cảm ơn toàn thể các thầy, cô giáo trong Khoa Toán - Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã tận tình hướng dẫn, truyền đạt kiến thức trong suốt thời gian theo học, thực hiện và hoàn thành luận văn. Tôi xin cảm ơn bạn bè, người thân và các đồng nghiệp đã giúp đỡ, động viên tôi để tôi hoàn thành luận văn này. Thái Nguyên, tháng 5 năm 2018 Người viết luận văn Nguyễn Thị Hằng 2 Chương 1 Giả thuyết Erdös về k số nguyên tố cùng nhau từng đôi một Mục tiêu của chương 1 là trình bày câu trả lời khẳng định cho giả thuyết của P. Erdös về k số nguyên tố cùng nhau từng đôi một khi k ≤ 4. Hai tiết đầu dành để nhắc lại khái niệm và một số tính chất cơ bản của ước, bội, ước chung lớn nhất, bội chung nhỏ nhất và một số bài toán về các số nguyên tố cùng nhau từng đôi một. Trong hai tiết tiếp theo, chúng tôi trình bày chi tiết chứng minh cho giả thuyết của Erdös khi k = 1, 2, 3. 1.1 Chuẩn bị Trong tiết này, chúng tôi nhắc lại một số khái niệm và tính chất cơ bản về ước, bội, ước chung lớn nhất, bội chung nhỏ nhất của các số nguyên, khái niệm các số nguyên tố cùng nhau từng đôi một để tiện cho việc theo dõi các nội dung phía sau. Định nghĩa 1.1.1. Giả sử a và b là hai số nguyên, b 6= 0. Ta nói b chia hết a hay a chia hết cho b nếu tồn tại số nguyên q sao cho a = bq. Khi ấy ta còn . nói b là ước của a hay a là bội của b và viết b | a hay a .. b. Khi b không chia hết a ta viết b - a. Ví dụ 1.1.2. −1, 1 là hai ước của mọi số nguyên a và 0 là bội của mọi số nguyên b 6= 0. 3 Trong trường hợp không xảy ra quan hệ chia hết, ta có định lý về phép chia có dư phát biểu như sau. Định lý 1.1.3. Với mọi cặp số nguyên a, b, b 6= 0 tồn tại duy nhất cặp số nguyên q, r thỏa mãn các hệ thức a = bq + r, 0 ≤ r < |b| . Hệ quả của Định lý 1.1.3 là vành các số nguyên Z là vành chính. Vì thế trong vành Z có các khái niệm ước chung lớn nhất, bội chung nhỏ nhất...Chúng ta sẽ lần lượt nhắc lại các kết quả về các khái niệm này ở trong Z, bỏ qua chứng minh. Định nghĩa 1.1.4. (i) Một số nguyên d được gọi là ước chung của các số nguyên a1 , a2 , . . . , an nếu d là ước đồng thời của mỗi số nguyên đó. (ii) Với mỗi số nguyên ai (i = 1, 2, . . . , n) ta kí hiệu U(ai ) là tập hợp các ước của ai . Hiển nhiên U(ai ) 6= ∅ và có hữu hạn phần tử. Rõ ràng Tn i=1 U(ai ) 6= ∅ và bị chặn trên bởi số lớn nhất trong các số |a1 |, |a2 |, . . . , |an | , do đó nó có số lớn nhất d. Hiển nhiên d là một chung của a1 , a2 , . . . , an và có thể thấy rằng mọi ước chung của a1 , a2 , . . . , an đều là ước của d. Định nghĩa 1.1.5. Một ước chung d của các số nguyên a1 , a2 , . . . , an sao cho mọi ước chung của a1 , a2 , . . . , an đều là ước của d, được gọi là ước chung lớn nhất của các số đó. Ví dụ 1.1.6. Các số 1, −1, 2, −2 là các ước chung của 4 và −6. Các ước chung lớn nhất của 4 và −6 là 2 và −2. Nhận xét 1.1.7. (i) Tập hợp các ước chung của nhiều số cho trước trùng với tập hợp các ước của ước chung lớn nhất của các số đó. (ii) Nếu tất cả các số a1 , a2 , . . . , an đều bằng 0 thì tập hợp các ước chung của chúng là Z \ {0}. Khi ấy khái niệm ước chung lớn nhất không có nghĩa nữa. Do đó giả thiết các số a1 , a2 , . . . , an đang xét không phải bằng 0 tất cả. Hơn nữa tập hợp các ước chung của các số đang xét sẽ không thay đổi nếu 4 ta thêm hay bớt một số bằng 0. Vì thế ta có thể giả thiết thêm ai 6= 0 với mọi i = 1, 2, . . . , n. (iii) Nếu d là một ước chung lớn nhất của (a1 , a2 , . . . , an ) thì −d cũng một ước chung lớn nhất của (a1 , a2 , . . . , an ). Hơn nữa nếu d và d0 cùng là ước chung lớn nhất của a1 , a2 , . . . , an thì d0 = ±d. Do đó từ đây về sau, nếu không có nói gì thêm ta sẽ lấy số dương d trong các ước chung lớn nhất của a1 , a2 , . . . , an làm ước chung lớn nhất của a1 , a2 , . . . , an và kí hiệu d = gcd(a1 , a2 , . . . , an ). Như vậy, ta có thể định nghĩa: ước chung lớn nhất của các số nguyên a1 , a2 , . . . , an là các số lớn nhất trong tập hợp các ước chung của chúng. Với khái niệm ước chung lớn nhất, ta có thể định nghĩa các số nguyên tố cùng nhau và nguyên tố cùng nhau từng đôi một như sau. Định nghĩa 1.1.8. (i) Các số nguyên a1 , . . . , an được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. (ii) Các số nguyên a1 , . . . , an được gọi là nguyên tố cùng nhau từng đôi một nếu hai số bất kì trong chúng nguyên tố cùng nhau. Ví dụ 1.1.9. 6, 10, 15 là nguyên tố cùng nhau vì gcd(6, 10, 15) = 1. Các số 6, 7, 13 là nguyên tố cùng nhau từng đôi một vì gcd(6, 7) = gcd(7, 13) = gcd(6, 13) = 1. Định lý sau đây khẳng định ước chung lớn nhất của các số nguyên khác không cho trước luôn tồn tại. Định lý 1.1.10. Tồn tại ước chung lớn nhất của các số nguyên khác không a1 , a2 , . . . , an cho trước. Hệ quả 1.1.11. Các khẳng định sau là đúng. (i) Nếu d = gcd(a1 , a2 , . . . , an ) thì tồn tại các số nguyên u1 , u2 , . . . , un sao cho d = a1 u1 + a2 u2 + . . . + an un . (ii) Điều kiện cần và đủ để a1 , a2 , . . . , an nguyên tố cùng nhau là tồn tại các 5 số nguyên u1 , u2 , . . . , un sao cho 1 = a1 u1 + a2 u2 + . . . + an un . Ta luôn tìm được ước chung lớn nhất của các số khác không cho trước nhờ vào thuật toán Ơclit. Tiếp theo, chúng ta nhắc lại các tính chất của ước chung lớn nhất. Mệnh đề 1.1.12. Các khẳng định sau là đúng. (i) Với k ∈ Z, k > 0 ta có gcd(ka1 , ka2 , . . . , kan ) = k ·gcd(a1 , a2 , . . . , an ). (ii) Với δ ∈ Z, δ > 0, δ | ai (i = 1, 2, . . . , n) ta có a a an  gcd(a1 , a2 , . . . , an ) 2 1 , ,..., = . gcd δ δ δ δ (iii) Một ước chung dương d của các số a1 , a2 , . . . , an là ước chung lớn a1 a2 an nhất của chúng khi và chỉ khi gcd( , , . . . , ) = 1. d d d (iv) Nếu gcd(a, b) = 1 và b | ac thì b | c. (v) Nếu gcd(a, b) = 1 thì gcd(ac, b) = gcd(c, b) với mọi c ∈ Z. (vi) Nếu gcd(a, b) = gcd(a, c) = 1 thì gcd(a, bc) = 1. 1.2 Về các số nguyên tố cùng nhau từng đôi một Mục tiêu của tiết này là nhắc lại khái niệm, tính chất và một số bài toán liên quan đến các số nguyên tố cùng nhau từng đôi một. Định nghĩa 1.2.1. Một tập con A của tập các số tự nhiên được gọi là nguyên tố cùng nhau từng đôi một nếu gcd(a, b) = 1 với mọi a, b ∈ A, a 6= b. Nhận xét 1.2.2. (i) Nếu các số tự nhiên a1 , . . . , at nguyên tố cùng nhau từng đôi một, thì chúng nguyên tố cùng nhau, tức là gcd(a1 , . . . , at ) = 1. Tuy nhiên, điều ngược lại không đúng. Chẳng hạn, các số 3, 5, 6 là nguyên tố cùng nhau, nhưng không nguyên tố cùng nhau từng đôi một. (ii) Tồn tại những tập hợp gồm vô hạn số nguyên tố cùng nhau từng đôi một. Chẳng hạn như tập tất cả các số nguyên tố. Trong Bài tập 1.2.5, chúng ta n thấy rằng tập hợp {62 + 1 | n ∈ N} là tập vô hạn số tự nhiên nguyên tố cùng nhau từng đôi một. 6 Giả thiết nguyên tố cùng nhau từng đôi một đã được sử dụng trong rất nhiều kết quả quan trọng của số học. Một trong những kết quả như thế là Định lí phần dư Trung Hoa. Định lí phần dư Trung Hoa là một kết quả của lí thuyết số, phát biểu rằng nếu chúng ta biết được các phần dư khi chia một số n cho những số m1 , . . . , mt nguyên tố cùng nhau từng đôi một, thì ta xác định được phần dư của phép chia số n cho tích m1 . . . mt . Định lí phần dư Trung Hoa được nhà toán học Trung Quốc Sunzi ghi chép vào thế kỉ thứ 3 sau công nguyên. Người Trung Quốc gọi nó là Bài toán Hàn Tín điểm binh. Tục truyền rằng khi Hàn Tín (229-196 trước công nguyên) điểm quân số, ông cho quân lính xếp hàng 3, hàng 5, hàng 7 rồi báo số dư. Từ đó ông tính chính xác quân số đến từng người. Ngày nay, Định lí phần dư Trung Hoa được sử dụng rộng rãi trong Lí thuyết mật mã, đặc biệt là trong việc tính toán các số nguyên tố lớn. Định lý 1.2.3. Cho m1 , . . . , mt là các số nguyên dương nguyên tố cùng nhau từng đôi một. Khi đó với t số nguyên a1 , . . . , at bất kì cho trước, hệ phương trình đồng dư x ≡ a1 (mod m1 ) x ≡ a2 (mod m2 ) ......... x ≡ at (mod mt ) có duy nhất một nghiệm modulo M , trong đó M = m1 . . . mt . Chứng minh. Trước hết ta chứng minh sự tồn tại nghiệm. Với mỗi i = 1, . . . , t, đặt ni = m1 . . . mi−1 mi+1 . . . mt . Do m1 , . . . , mt là các số nguyên dương nguyên tố cùng nhau từng đôi một nên gcd(ni , mi ) = 1, với mọi i = 1, . . . , t. Suy ra tồn tại các số nguyên ki sao cho ni ki ≡ 1 (mod mi ). Đặt bi = ni ki . Khi đó bi ≡ 1 (mod mi ) và bi ≡ 0 (mod mj ) với mọi j 6= i. Suy ra x = b1 a1 + . . . + bt at là nghiệm của hệ phương trình đồng dư đã cho. 7 Tiếp theo ta chứng minh sự duy nhất. Giả sử x, y cùng là nghiệm của hệ đã cho. Khi đó x ≡ y (mod mi ), với mọi i = 1, . . . , t. Do m1 , . . . , mt là nguyên tố cùng nhau từng đôi một nên x ≡ y (mod m1 . . . mt ). Trong toán phổ thông, có rất nhiều bài toán liên quan đến các số nguyên tố cùng nhau từng đôi một. Dưới đây là một số ví dụ. Bài tập 1.2.4. Tìm 3 số nguyên dương nguyên tố cùng nhau từng đôi một sao cho tổng của hai số tùy ý trong 3 số đó là bội của số còn lại. Lời giải. Không mất tính tổng quát, ta có thể giải thiết x < y < z. Theo giả thiết, z là ước của x + y. Vì x + y < 2z nên z = x + y (vì mọi số tự nhiên lớn hơn z và nhỏ hơn 2z đều không thể là bội của z). Theo giả thiết, x là ước của y + z. Vì z = x + y nên ta suy ra x là ước của x + 2y và vì thế x là ước của 2y. Vì x, y, z nguyên tố cùng nhau từng đôi một, nên gcd(x, y) = 1. Suy ra x là ước của 2. Do đó x = 1 hoặc x = 2. Hoàn toàn tương tự ta có y = 1 hoặc y = 2. Vì x < y nên x = 1 và y = 2. Do đó z là ước của 1 + 2. Vì y < z, nên z = 3. Vậy, 3 số cần tìm là 1, 2, 3. n Bài tập 1.2.5. Dãy số an = 62 + 1 với n = 1, 2, . . . là nguyên tố cùng nhau từng đôi một. Chứng minh. Cho n > m là hai số nguyên dương. Chia an cho am ta được an = am q + r, trong đó 0 ≤ r ≤ am − 1. Suy ra r = an − am q. Giả sử p là một ước chung của am , an . Khi đó p là ước của r. Do đó ta cần tính r. Ta có n m n−m 62 + 1 = (62 )2 n−m + 1 ≡ (−1)2 m + 1 ≡ 2 (mod (62 + 1)). Do đó r = 2. Suy ra p là ước của 2. Do an , am đều là số lẻ, nên p = 1. Vì thế gcd(an , am ) = 1 với mọi n 6= m. 8 Một trong những bài toán được quan tâm là xác định các bộ số Pythagore nguyên tố cùng nhau từng đôi một. Nhắc lại rằng một bộ 3 số tự nhiên x, y, z được gọi là bộ số Pythagore nếu x2 +y 2 = z 2 . Nếu bộ số Pythagore x, y, z thỏa mãn gcd(x, y) = 1, thì ta nói x, y, z là bộ số Pythagore nguyên thủy. Chẳng hạn 6, 8, 10 là bộ số Pythagore, 3, 4, 5 là bộ số Pythagore nguyên thủy. Chú ý rằng nếu x, y, z là bộ số Pythagore nguyên thủy, thì các bộ kx, ky, kz đều là bộ số Pythagore với mọi k ∈ N. Ngược lại, nếu x, y, z là x y z bộ số Pythagore và d = gcd(x, y), thì d là ước của z và , , là bộ số d d d Pythagore nguyên thủy. Như vậy, để xác định các bộ số Pythagore, chúng ta chỉ cần xác định các bộ số Pythagore nguyên thủy. Bài tập 1.2.6. Chứng minh rằng bộ 3 số nguyên dương x, y, z là bộ số Pythagore nguyên tố cùng nhau từng đôi một nếu và chỉ nếu tồn tại hai số tự nhiên u > v nguyên tố cùng nhau và không đồng thời là số lẻ sao cho sau một hoán vị của x và y ta có x = u2 − v 2 , y = 2uv. Chứng minh. Giả sử x, y, z là bộ số Pythagore nguyên thủy. Khi đó ta có gcd(x, y) = 1 và z 2 = x2 + y 2 . Suy ra gcd(x2 , y 2 ) = 1. Vì thế, gcd(x2 , z 2 ) = gcd(x2 , x2 + y 2 ) = gcd(x2 , y 2 ) = 1. Suy ra gcd(x, z) = 1. Tương tự ta có gcd(y, z) = 1. Vì vậy, mỗi bộ số Pythagore nguyên thủy đều nguyên tố cùng nhau từng đôi một. Ngược lại, nếu x, y, z là bộ số Pythagore nguyên tố cùng nhau từng đôi một, thì nó phải là bộ số Pythagore nguyên thủy. Do đó, bài toán được suy ra từ kết quả quen biết về bộ số Pythagore nguyên thủy. 1.3 Giả thuyết Erdös về k số nguyên tố cùng nhau từng đôi một Mục tiêu của tiết này là giới thiệu một giả thuyết của Erdös về k số nguyên tố cùng nhau từng đôi một, đồng thời đưa ra câu trả lời khẳng định cho giả thuyết khi k = 1 và k = 2. 9 Trong suốt tiết này chúng tôi sử dụng các kí hiệu Ak (n) và Bk (n) định nghĩa trong tài liệu [4] như sau. Ký hiệu 1.3.1. Cho n ≥ 1 và k ≥ 1 là hai số tự nhiên. Kí hiệu Ak (n) là số các số nguyên dương không vượt quá n và chia hết cho ít nhất một trong k số nguyên tố đầu tiên. Kí hiệu Bk (n) là số t lớn nhất sao cho tồn tại một tập gồm t số nguyên dương không vượt quá n mà trong tập đó không thể trích ra k + 1 số nguyên dương nguyên tố cùng nhau từng đôi một. Kết quả sau đây cho ta mối quan hệ giữa Ak (n) và Bk (n). Mệnh đề 1.3.2. Ta luôn có Bk (n) ≥ Ak (n). Chứng minh. Gọi k số nguyên tố đầu tiên là p1 , p2 , . . . , pk , nghĩa là p1 = 2, p2 = 3, p3 = 5, . . . Gọi X là tập gồm các số nguyên dương a sao cho a ≤ n và a chia hết cho một số nguyên tố pi với i ≤ k nào đó. Giả sử tập X có r phần tử. Khi đó, theo Kí hiệu 1.3.1, ta có Ak (n) = r. Ta khẳng định rằng không tồn tại một bộ k + 1 số trong tập X nguyên tố cùng nhau từng đôi một. Thật vậy, lấy k + 1 số tùy ý a1 , . . . , ak+1 ∈ X. Theo Nguyên lí Dirichlet (Dirichlet’s Principle), trong k + 1 số a1 , . . . , ak+1 , mỗi số đều chia hết cho một trong k số nguyên tố p1 , . . . , pk , ắt phải tồn tại hai số ai , aj với i 6= j sao cho ai và aj chia hết cho cùng một số nguyên tố pt nào đó với t ≤ k. Suy ra gcd(ai , aj ) > 1. Do đó a1 , . . . , ak+1 không thể nguyên tố cùng nhau từng đôi một. Suy ra Bk (n) ≥ r = Ak (n). Năm 1965, P. Erdös [7] đã chỉ ra rằng nếu k = 1 hoặc k = 2, thì ta có đẳng thức Bk (n) = Ak (n). Vì thế ông đã đặt ra giả thuyết sau. Giả thuyết 1.3.3. (Erdös, 1965) Với hai số nguyên dương k ≤ n ta có Bk (n) = Ak (n). 10 Trước hết, chúng ta xét giả thuyết của Erdös cho trường hợp k = 1. Theo Kí hiệu 1.3.1 thì A1 (n) là số các số nguyên dương không vượt quá n và chia hết cho 2; còn B1 (n) là số tự nhiên t lớn nhất sao cho tồn tại một tập gồm t số nguyên dương không vượt quá n mà trong tập đó không có 2 số nguyên tố cùng nhau. Ta xét hai trường hợp. n • Cho n chẵn. Khi đó A1 (n) = . Chọn X = {2, 4, . . . , n} là tập hợp 2 n gồm số chẵn không vượt quá n. Rõ ràng từ tập X ta không thể trích ra 2 2 số nguyên tố cùng nhau. Vì thế n = A1 (n). 2 n−1 • Cho n là số lẻ. Khi đó A1 (n) = . Chọn X = {2, 4, . . . , n − 1} là 2 n−1 số chẵn không vượt quá n, từ tập X ta không thể trích tập hợp gồm 2 ra được hai số nguyên tố cùng nhau. Vì thế B1 (n) ≥ B1 (n) ≥ n−1 = A1 (n). 2 Dưới đây ta sẽ chứng minh rằng B1 (n) = A1 (n). Trước hết, ta cần bổ đề sau. Bổ đề 1.3.4. Cho n = 2t + r với r ∈ {0, 1}. Khi đó trong t + 1 số nguyên dương bất kì không vượt quá n, luôn chọn được 2 số nguyên tố cùng nhau. Chứng minh. Cho 1 ≤ a1 < a2 < . . . < at+1 ≤ n là dãy gồm t + 1 số nguyên dương không vượt quá n. Nếu a1 = 1, thì a1 , a2 là hai số trong dãy nguyên tố cùng nhau. Do đó ta có thể giả thiết a1 ≥ 2. Đặt m = min{ai+1 − ai | i = 1, . . . , t}. Hiển nhiên m ≥ 1. Ta chứng minh m = 1. Thật vậy, giả sử ngược lại. Khi đó m ≥ 2 và ta có at+1 ≥ a1 + 2t ≥ 2 + 2t > n. Điều này là vô lí. Suy ra m = 1. Vì thế tồn tại một chỉ số i ≤ t sao cho ai+1 = ai + 1. Rõ ràng, nếu d là ước chung của ai và ai+1 , thì d là ước của 1, vì thế ai , ai+1 là nguyên tố cùng nhau. 11 Kết quả sau đây, được suy ra ngay từ các Bổ đề 1.3.2, 1.3.4, chỉ ra công thức tính số t lớn nhất sao cho có một tập X gồm t số nguyên dương không vượt quá n mà từ tập X không thể trích ra 2 số nguyên tố cùng nhau. Từ nay đến hết luận văn, chúng ta sử dụng kí hiệu phần nguyên như sau: Với mối số hữu tỷ a > 0, kí hiệu bac là số nguyên lớn nhất không vượt quá a.   n . Định lý 1.3.5. B1 (n) = A1 (n) = 2 Tiếp theo, chúng ta xét giả thuyết của Erdös cho trường hợp k = 2. Theo Kí hiệu 1.3.1 thì B2 (n) là số tự nhiên t lớn nhất sao cho tồn tại một tập gồm t số nguyên dương không vượt quá n mà trong tập đó không có 3 số nguyên tố cùng nhau từng đôi một. Còn A2 (n) là số các số nguyên dương không vượt quá n hoặc chia hết cho 2 hoặc chia hết cho 3. Gọi A là tập các số chẵn không vượt quá n và B là tập các số lẻ không vượt quá n và chia hết cho 3. Khi đó A2 (n) = |A| + |B|. Ta xét 4 trường hợp. • Nếu n = 6t hoặc n = 6t + 1, thì A2 (n) = 4t. • Nếu n = 6t + 2, thì A2 (n) = 4t + 1. • Nếu n = 6t + 3, thì A2 (n) = 4t + 2. • Nếu n = 6t + 4 hoặc n = 6t + 5, thì A2 (n) = 4t + 3. Trong tài liệu [7], P. Erdös đã chú thích rằng B2 (n) = A2 (n). Chúng ta thảo luận điều này trong phần dưới đây. Bổ đề 1.3.6. Cho n = 6t hoặc n = 6t + 1. Khi đó trong 4t + 1 số nguyên dương bất kì không vượt quá n, luôn chọn được 3 số nguyên tố cùng nhau từng đôi một. Chứng minh. Cho 1 ≤ a1 < a2 < . . . < a4t+1 ≤ n là dãy gồm 4t + 1 số nguyên dương không vượt quá n. Giả sử a1 = 1. Xét dãy 2 ≤ a2 < a3 < . . . < a4t+1 ≤ n gồm 4t số nguyên dương nhỏ hơn n. Chú ý rằng 4t ≥ 3t + 1. Do đó theo chứng minh Bổ đề 1.3.4, tồn tại số i với 2 ≤ i ≤ 4t sao cho ai+1 = ai + 1. Suy 12 ra a1 , ai , ai+1 là ba số nguyên trong dãy nguyên tố cùng nhau từng đôi một. Do đó ta có thể giả thiết a1 ≥ 2. Đặt mi = ai+1 − ai với i = 1, . . . , 4t. Hiển nhiên mi ≥ 1 với mọi i. Gọi r là số vị trí i của dãy sao cho mi = 1. Khi đó có 4t − r vị trí i thỏa mãn mi ≥ 2. Ta có n ≥ a4t+1 ≥ a1 + r + 2(4t − r) ≥ 2 + 8t − r ≥ n + (1 + 2t) − r. Suy ra r ≥ 2t + 1, nghĩa là có ít nhất 2t + 1 vị trí i sao cho mi = 1. Nếu trong dãy không có 3 số tự nhiên liên tiếp, thì ứng với 2t + 1 vị trí mà mi = 1, sẽ có ít nhất 2t + 1 số lẻ và 2t + 1 số chẵn, tức là trong dãy có ít nhất 4t + 2 số, điều này không thể xảy ra. Vì thế tồn tại một chỉ số i ≤ 4t sao cho ai+1 = ai + 1 và ai+2 = ai + 2. Rõ ràng ai , ai+1 nguyên tố cùng nhau, và ai+1 , ai+2 nguyên tố cùng nhau. Giả sử ai lẻ. Nếu d là ước chung của ai và ai+2 , thì d là số lẻ và d ước của 2, vì thế ai , ai+2 là nguyên tố cùng nhau. Suy ra ai , ai+1 , ai+2 là nguyên tố cùng nhau từng đôi một. Trường hợp ai chẵn, chúng ta lại tiếp tục khảo sát thêm các chỉ số i mà mi ≥ 2, ta sẽ suy ra rằng trong dãy trên có ít nhất ba số nguyên tố cùng nhau từng đôi một. Chứng minh bổ đề sau đây rất sơ cấp, nhưng cần đến nhiều tính toán chi tiết và phân thành nhiều trường hợp nhỏ, vì thế tác giả luận văn không trình bày nó ở đây. Bổ đề 1.3.7. Các phát biểu sau là đúng (i) Nếu n = 6t + 2, thì mỗi dãy gồm 4t + 2 số nguyên dương bất kì không vượt quá n, luôn chọn được 3 số nguyên tố cùng nhau từng đôi một. (ii) Nếu n = 6t + 3, thì mỗi dãy gồm 4t + 3 số nguyên dương bất kì không vượt quá n, luôn chọn được 3 số nguyên tố cùng nhau từng đôi một. (iii) Nếu n = 6t + 4 hoặc n = 6t + 5, thì mỗi dãy gồm 4t + 4 số nguyên dương bất kì không vượt quá n, luôn chọn được 3 số nguyên tố cùng nhau từng đôi một. 13 Kết quả sau cho ta công thức tính số t lớn nhất sao cho có một tập X gồm t số nguyên dương không vượt quá n mà từ tập X không thể trích ra 3 số nguyên tố cùng nhau từng đôi một. Chứng minh kết quả này được suy ra ngay từ các Bổ đề 1.3.2, 1.3.6, 1.3.7. Định lý 1.3.8. Với mọi n ≥ 3 ta có       n n n B2 (n) = A2 (n) = + − . 2 3 6 1.4 Giả thuyết Erdös với k = 3 Tiết này dành để trình bày chi tiết các kết quả về các dãy chứa nhiều nhất 3 số tự nhiên nguyên tố cùng nhau từng đôi một. Nội dung của tiết này dựa theo hai bài báo [4] của S. G. Choi đăng trên Trans. AMS và bài báo [3] của Y-G. Chen và X-F. Zhou đăng trên Discrete Mathematics. Mục tiêu chính của tiết này là chứng minh giả thuyết của P. Erdös khi k = 3, đồng thời đưa ra câu trả lời bộ phận khi k = 4. Định lí sau đây đưa ra câu trả lời khẳng định cho giả thuyết của P. Erdös với k = 3. Ta luôn kí hiệu k số nguyên tố đầu tiên là p1 = 2, p2 = 3, p3 = 5, . . . , pk . Định lý 1.4.1. Cho n ≥ 5 là số nguyên dương. Khi đó B3 (n) = A3 (n). Để chứng minh Định lí 1.4.1, chúng ta cần các bổ đề sau. Trước hết, để thuận tiện, ta sẽ sử dụng khái niệm và kí hiệu dưới đây. Định nghĩa 1.4.2. Một tập các số nguyên dương là tốt nếu nó chứa 4 số nguyên tố cùng nhau từng đôi một, nếu X không tốt thì ta nói X là xấu. Rõ ràng, nếu có một tập con nào đó của X là tốt thì X cũng là tốt. Ký hiệu 1.4.3. Cho n1 , n2 là các số nguyên dương. Ta ký hiệu A(n1 , n2 ) là số các số nguyên trong [n1 , n2 ] là bội của ít nhất một trong ba số 2, 3, 5. Với kí hiệu này ta có A3 (n) = A(1, n). 14 Bổ đề 1.4.4. Cho X là tập gồm A3 (30) số nguyên dương không vượt quá 30. Khi đó X là xấu nếu và chỉ nếu X trùng với tập các số nguyên dương không vượt quá 30 và là bội của một trong ba số 2, 3, 5. Chứng minh. Các số nguyên dương không vượt quá 30 và không chia hết cho số nào trong các số 2, 3, 5 là 1, 7, 11, 13, 17, 19, 23, 29. Do đó ta tính được |X| = A3 (30) = 22. Suy ra X phải chứa ít nhất 8 trong các số sau: 2, 4, 8, 3, 9, 27, 5, 25, 1, 7, 11, 13, 17, 19, 23, 29. Dễ dàng kiểm tra được X là tốt trừ khi X không chứa số nào trong các số 1, 7, 11, 13, 17, 19, 23, 29. Vì thế X là xấu nếu và chỉ nếu X trùng với tập các số nguyên dương không vượt quá 30 và là bội của một trong ba số 2, 3, 5. Bổ đề 1.4.5. Cho 5 ≤ j ≤ 15 và X là tập gồm A3 (j) + 1 số nguyên dương trong đoạn [30k + 1, 30k + j]. Khi đó X là tốt. Chứng minh. Đặt M = 30k. Vì M chia hết cho cả 2, 3 và 5 và 5 ≤ j ≤ 15 nên M + 1, M + 7, M + 11, M + 13 là tất cả các số nguyên trong đoạn [M + 1, M + 15] mà không chia hết cho số nào trong các số 2, 3, 5. Dễ dàng kiểm tra được M + 1, M + 2, M + 3, M + 5, M + 7, M + 11 là các số nguyên tố cùng nhau từng đôi một. Vì thế ta chỉ cần chứng minh Bổ đề đúng với j = 5, 6, 7, 11 và 13. • Nếu j = 5 hoặc 6 thì A3 (j) + 1 lần lượt là 5 và 6. Vì thế X chứa tất cả các số nguyên trong đoạn [M + 1, M + j] và do đó X chứa các số M + 1, M + 2, M + 3, M + 5 nguyên tố cùng nhau từng đôi một. • Nếu j = 7 thì A3 (7) + 1 = 6, do đó X chứa 6 trong 7 số của đoạn [30k + 1, 30k + 7]. Vì thế X chứa ít nhất 4 số trong các số nguyên tố cùng nhau từng đôi một M + 1, M + 2, M + 3, M + 5, M + 7. • Nếu j = 11 thì A3 (11) + 1 = 9, do đó X chứa 9 trong 11 số của đoạn [30k + 1, 30k + 11]. Vì thế X chứa ít nhất 4 số trong các số nguyên tố cùng nhau từng đôi một M + 1, M + 2, M + 3, M + 5, M + 7, M + 11. • Nếu j = 13 thì A3 (13) + 1 = 10, do đó X chứa 10 trong 13 số của đoạn [30k + 1, 30k + 13]. Dễ thấy M + 4 và M + 8 không thể cùng chia hết cho 7. Vì thế có ít nhất một trong hai số M + 4, M + 8 không chia hết cho 15 7. Đặt x là số đó. Suy ra X chứa ít nhất 4 số trong các số nguyên tố cùng nhau từng đôi một x, M + 1, M + 3, M + 5, M + 7, M + 11, M + 13. Như vậy, X là tốt. Bổ đề 1.4.6. Giả sử X chứa A(16, 30) + 1 số nguyên dương trong đoạn [30k + 16, 30k + 30]. Khi đó X là tốt. Chứng minh. Đặt M = 30k. Ta có A(16, 30) + 1 = 12. Giả sử x là một trong hai số M + 22, M + 26 mà không chia hết cho 7. Khi đó X chứa ít nhất 4 trong 7 số nguyên tố cùng nhau từng đôi một x, M + 25, M + 27, M + 17, M + 19, M + 23, M + 29. Vì thế X là tốt. Bổ đề 1.4.7. Giả sử X là tập gồm A(1, 30) + 1 số nguyên dương trong đoạn [30k + 1, 30k + 30]. Khi đó X là tốt. Chứng minh. Vì A(1, 30) + 1 = A(1, 15) + A(16, 30) + 1 nên X chứa ít nhất A(1, 15) + 1 số nguyên trong đoạn [30k + 1, 30k + 15] hoặc chứa ít nhất A(16, 30) + 1 số nguyên trong đoạn [30k + 16, 30k + 30]. Do đó từ Bổ đề 1.4.5 và Bổ đề 1.4.6 ta có ngay điều phải chứng minh. Bổ đề 1.4.8. Giả sử j ≥ 1 và X là tập gồm A(1, 30j) số nguyên trong đoạn [1, 30j]. Khi đó X là xấu khi và chỉ khi nó trùng với tập các số nguyên dương trong [1, 30j] và là bội của một trong các số 2, 3 và 5. Chứng minh. Giả sử X là xấu. Theo Bổ đề 1.4.7 tập X chứa đúng A(1, 30) số nguyên dương trong mỗi đoạn [30k + 1, 30k + 30] với k = 0, 1, . . . , j − 1. Vì thế theo Bổ đề 1.4.4, X trùng với tập các số nguyên dương trong [1, 30j] và là bội của một trong các số 2, 3 và 5. Bổ đề 1.4.9. Giả sử 1 ≤ j ≤ 30 và X là tập gồm A(1, j) + 2 số nguyên trong đoạn [30k + 1, 30k + j]. Khi đó X là tốt. Chứng minh. Với mỗi 1 ≤ j ≤ 6, ta có A(1, j) = j − 1 nên A(1, j) + 2 = j + 1. Vì thế giả thiết của định lý chỉ thỏa mãn khi j ≥ 7. Nếu 7 ≤ j ≤ 15, thì mỗi tập con của X chứa A(1, j) + 1 số nguyên trong [30k + 1, 30k + j] đều tốt theo Bổ đề 1.4.5. Suy ra X tốt và ta có thể giả sử j > 15. Nếu X chứa nhiều hơn hoặc ít hơn A(1, 15) số nguyên trong đoạn [30k + 1, 30k + 15] 16 thì theo Bổ đề 1.4.5 và Bổ đề 1.4.6, X là tốt. Suy ra ta giả sử X chứa đúng A(1, 15) số nguyên trong đoạn [30k + 1, 30k + 15] và A(16, j) + 2 số nguyên trong đoạn [30k + 16, 30k + j]. Khi đó nếu j < 19 thì A(16, j) + 2 lớn hơn số phần tử của [30k + 16, 30k + j.] Suy ra j ≥ 19. Đặt M = 30k. Khi đó M + 17, M + 19, M + 23, M + 29 là tất cả các số nguyên trong đoạn [30k + 16, 30k + 30] không chia hết cho 2, 3 hoặc 5. Vì thế ta chỉ cần chứng minh bổ để trong trường hợp j = 19, 23 và 29. • Nếu j = 19 thì X chứa M + 16, M + 17, M + 18, M + 19 và 11 số nguyên trong [30k + 1, 30k + 15]. Vì M + 16, M + 17, M + 19 và M + l nguyên tố cùng nhau từng đôi một với l = 1, 7, 11 và 13 nên ta có thể giả sử X chứa tất cả các số nguyên còn lại trong đoạn [30k + 1, 30k + 15]. Khi đó ta chọn được M + 9, M + 14, M + 17, M + 19 là các số nguyên tố cùng nhau từng đôi một. • Nếu j = 23 thì X chứa 18 số trong đó có 11 số trong [30k +1, 30k +15]. Vì thế X chứa 7 số trong đoạn [30k + 16, 30k + 23]. Do đó X luôn chứa ít nhất 4 số trong các số M + 22, M + 21, M + 17, M + 19, M + 23 nguyên tố cùng nhau từng đôi một. • Nếu j = 29 thì A(16, 29) = 10. Suy ra X chứa 12 số trong đoạn [30k + 16, 30k + 29]. Đoạn này gồm 14 số. Vì thế X chứa ít nhất 4 số trong các số nguyên tố cùng nhau từng đôi một M + 27, M + 25, M + 17, M + 19, M + 23, M + 29. Vậy X là tốt. Chứng minh Định lý 1.4.1 Chứng minh. Cho X là tập gồm A3 (n) + 1 số nguyên trong đoạn [1, n] với n ≥ 5. Ta sẽ chứng minh rằng X là tốt. Theo Bổ đề 1.4.8 ta có thể giả sử n không chia hết cho 30. Dễ thấy rằng mọi tập gồm A3 (n) + 1 số nguyên trong đoạn [1, n] là tốt nếu 30 ≥ n ≥ 5. Vì thế ta có thể giả sử n > 30 nghĩa là n = 30k + l với 1 ≤ l < 30. Ký hiệu X ∗ là tập con của X trong đoạn [30k + 1, 30k + l]. Vì kết quả của Định lý có thể suy ra từ Bổ đề 1.4.9 khi |X ∗ | ≥ A3 (l) + 2 nên ta có thể giả sử |X ∗ | ≤ A3 (l) + 1. Theo Bổ đề 1.4.7 suy 17