ĐẠ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 NGUN 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 Mc lc Li núi u 1 Gi thuyt Erdă os k số nguyên tố đôi 1.1 Chuẩn bị 1.2 Về số nguyên tố đôi 1.3 Giả thuyt Erdăos v k s nguyờn t cựng tng ụi mt 1.4 Gi thuyt Erdăos vi k = 14 Bộ số nguyên tố đôi 19 2.1 Bộ ba số không nguyên tố đôi 19 2.2 Bộ số nguyên tố đôi 26 Kết luận 44 Tài liệu tham khảo 45 Mở đầu Cho A tập tập tích Đề Các {1, , k}2 Bộ (a1 , , ak ) ∈ Zk gọi nguyên tố đôi A gcd(ai , aj ) = với (i, j) ∈ A Trong trường hợp gcd(ai , aj ) = với ≤ i < j ≤ k, (a1 , , ak ) ∈ Zk gọi nguyên tố đôi Nếu gcd(ai , aj ) = với ≤ i < j ≤ k ta nói (a1 , , ak ) không nguyên tố đơi Tính chất ngun tố đơi có vai trò quan trọng lý thuyết số Nó giả thiết khơng thể thiếu Định lý phần dư Trung Hoa tiếng chứng minh cách 750 năm (xem [11]) Cho đến nay, Định lý áp dụng nhiều lĩnh vực khác toán học đại nhân đồng dư; tính tốn bắc cầu; lý thuyết mã hóa mật mã (xem [6]) Ngày nay, việc tính tốn ngun tố đơi cần thiết để xác định số không nguyên tố đôi (xem [8], [14]) Chính lý này, tơi chọn đề tài "Về tính chất đơi ngun tố nhau" Mục đích thứ luận văn trình bày lại số kết giả thuyt ca Erdăos cho trng hp k = 1, 2, 3, 4, dựa theo báo [3] [4] Giả thuyết phát biểu rằng, số lớn số nguyên dương không vượt số nguyên dương n, cho từ số khơng thể trích k + số nguyên nguyên tố đôi số số nguyên dương không vượt n bội k số nguyên tố Mục đích thứ hai luận văn trình bày lại kết Randell Heyman báo [9] xây dựng cơng thức gần với sai số thích hợp để tính số gồm ba số nguyên dương nhỏ số H cho trước, không nguyên tố đôi số gồm v số nguyên dương nhỏ số H cho trước, nguyên tố đôi tập A xác định Ngoài phần mở đầu kết luận, luận văn gồm chương Chương trình bày số tốn liên quan đến số nguyên tố đôi chứng minh khẳng định cho giả thuyết ca Erdăos cỏc trng hp k Chng trình bày kết chứng minh chi tiết cơng thức tính gần số ngun dương nhỏ số H không nguyên tố đôi nguyên tố đôi tập A dựa lý thuyết đồ thị số cơng cụ giải tích Luận văn hoàn thành trường Đại học Khoa học, Đại học Thái Nguyên, hướng dẫn tận tình cô giáo TS Trần Đỗ Minh Châu Cô dành nhiều thời gian hướng dẫn giải đáp thắc mắc tơi suốt q 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 Tơi xin chân thành cảm ơn tồn thể thầy, giáo Khoa Tố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 suốt thời gian theo học, thực hoàn thành luận văn Tôi xin cảm ơn bạn bè, người thân đồng nghiệp giúp đỡ, động viên để tơi hồn thành luận văn Thái Ngun, tháng năm 2018 Người viết luận văn Nguyễn Thị Hằng Chng Gi thuyt Erdă os v k s nguyên tố đôi Mục tiêu chương trình bày câu trả lời khẳng định cho gi thuyt ca P Erdăos v k s nguyờn tố đôi k ≤ Hai tiết đầu dành để nhắc lại khái niệm số tính chất ước, bội, ước chung lớn nhất, bội chung nhỏ số toán số nguyên tố đơi Trong hai tiết tiếp theo, chúng tơi trình by chi tit chng minh cho gi thuyt ca Erdăos k = 1, 2, 1.1 Chuẩn bị Trong tiết này, nhắc lại số khái niệm tính chất ước, bội, ước chung lớn nhất, bội chung nhỏ số nguyên, khái niệm số nguyên tố đôi để tiện cho việc theo dõi nội dung phía sau Định nghĩa 1.1.1 Giả sử a b hai số nguyên, b = Ta nói b chia hết a hay a chia hết cho b tồn số nguyên q cho a = bq Khi ta nói b ước a hay a bội b 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, hai ước số nguyên a bội số nguyên b = Trong trường hợp không xảy quan hệ chia hết, ta có định lý phép chia có dư phát biểu sau Định lý 1.1.3 Với cặp số nguyên a, b, b = tồn cặp số nguyên q, r thỏa mãn hệ thức a = bq + r, ≤ r < |b| Hệ Định lý 1.1.3 vành số ngun Z vành Vì vành Z có khái niệm ước chung lớn nhất, bội chung nhỏ Chúng ta nhắc lại kết khái niệm Z, bỏ qua chứng minh Định nghĩa 1.1.4 (i) Một số nguyên d gọi ước chung số nguyên a1 , a2 , , an d ước đồng thời số nguyên (ii) Với số nguyên (i = 1, 2, , n) ta kí hiệu U(ai ) tập hợp ước Hiển nhiên U(ai ) = ∅ có hữu hạn phần tử Rõ ràng n i=1 U(ai ) = ∅ bị chặn số lớn số |a1 |, |a2 |, , |an | , có số lớn d Hiển nhiên d chung a1 , a2 , , an thấy ước chung a1 , a2 , , an ước d Định nghĩa 1.1.5 Một ước chung d số nguyên a1 , a2 , , an cho ước chung a1 , a2 , , an ước d, gọi ước chung lớn số Ví dụ 1.1.6 Các số 1, −1, 2, −2 ước chung −6 Các ước chung lớn −6 −2 Nhận xét 1.1.7 (i) Tập hợp ước chung nhiều số cho trước trùng với tập hợp ước ước chung lớn số (ii) Nếu tất số a1 , a2 , , an tập hợp ước chung chúng Z \ {0} Khi khái niệm ước chung lớn khơng có nghĩa Do giả thiết số a1 , a2 , , an xét tất Hơn tập hợp ước chung số xét không thay đổi ta thêm hay bớt số Vì ta giả thiết thêm = với i = 1, 2, , n (iii) Nếu d ước chung lớn (a1 , a2 , , an ) −d ước chung lớn (a1 , a2 , , an ) Hơn d d ước chung lớn a1 , a2 , , an d = ±d Do từ sau, khơng có nói thêm ta lấy số dương d ước chung lớn a1 , a2 , , an làm ước chung lớn a1 , a2 , , an kí hiệu d = gcd(a1 , a2 , , an ) Như vậy, ta định nghĩa: ước chung lớn số nguyên a1 , a2 , , an số lớn tập hợp ước chung chúng Với khái niệm ước chung lớn nhất, ta định nghĩa số nguyên tố nguyên tố đôi sau Định nghĩa 1.1.8 (i) Các số nguyên a1 , , an gọi nguyên tố ước chung lớn chúng (ii) Các số nguyên a1 , , an gọi nguyên tố đôi hai số chúng ngun tố Ví dụ 1.1.9 6, 10, 15 nguyên tố gcd(6, 10, 15) = Các số 6, 7, 13 ngun tố đơi gcd(6, 7) = gcd(7, 13) = gcd(6, 13) = Định lý sau khẳng định ước chung lớn số nguyên khác không cho trước tồn Định lý 1.1.10 Tồn ước chung lớn số nguyên khác không a1 , a2 , , an cho trước Hệ 1.1.11 Các khẳng định sau (i) Nếu d = gcd(a1 , a2 , , an ) tồn số nguyên u1 , u2 , , un cho d = a1 u1 + a2 u2 + + an un (ii) Điều kiện cần đủ để a1 , a2 , , an nguyên tố tồn số nguyên u1 , u2 , , un cho = a1 u1 + a2 u2 + + an un Ta ln tìm ước chung lớn số khác không cho trước nhờ vào thuật toán Ơclit Tiếp theo, nhắc lại tính chất ước chung lớn Mệnh đề 1.1.12 Các khẳng định sau (i) Với k ∈ Z, k > ta có gcd(ka1 , ka2 , , kan ) = k ·gcd(a1 , a2 , , an ) (ii) Với δ ∈ Z, δ > 0, δ | (i = 1, 2, , n) ta có gcd an a1 a2 , , , δ δ δ = gcd(a1 , a2 , , an ) δ (iii) Một ước chung dương d số a1 , a2 , , an ước chung lớn a1 a2 an chúng gcd( , , , ) = d d d (iv) Nếu gcd(a, b) = b | ac b | c (v) Nếu gcd(a, b) = gcd(ac, b) = gcd(c, b) với c ∈ Z (vi) Nếu gcd(a, b) = gcd(a, c) = gcd(a, bc) = 1.2 Về số nguyên tố đôi Mục tiêu tiết nhắc lại khái niệm, tính chất số toán liên quan đến số nguyên tố đôi Định nghĩa 1.2.1 Một tập A tập số tự nhiên gọi nguyên tố đôi gcd(a, b) = với a, b ∈ A, a = b Nhận xét 1.2.2 (i) Nếu số tự nhiên a1 , , at nguyên tố đơi một, chúng ngun tố nhau, tức gcd(a1 , , at ) = Tuy nhiên, điều ngược lại không Chẳng hạn, số 3, 5, nguyên tố nhau, không nguyên tố đôi (ii) Tồn tập hợp gồm vô hạn số nguyên tố đôi Chẳng hạn tập tất số nguyên tố Trong Bài tập 1.2.5, n thấy tập hợp {62 + | n ∈ N} tập vô hạn số tự nhiên nguyên tố đôi Giả thiết nguyên tố đôi sử dụng nhiều kết quan trọng số học Một kết Định lí phần dư Trung Hoa Định lí phần dư Trung Hoa kết lí thuyết số, phát biểu biết phần dư chia số n cho số m1 , , mt nguyên tố đơi một, ta xác định phần dư phép chia số n cho tích m1 mt Định lí phần dư Trung Hoa nhà toán học Trung Quốc Sunzi ghi chép vào kỉ thứ sau công nguyên Người Trung Quốc gọi Bài tốn Hàn Tín điểm binh Tục truyền Hàn Tín (229-196 trước cơng ngun) điểm qn số, ơng cho qn lính xếp hàng 3, hàng 5, hàng báo số dư Từ ơng tính xác quân số đến người Ngày nay, Định lí phần dư Trung Hoa sử dụng rộng rãi Lí thuyết mật mã, đặc biệt việc tính tốn số ngun tố lớn Định lý 1.2.3 Cho m1 , , mt số nguyên dương nguyên tố đôi Khi với t số nguyên a1 , , at cho trước, hệ phương trình đồng dư x ≡ a1 (mod m1 ) x ≡ a2 (mod m2 ) x ≡ at (mod mt ) có nghiệm modulo M , M = m1 mt Chứng minh Trước hết ta chứng minh tồn nghiệm Với i = 1, , t, đặt ni = m1 mi−1 mi+1 mt Do m1 , , mt số nguyên dương nguyên tố đôi nên gcd(ni , mi ) = 1, với i = 1, , t Suy tồn số nguyên ki cho ni ki ≡ (mod mi ) Đặt bi = ni ki Khi bi ≡ (mod mi ) bi ≡ (mod mj ) với j = i Suy x = b1 a1 + + bt at nghiệm hệ phương trình đồng dư cho ρG = p QG p nguyên tố Chứng minh Ta chứng minh định lí theo ba bước sau • Bước 1: Chứng minh v g(H) = µ(n1 ) µ(ne ) n1 , ,ne r=1 H Nr • Bước 2: Chứng minh ∞ ∞ g(H) = H v v µ(n1 ) µ(ne ) ne =1 n1 =1 + R + O(H v−1 logd H), N r=1 r e |R| ≤ H ∞ ∞ ∞ v−1 ∞ j=1 n1 =1 nj−1=1 nj >H nj+1=1 v µ(n1 ) µ(ne ) ne =1 N r r=1 • Bước 3: Chứng minh |R| = O(H v−1 logd H) Sau ta bắt đầu chứng minh bước Trước hết ta cần Bổ đề sau lực lượng tập hợp, mở rộng thuật toán sàng Eratosthenes Bổ đề 2.2.10 Cho X tập hữu hạn, A1 , A2 , , Ak ⊆ X Khi k |X\ (−1)|J| |BJ | , Aj | = j=1 J⊆{1,2, ,k} B∅ = X, với ∅ = J ⊆ {1, 2, , k} BJ = Aj j∈J Ta kí hiệu X tập hợp xác định X = (a1 , , av ) ∈ Nv : ar ≤ H, ≤ r ≤ v Khi tập G(H) liên kết với đồ thị G tập tập X Với số nguyên tố p ≤ H cạnh a = {r, s} ∈ G xác định tập sau X Ap,a = (a1 , , av ) ∈ X : p | ar , p | as 32 Rõ ràng Ap,a không thuộc G(H) Hơn nữa, G(H) = X\ Ap,a , a∈E p≤H E tập tất cạnh đồ thị G Chú ý rằng, với số nguyên tố p nhỏ H cạnh a ∈ E, tập Ap,a xác định Kí hiệu PH tập tất số nguyên tố nhỏ H Ta viết Ap,a dạng Aj j ∈ PH × E Áp dụng Bổ đề 2.2.10 ta (−1)|J| |BJ | g(H) = (2.23) J⊆PH ×E Tiếp theo ta tính BJ |J| Với J ⊆ PH × E, giả sử J có dạng J = (p1 , e1 ), , (pm , em ) Khi m BJ = Apj ,ej j=1 Vì (a1 , , av ) ∈ BJ pj | arj , pj | asj với ≤ j ≤ m, ej = rj , sj Chú ý rằng, pi1 , , pi số nguyên tố J liên kết với cạnh cho trước a = {r, s}, tích pi1 pi phải chia hết giá trị ar as liên kết với đỉnh a Cho tập Ta ⊆ PH gồm số nguyên tố p cho (p, a) ∈ J Ta đặt na = p, p∈Ta suy Ta = ∅ ta có na = Vì (a1 , , av ) ∈ BJ với cạnh a = {r, s} xuất J ta có na | ar na | as Theo cách này, xác định J cách đưa số na ứng với cạnh a Chú ý na không số phương tất ước nguyên tố nhỏ H Hơn nữa, (a1 , , av ) ∈ BJ na | ar với cạnh a nối đỉnh r với đỉnh khác Với đỉnh r, xét tất cạnh a nối đỉnh r với đỉnh khác, kí hiệu bội chung nhỏ na tương ứng Nr Khi (a1 , , av ) ∈ BJ 33 với Nr | ar Vì số bội Nr mà khơng vượt q H H nên ta biểu diễn số phần tử BJ sau Nr v |BJ | = r=1 H Nr (2.24) Tiếp theo tính |J| Vì |J| thực chất tổng số thừa số nguyên tố chạy qua tất nj nj khơng số phương, nên (−1)|J| = (−1) e j=1 ω(nj ) = µ(n1 ) µ(ne ), (2.25) tổng lấy tất nj khơng phương có ước ngun tố lớn P + (nj ) ≤ H Thay (2.24) (2.25) vào (2.23) ta ∞ ∞ g(H) = n1 =1 v H Nr µ(n1 ) µ(ne ) ne =1 r=1 Tổng đẳng thức chạy qua tất (n1 , , ne ) cho ni khơng số khơng phương có tất thừa số nguyên tố nhỏ H Tuy nhiên mở rộng tổng cho tất (n1 , , ne ), có (n1 , , ne ) khơng thỏa mãn hai điều kiện số hạng tương ứng 0, giá trị g(H) khơng thay đổi Thậm chí ta hạn chế phép lấy tổng na ≤ H, tồn a = {r, s} H cho na > H Nr > H = Vì Nr v g(H) = 1≤n1 ≤H µ(n1 ) µ(ne ) 1≤ne ≤H r=1 H , Nr bước chứng minh thứ hoàn thành Để hoàn thành chứng minh bước 2, ta cần biểu diễn g(H) dạng bội H v cộng thêm với sai số thích hợp Trước hết ta nhắc lại tính chất sau phần nguyên Bổ đề 2.2.11 Cho số thực z1 , z2 , z3 > Khi z1 z2 z3 = z1 z2 z3 − z1 z2 {z3 } − z1 {z2 } z3 − {z1 } z2 z3 , {z1 } , {z2 } , {z3 } kí hiệu phần lẻ z1 , z2 , z3 34 Áp dụng Bổ đề 2.2.11 cho v thừa số ta v g(H) = 1≤n1 ≤H − H N r=1 r µ(n1 ) µ(ne ) H N1 1≤ne ≤H 1≤n1 ≤H − µ(n1 ) µ(ne ) 1≤ne ≤H 1≤n1 ≤H 1≤ne ≤H H µ(n1 ) µ(ne ) N1 v H Nr r=2 H N2 v H Nr r=3 − 1≤n1 ≤H µ(n1 ) µ(ne ) 1≤ne ≤H H H N1 Nv−1 H Nv v v =H v 1≤n1 ≤H 1≤ne ≤H + µ(n1 ) µ(ne ) N r r=1 Rk , (2.26) k=1 với ≤ k ≤ v, Rk = − 1≤n1 ≤H µ(n1 ) µ(ne ) 1≤ne ≤H H H N1 Nk−1 H Nk H H Nk+1 Nv Lấy trị tuyệt đối hai vế với ý phần nguyên số khơng vượt q số phần lẻ số nằm đoạn [0; 1] ta |Rk | ≤ |µ(n1 ) µ(ne )| 1≤n1 ≤H 1≤ne ≤H ≤ H v−1 P + (m)≤H H H H H N1 Nk−1 Nk+1 Nv CG,k (m) , m |µ(n1 ) µ(ne )| CG,k (m) = m= 1≤r≤v,r=k Nr Lập luận tương tự Bổ đề 2.2.7, ta chứng minh hàm CG,k (m) hàm nhân Chú ý số CG,k (pα ) = CG,k,α không phụ thuộc vào p, CG,k (pα ) = CG,k,α = α > v Vì ta có P + (m)≤H CG,k (m) ≤ m 1+ p≤H CG,k,1 CG,k,2 CG,k,v + + p p2 pv = O(logCG,k,1 H), 35 CG,k (m) số (n1 , , ne ), với nj số khơng phương thỏa mãn Nr = m (2.27) 1≤r≤v,r=k Kí hiệu hk bậc đỉnh k Dễ dàng thấy với số nguyên tố p, ta có CG,k,1 = CG,k (p) = hk Các (n1 , , ne ) để (2.27) xảy có nj = 1, ngoại trừ nl = p, l cạnh qua đỉnh k Suy số (n1 , , ne ) lớn k đỉnh có bậc lớn Vì vậy, d bậc lớn đỉnh G giá trị lớn CG,k (p) d Do đó, |Rk | = O(H v−1 logd H) (2.28) Thay (2.28) vào (2.26) ta thu v g(H) = H v 1≤n1 ≤H µ(n1 ) µ(ne ) 1≤ne ≤H + O(H v−1 logd H) N r=1 r (2.29) Để kết thúc chứng minh bước ta cần Bổ đề sau Bổ đề 2.2.12 Ta có v lim H→∞ |µ(n1 ) µ(ne )| 1≤n1 ≤H 1≤ne ≤H < ∞ N r r=1 Chứng minh Xét hàm fG+ (m) = |µ(n1 ) µ(ne )| m= v r=1 Nr Theo Bổ đề 2.2.7 ta có fG+ (m) hàm nhân Dễ thấy fG+ (1) = Hơn nữa, cạnh nối hai đỉnh r s, nj | Nr nj | Ns Điều có nghĩa v n2j | Nr r=1 Suy v Nr = p, r=1 36 với số nguyên tố p fG+ (p) = Ta lưu ý (n1 , , ne ) tính fG+ (m) |µ(n1 ) µ(ne )| = Do nj số khơng phương Vì thừa số tích v Nr (2.30) r=1 chứa nhiều thừa số nguyên tố p Suy lũy thừa lớn p (2.30) pv Do fG+ (pα ) = với α > v Chú ý fG+ (pα ) + α hệ số xα Q+ G (z) Vì vậy, theo Bổ đề 2.2.8, fG (p ) phụ thuộc vào α mà khơng phụ thuộc vào p Vì thế, sử dụng tính chất fG+ (m) hàm nhân suy ∞ fG+ (m) = m m=1 p nguyên tố Chú ý dãy   fG+ (pv ) fG+ (p2 ) + + 1+ p2 pv v |µ(n1 ) µ(ne )|  1≤n1 ≤H 1≤ne ≤H r=1 < ∞ (2.31) ∞  Nr  H=1 dãy tăng dãy dãy bị chặn v 1≤n1 ≤H 1≤ne ≤H ∞ fG+ (m) ≤ |µ(n1 ) µ(ne )| N m m=1 r=1 r với H ∈ N Vì thế, theo định lí hội tụ đơn điệu, giới hạn v lim H→∞ |µ(n1 ) µ(ne )| 1≤n1 ≤H 1≤ne ≤H hữu hạn bị chặn N r=1 r ∞ fG+ (m) m m=1 Bây ta tiếp tục chứng minh bước Đặt v ρG := lim H→∞ 1≤n1 ≤H µ(n1 ) µ(ne ) 1≤ne ≤H 37 N r=1 r (2.32) Theo Bổ đề 2.2.12, ta có ρG chuỗi hội tụ tuyệt đối Thay vào (2.29) ta g(H) = HρvG + R + O(H v−1 logd H), ∞ ∞ v µ(n1 ) µ(ne ) ρG = ne =1 n1 =1 (2.33) , N r r=1 e |R| ≤ H ∞ ∞ v−1 ∞ ∞ ne =1 nj−1 =1 nj >H nj+1 =1 j=1 n1 =1 |µ(n1 ) µ(ne )| v N r r=1 Hơn nữa, ta có ∞ ρG = m m=1 ∞ µ(n1 ) µ(ne ) = N1 Nv =m fG (m) m m=1 Chú ý fG (m) hàm nhân theo Bổ đề 2.2.7 Vì lập luận tương tự Bổ đề 2.2.12, ta fG (1) = 1, fG (p) = fG (pα ) = 0, với α > v Do ∞ ρG = fG (m) = m m=1 1+ p nguyên tố fG (pv ) fG (p2 ) + + p2 pv Áp dụng Bổ đề 2.2.8, suy ρG = p QG p nguyên tố (2.34) Thay (2.34) vào (2.33), ta phải chứng minh bước 3: |R| = O(H v−1 logd H) Thật vậy, ta có e |R| ≤ H ∞ ∞ v−1 ∞ ∞ j=1 n1 =1 |µ(n1 ) µ(ne )| nj−1 =1 nj >H nj+1 =1 v ne =1 N r r=1 Tất số hạng tổng chạy j có vai trò tương tự nhau, nên khơng tính tổng qt ta giả sử tổng lớn Khi ta có ∞ |R| ≤ C1 H ∞ ∞ v−1 |µ(n1 ) µ(ne )| n1 >H n2 =1 nj+1 =1 38 v ne =1 , N r r=1 C1 hàm e khơng hàm H Vì ta cần chứng minh ∞ ∞ R1 := v |µ(n1 ) µ(ne )| ne =1 n1 >H n2 =1 = O(logd H) N r=1 r (2.35) Ta xem cạnh e1 = {u, s} khác với cạnh lại Với (n1 , , ne ) số khơng phương cho trước, ta hai số nguyên Nu = lcm(n1 , nα1 , nαk ), Ns = lcm(n1 , nβ1 , nβk ) Chú ý rằng, xảy Nu = lcm(n1 ) Ns = lcm(n1 ) Với cạnh ej ≤ j ≤ e, đặt dj = gcd(n1 , nj ) Vì nj số khơng phương nên ta có nj = dj nj , dj | n1 , gcd(n1 , nj ) Vì Nu = lcm(n1 , dα1 nα1 , , dαk nαk ) = n1 lcm(nα1 , , nαk ) Ns = n1 lcm(nβ1 , , nβl ) Với đỉnh t cho t = u t = s, ta có Nt = lcm(nt1 , , ntm ) = lcm(dt1 nt1 , , dtm ntm ) = lcm(dt1 , , dtm )lcm(nt1 , , ntm ) m thay đổi theo t Thay Nu , Ns Nt vào (2.35) ta ∞ R1 = ∞ |µ(n1 ) µ(ne )| n1 >H n2 =1 = n1 >H |à(n1 )| n21 ì 1≤t≤v t=u,t=s ne =1 ∞ d2 |n1 1 Nu Ns ∞ de |n1 n2 =1 ne =1 1≤t≤v t=u,t=s |µ(n2 ) µ(ne )| lcm(nα1 , , nαk )lcm(nβ1 , , nβl ) lcm(dt1 , , dtm )lcm(nt1 , , ntm ) 39 Nt Suy R1 = n1 >H |µ(n1 )| n21 ∞ × ∞ ne =1 × 1≤t≤v t=u, t=s de |n1 1≤t≤v t=u,t=s d2 |n1 lcm(dt1 , , dtm ) |µ(d2 n2 ) µ(de ne )| lcm(nα1 , , nαk )lcm(nβ1 , , nβl ) n2 =1 lcm(nt1 , , ntm ) Suy R1 ≤ n1 >H |à(n1 )| n21 ì n2 =1 ne =1 ì 1tv t=u, t=s |à(d1 ) µ(de )| d2 |n1 1≤t≤v t=u,t=s de |n1 lcm(dt1 , , dtm ) |µ(d2 n2 ) µ(de ne )| lcm(nα1 , , nαk )lcm(nβ1 , , nβl ) lcm(nt1 , , ntm ) Biểu thức ∞ ∞ n2 =1 ne =1 |µ(d2 n2 ) µ(de ne )| lcm(nα1 , , nαk )lcm(nβ1 , , nβl ) 1≤t≤v t=u, t=s lcm(nt1 , , ntm ) hữu hạn theo Bổ đề 2.2.12 (tuy nhiên ta xét đồ thị G khơng có cạnh {u, s}) Vì thế, tồn số C2 cho |µ(n1 )| |µ(d2 ) µ(de )| R1 ≤ C 2 n1 lcm(dt1 , , dtm ) 1≤t≤v n1 >H d2 |n1 de |n1 t=u,t=s (2.36) = C2 n1 >H |µ(n1 )| fG,e (n1 ), n21 hàm số học fG,e xác định sau, fG,e (n) = |µ(d1 ) µ(de )| d2 |n1 1≤t≤v t=u, t=s de |n1 40 lcm(dt1 , , dtm ) Chú ý tồn nhân tử lcm(dt1 , , dtm ) với đỉnh khác u s hàm fG,e hàm nhân Vì ta có fG,e (pk ) = fG,e (p) với lũy thừa k p thỏa mãn k ≥ 2, định nghĩa fG,e (pk ), có ước p pk làm cho số hạng không Suy n = p ta có Av−2 A1 + + v−2 , fG,e (p) = + p p Ai số cách mà |µ(d2 ) µ(de )|lcm(dt1 , , dtm ) = pi , 1≤t≤v t=u, t=s với ước tích dh | n = p p Bất đẳng thức Ai ≤ 2e−1 không phụ thuộc vào p, phải có số w không phụ thuộc p cho k fG,e (p ) = fG,e (p) ≤ ω 1+ p Vì fG,e hàm nhân nên với số khơng phương n, ta có fG,e (n) ≤ p|n 1+ p ω ω σ(n) n = , |µ(n)| = (2.37) Thay (2.37) vào (2.36) ta thu R1 ≤ C2 n>H |µ(n)| n2 σ(n) n ω ≤ C2 n>H n2 σ(n) n ω Ta có σ(n) = O(n log log n) Do R1 = O (log log H)ω H (2.38) Kết hợp (2.38) với (2.35) ta có điều phải chứng minh Ví dụ 2.2.13 Để tính tỉ lệ gần số nguyên dương tùy ý (a1 , a2 , a3 , a4 ) thỏa mãn gcd(a1 , a2 ) = gcd(a2 , a3 ) = gcd(a3 , a4 ) = gcd(a4 , a1 ) = 1, (2.39) xét đồ thị G(V, E) cho V = {1, 2, 3, 4} , E = {1, 2} , {2, 3} , {3, 4} , {4, 1} Áp dụng Định lý 2.2.9, tỉ lệ ρG = QG p nguyên tố , QG p 41 p |F | = (−1) F ⊆E p v(F ) , v(F ) số đỉnh không bị cô lập F Các hạng tử QG (z) tính bảng 2.1 cách liệt kê tập F ⊆ E để tính tốn Bảng 2.1: Các tập E phép tính tốn đa thức QG (z) F ⊆E |F | v(F ) (−1)|F | z v(F ) ∅ 0 {{1, 2}}, {{2, 3}}, {{3, 4}}, {{4, 1}} −4z 2 4z 2z 4 −4z 4 z4 {{1, 2}, {2, 3}}; {{2, 3}, {3, 4}}; {{3, 4}, {4, 1}}; {{4, 1}, {1, 2}} {{1, 2}, {3, 4}}; {{2, 3}, {4, 1}}, {{1, 2}, {2, 3}, {3, 4}}; {{2, 3}, {3, 4}, {4, 1}}; {{3, 4}, {4, 1}, {1, 2}}; {{4, 1}, {1, 2}, {2, 3}} E QG (z) = − 4z + 4z − z Suy 1− ρG = p nguyên tố 4 + 3− p p p = 0.217778 Hai bảng trang sau trình bày q trình tính toán fG (p4 ) fG+ (p4 ) 42 Bảng 2.2: Cách tính fG (p4 ) F ⊆E (n1 , , n4 ) (N1 , , N4 ) µ(n1 ) µ(n4 ) {{1, 2}, {2, 3}} (p, 1, p, 1) (p, p, p, p) {{2, 3}, {4, 1}} (1, p, 1, p) (p, p, p, p) {{1, 2}, {2, 3}, {3, 4}} (p, p, 1, p) (p, p, p, p) −1 {{2, 3}, {3, 4}, {4, 1}} (1, p, p, p) (p, p, p, p) −1 {{1, 2}, {3, 4}, {4, 1}} (p, 1, p, p) (p, p, p, p) −1 {{1, 2}, {2, 3}, {4, 1}} (p, p, 1, p) (p, p, p, p) −1 {{1, 2}, {2, 3}, {3, 4}, {4, 1}} (p, p, p, p) (p, p, p, p) fG (p4 ) = −1 Bảng 2.3: Cách tính fG+ (p4 ) F ⊆E (n1 , , n4 ) (N1 , , N4 ) |µ(n1 ) µ(n4 )| {{1, 2}, {2, 3}} (p, 1, p, 1) (p, p, p, p) {{2, 3}, {4, 1}} (1, p, 1, p) (p, p, p, p) {{1, 2}, {2, 3}, {3, 4}} (p, p, 1, p) (p, p, p, p) {{2, 3}, {3, 4}, {4, 1}} (1, p, p, p) (p, p, p, p) {{1, 2}, {3, 4}, {4, 1}} (p, 1, p, p) (p, p, p, p) {{1, 2}, {2, 3}, {4, 1}} (p, p, 1, p) (p, p, p, p) {{1, 2}, {2, 3}, {3, 4}, {4, 1}} (p, p, p, p) (p, p, p, p) fG+ (p4 ) = 43 Kết luận Luận văn trình bày số vấn đề xoay quanh tính chất nguyên tố đôi Trước hết, luận văn đưa số toán sơ cấp số nguyên tố đôi Tiếp theo luận văn chứng minh khng nh cho gi thuyt ca Erdăos k số phần tử lớn dãy số ngun dương khơng vượt q n để từ khơng trích k + số ngun tố đơi Cuối cùng, luận văn trình bày công thức gần để ước lượng số ba số nguyên dương không nguyên tố đôi số v số nguyên dương nguyên tố đôi tập cho trước 44 Tài liệu tham khảo Tiếng Anh [1] J Arias de Reyna and R Heyman (2014), Counting tuples with coprimality conditions, J Integer Seq., 18, 15.10.4 [2] U Balakrishnan and Y F S Pétermann (1996), The Dirichlet series of ζ(s)ζ α (s + 1)f (s + 1): On an error term associated with its coefficients Acta Arith., 75, 39-69 [3] Y-G Chen, X-F Zhou, (2013) On sequences containing at most pairwise coprime integers, Discrete Mathematics, 313, 357-365 [4] S G Choi, (1973) On sequences containing at most pairwise coprime integers, Transactions of the American Mathematical Society, 183, 437440 [5] S D Chowla (1929-1930), An order result involving the Euler ϕ- function, J Ind Math Soc Old Ser 18, 138-141 [6] C Ding, D Pei and A Salomaa (1996), The Chinese remainder theorem, World Scientific [7] P Erdăos (1965), Extremal problems in number theory, Proc Sympos Pure Math., Vol 8, Amer Math Soc, Providence, R I., 181-189 [8] R Heyman (2014), Pairwise non-coprimality of triples, Preprint, available at arXiv, pp 1309-5578 [math.NT] [9] R Heyman (2016), Topics in divisibility: pairwise coprimality, the GCD of shifted sets and polynomial irreducibility, Bull Aust Math Society, 94, 167-168 45 [10] R Heyman and I E Shparlinski (2013), On the number of Eisenstein polynomials of bounded height Appl Algebra Engrg Comm Comput., 24, 149-156 [11] V J Katz (2003), A history of mathematics (brief edition), Pearson/Addition-Wesley [12] J Y Liu (1997) On an error term of Chowla, I, J Number Theory, 64, 20-35 [13] G Maze, J Rosenthal and U Wagner(2011), Natural density of rectangular unimodular integer matrices, In Linear Algebra Appl., 434, 13191324 [14] P Moree (2015), Counting carefree couples, Preprint, available at arXiv, pp 0510003[math.NT] [15] J E Nymanm (1972), On the probability that k positive intergers are relatively prime, J Number Theory, 4, 469-473 [16] G Tenenbaum(1995), Introduction to analytic and probabilistic number theory, Cambridge University Press 46 ... gcd(a, bc) = 1.2 Về số nguyên tố đôi Mục tiêu tiết nhắc lại khái niệm, tính chất số tốn liên quan đến số nguyên tố đôi Định nghĩa 1.2.1 Một tập A tập số tự nhiên gọi nguyên tố đôi gcd(a, b) =... ngun tố đơi một, chúng nguyên tố nhau, tức gcd(a1 , , at ) = Tuy nhiên, điều ngược lại không Chẳng hạn, số 3, 5, nguyên tố nhau, không nguyên tố đôi (ii) Tồn tập hợp gồm vô hạn số nguyên tố đôi. .. Do m1 , , mt nguyên tố đôi nên x ≡ y (mod m1 mt ) Trong tốn phổ thơng, có nhiều tốn liên quan đến số nguyên tố đôi Dưới số ví dụ Bài tập 1.2.4 Tìm số nguyên dương nguyên tố đôi cho tổng hai