Luận văn Các ước số của số mersenne

nne thứ 45 được tìm thấy 243112609 − 1, với hơn 10 triệu chữ số. Và chỉ một tháng sau, số nguyên tố Mersenne thứ 46 được tìm thấy là 237156667 − 1, nhỏ hơn số ở trên! George Woltman, một lập trình viên đưa lên một chương trình được tối ưu hóa cực cao phục vụ cho công cuộc tìm kiếm. Đó chính là chương trình GIMPS (Great Internet Mersenne Prime Search), thu hút hàng chục chuyên gia và hàng nghìn người nghiệp dư tham gia tìm kiếm. Số nguyên tố Mersenne lớn nhất hiện nay do ông tìm ra nhờ việc cho chương trình quét qua tất cả các lỗ hổng chưa được kiểm tra trước đó. Năm 2013, số nguyên tố Mersenne đã tìm ra là 257885161−1 có 17425170 chữ số. Quỹ Electronic Frontier Foundation (www.eff.org) trao giải thưởng 150.000 USD cho ai tìm được số nguyên tố Mersenne có trên 100 triệu chữ số và 250.000 USD cho số có trên 1 tỉ chữ số và 3000 USD cho bất kỳ số nguyên tố mới nào dưới 100 chữ số. Đến ngày 7− 1− 2017, số nguyên tố Mersenne mới nhất được công bố trong lễ kỷ niệm 20 năm ngày thành lập GIMPS. Đó là 274,207,281 − 1, có 22,338,618 chữ số. Bảng sau đây gồm 49 số nguyên tố Mersenne đã được biết đến năm 2017, trong đó ta ký hiệu Mp = 2 p − 1 là số nguyên tố Mersenne và Np là số hoàn hảo 2p−1(2p − 1) ứng với số nguyên tố p. 16 Số thứ tự p Số chữ số của Mp Số chữ số của Np Năm phát hiện Người phát hiện (1) (2) (3) (4) (5) (6) 1 2 1 1 ... ... 2 3 1 2 ... ... 3 5 2 3 ... ... 4 7 3 4 ... ... 5 13 4 8 1456 ... 6 17 6 10 1588 Cataldi 7 19 6 12 1588 Cataldi 8 31 10 19 1772 Euler 9 61 19 37 1883 Pervushin 10 89 27 54 1911 Powers 11 107 33 65 1914 Powers 12 127 39 77 1876 Lucas 13 521 157 314 1952 Robinson 14 607 183 366 1952 Robinson 15 1279 386 770 1952 Robinson 16 2203 664 1327 1952 Robinson 17 2281 687 1373 1952 Robinson 18 3217 969 1937 1957 Riesel 19 4253 1281 2561 1961 Hurwitz 20 4423 1332 2663 1961 Hurwitz 21 9689 2917 5834 1963 Gillies 22 9941 2993 5985 1963 Gillies 23 11213 3376 6751 1963 Gillies 24 19937 6002 12003 1971 Tuckerman Bảng 1.1: Bảng 24 số nguyên tố Mersenne đầu tiên 17 (1) (2) (3) (4) (5) (6) 25 21701 6533 13066 1978 Noll và Nickel 26 23209 6987 13973 1979 Noll 27 44497 13395 26790 1979 Nelson và Slowinski 28 86243 25962 51924 1982 Slowinski 29 110503 33265 66530 1988 Colquitt và Welsh 30 132049 39751 79502 1983 Slowinski 31 216091 65050 130100 1985 Slowinski 32 756839 227832 455663 1992 Slowinski và Gage 33 859433 258716 517430 1994 Slowinski và Gage 34 1257787 378632 757263 1996 Slowinski và Gage 35 1398269 420921 841842 1996 Armengaud, Woltman 36 2976221 895932 1791864 1997 Spence, Woltman 37 3021377 909526 1819050 1998 Clarkson, Woltman, Kurowski 38 6972593 2098960 4197919 1999 Hajratwala, Woltman, Kurowski 39 13466917 4053946 8107892 2001 Cameron, Woltman, Kurowski 40 20996011 6320430 12640858 2003 Shafer, Woltman, Kurowski 41 24036583 7235733 14471465 2004 Findley, Woltman, Kurowski 42 25964951 7816230 15632458 2005 Nowak, Woltman, Kurowski ? 30402457 9152052 18304103 2005 Cooper, Boone, Woltman, Kurowski ? 32582657 9808358 19616714 2006 Cooper, Boone, Woltman, Kurowski ? 37156667 11185272 22370543 2008 Elvenich, Woltman, Kurowski ? 42643801 12837064 25674127 2009 Strindmo, Woltman, Kurowski ? 43112609 12978189 25956377 2008 Smith, Woltman, Kurowski ? 57885161 17425170 34850339 2013 Cooper, Woltman, Kurowski ? 74207281 22338618 44677236 2017 Cooper, Blosser, Kurowski Bảng 1.2: Bảng 25 số nguyên tố Mersenne tiếp theo 18 Dấu ? được đặt ở vị trí thứ tự ứng với các số ở cùng dòng đó mà người ta chưa kiểm tra được liệu giữa chúng có còn số nào bị bỏ sót không. Chẳng hạn các giá trị từ p = 25964951 ở vị trí thứ 42 đến p = 30402457 ở vị trí dấu ? đầu tiên chưa được kiểm tra hết. Hiện nay, có nhiều thuật toán đặc biệt để kiểm tra nguyên tố các số Mersenne. Nhờ đó, người ta phát hiện được những số nguyên tố lớn. Mỗi lần có một số nguyên tố Mersenne, ta lại được một số hoàn hảo. Giả thuyết sau đây vẫn chưa được chứng minh. Giả thuyết 1.4 Tồn tại vô hạn số nguyên tố Mersenne. 1.3 Một số tính chất đặc biệt của số hoàn hảo chẵn Carolus phát hiện tổng các chữ số của một số hoàn hảo lớn hơn 6 chia cho 9 dư 1 và ước của số hoàn hảo là số thiếu, bội của số hoàn hảo là số thừa, ít nhất 1 trong 2 số 6n ± 1 là số nguyên tố và ngược lại bất kỳ số nguyên tố đều có dạng 6n± 1 (Cataldi sau đó sửa lại phát biểu thứ nhất và chứng minh phát biểu thứ 2). Trên cơ sở đó, năm 1844, L.Wantzel đã chứng minh được phát hiện trên của Kraft. Mệnh đề 1.4 Cho N là một số hoàn hảo chẵn. Khi đó 1. N ≡ 1 (mod 9). 2. Tổng lặp các chữ số của N bằng 1. Chứng minh. Viết N = 2n−1(2n − 1) trong đó 2n − 1 là một số nguyên tố. Do N > 6 nên n phải là một số nguyên tố khác 2. Vì n nguyên tố nên n = 3k + 1 hoặc n = 3k + 2. Với n = 3k + 1 thì k phải chẵn (n là nguyên tố), do vậy n = 6l + 1 và khi đó N = 26l(26l+1 − 1) = 64l(2.64l − 1) ≡ 1 (mod 9) Trường hợp còn lại hoàn toàn tương tự. 19 Bây giờ, kí hiệu N1 là tổng các chữ số của N , N2 là tổng các chữ số của N1,... Do N chia cho 9 dư 1 nên mọi Nj cũng vậy. Hơn nữa, dãy (Ni)i là giảm nên sẽ tồn tại i để cho Ni = 1. Năm 1652, J.Broscius nhận xét 6 = 1 + 2 + 3; 28 = 1 + 2 + 3 + 4 + 5 + 6 + 7; 496 = 1 + 2 + 3 + 4 + 5 . . .+ 29 + 30 + 31. Nhiều nhà toán học khác cũng nhận ra điều này, và gọi chúng là số tam giác, nghĩa là nếu lấy một số vòng tròn bằng nhau với số lượng bằng một số hoàn hảo thì bao giờ cũng có thể xếp chúng thành dạng một tam giác đều. Nói cách khác, số hoàn hảo bằng tổng của các số tự nhiên đầu tiên liên tiếp. Mệnh đề 1.5 Nếu N = 2n−1(2n − 1) là một số hoàn hảo chẵn thì N là một số tam giác. Chứng minh. Tổng của k số tự nhiên đầu tiên là 1 + 2 + . . .+ k = k(k + 1) 2 . Do đó, chọn k = 2n − 1, ta có ngay N = 2 n(2n − 1) 2 . Asadulla nhận ra các đẳng thức đẹp sau 28 = 13 + 33; 496 = 13 + 33 + 53 + 73; 8128 = 13 + 33 + 53 + 73 + . . .+ 153. và ông phát biểu: mọi số hoàn hảo chẵn lớn hơn 6 biểu diễn được dưới dạng tổng lập phương của các số lẻ liên tiếp. Mệnh đề 1.6 Nếu N = 2n−1(2n − 1) là một số hoàn hảo chẵn lớn hơn 6 thì N = 13 + 33 + 53 + . . .+ (2 n+1 2 − 1)3. 20 Chứng minh. Chú ý rằng ta có công thức n∑ i=1 i3 = n2(n+ 1)2 4 . Đặt m = 2 n−1 2 , ta có 13 + 33 + . . .+ (2m− 1)3 = (13 + 23 + . . .+ (2m)3)− (23 + 43 + . . .+ (2m)3) = (2m)2(2m+ 1)2 4 − 23m 2(m+ 1)2 4 = m2(2m+ 1)2 − 2m2(m+ 1)2 = m2(4m2 + 4m+ 1− 2m2 − 4m− 1) = m2(2m2 − 1) Thay m trở lại ta có công thức cần chứng minh. Năm 1896, C.Bourlet đã chứng minh rằng tổng của tất cả các nghịch đảo các ước của một số hoàn hảo bằng 2. Ta phát biểu nó dưới dạng mệnh đề sau Mệnh đề 1.7 Nếu n là một số hoàn hảo thì∑ d|n 1 d = 2. Chứng minh. Gọi di, i = 1, . . . , k là các ước của n. Lúc đó n di cũng là tất cả các ước của n. Do n là hoàn hảo nên 2n = k∑ i=1 n di . Vì vậy k∑ i=1 1 di = 2. Chứng minh tương tự cũng được tìm thấy trong các công trình của Pythago- ras, Palermo. Studnickad nhận xét rằng khi viết trong hệ nhị phân ta được 6 = 1102; 21 28 = 111002; 496 = 1111100002; 8128 = 11111110000002. Một cách tổng quát, ta có Mệnh đề 1.8 Nếu viết số hoàn hảo N = 2n−1(2n− 1) trong hệ cơ số 2 thì nó có 2n− 1 chữ số, trong đó n chữ số đầu tiên là 1 và n− 1 chữ số sau là 0. Chứng minh. Nhận xét 2n − 1 = 1 + 2 + 22 + . . .+ 2n−1. Do đó 2n−1(2n − 1) = 2n−1 + 2n + . . .+ 22n−2. Đó là điều phải chứng minh. 1.4 Số hoàn hảo lẻ Mặc dù số hoàn hảo chẵn và các tính chất của chúng đã được phát hiện khá nhiều nhưng có một điều lạ là người ta vẫn chưa tìm thấy bất kỳ một số hoàn hảo lẻ nào. Chính điều đó khiến số hoàn hảo lẻ trở nên bí ẩn hơn bao giờ hết, vì lẽ người ta chưa thể thấy được chúng. Số hoàn hảo lẻ có tồn tại hay không? Thêm nữa, nếu tồn tại, liệu ta có thể biết được gì về tính chất của chúng? Đó thực sự là một thách thức cực lớn, nhưng cũng là nguồn cảm hứng của không biết bao nhiêu tên tuổi lỗi lạc. Rene Descartes, trong một bức thư gửi tới Mersenne, ngày 15 tháng 11 năm 1638 đã cho rằng mọi số hoàn hảo lẻ phải có dạng ps2, với p là số nguyên tố. Descartes nghi ngờ rằng số hoàn hảo lẻ có thể tồn tại, ông cho rằng ps2 với p = 22021, s = 3.7.11.13 là hoàn hảo nếu p là số nguyên tố, tuy nhiên thật đáng tiếc p = 61.192 lại là một hợp số. Mặc dù vậy, Descartes vẫn không từ bỏ hi vọng. Trong một lá thư gửi tới Frenicle ngày 9 – 1 – 1639, ông tin tưởng rằng số hoàn hảo lẻ có thể được tìm thấy khi 22 thay các số 7, 11, 13 trong phân tích ra thừa số nguyên tố của s bởi những giá trị khác! Năm 1657, Frenicle tiến thêm một bước khi chứng minh số hoàn hảo lẻ nếu tồn tại sẽ có dạng pk2 với p là số nguyên tố dạng 4n + 1 và nhờ đó, M. Stuyvaert bổ sung thêm tính chất một số hoàn hảo lẻ nếu tồn tại thì phải là tổng của hai số chính phương. Leonard Euler đã chứng minh được khẳng định của Descartes ở trên, ông còn chỉ ra số hoàn hảo lẻ phải có dạng (4n+ 1)4k+1b2, trong đó 4n+ 1 là nguyên tố. Trong bài báo nổi tiếng How Euler Did It, tác giả Sandifer đã lí giải cách làm của Euler như sau: Giả sử n là một số hoàn hảo lẻ và n = n1n2 . . . nk trong đó các nhân tử ni là lũy thừa của các số nguyên tố phân biệt. Vì n lẻ nên các ni đều lẻ và ta có 2n = σ(n) = σ(n1) . . . σ(nk), 2n có tính chất là nó và các nhân tử của nó chia hết cho 2 nhưng không chia hết cho 4 (Euler gọi tính chất này là "oddly even"). Euler đã chỉ ra tập các σ(ni) chỉ có một số có tính chất này, các số còn lại đều phải lẻ. Nghiên cứu kĩ các lập luận của Euler, Sandifer khẳng định rằng các ni lẻ đều phải là lũy thừa chẵn của một số nguyên tố, còn nj duy nhất có tính chất "oddly even" được Euler viết dưới dạng nj = q m. Để σ(nj) là "oddly even", q phải là một số nguyên tố có dạng 4n+ 1 và m phải là một số lẻ có dạng 4λ+ 1. Desboves chỉ ra không có số hoàn hảo lẻ với chỉ hai hay ba nhân tử nguyên tố phân biệt và một số hoàn hảo lẻ có n nhân tử nguyên tố phân biệt thì nhân tử nguyên tố nhỏ nhất phải nhỏ hơn 2n. E.Cesaro đạt được ước lượng tốt hơn với khẳng định nhân tử nguyên tố nhỏ nhất ≤ n√2, Cl.Servais thậm chí còn chỉ ra rằng nó không vượt quá n. 23 Khi nghiên cứu về các nhân tử nguyên tố trong phân tích của một số hoàn hảo lẻ (nếu tồn tại), Servais đã chứng minh rằng nếu một số hoàn hảo lẻ chỉ có 3 ước nguyên tố phân biệt thì hai trong ba số đó là 3 và 5. Năm 1832, nhà toán học Mỹ Benjamin Peirce đã chứng minh rằng số hoàn hảo lẻ đầu tiên phải có ít nhất 4 nhân tử. Năm 1888, James Joseph Sylvester (nhà toán học Anh, 1814-1897) tìm được kết quả là số hoàn hảo lẻ có ít nhất 4 ước nguyên tố phân biệt, đến cuối năm 1888, ông đã tăng con số đó lên thành 5. Peirce và Sylvester đồng thời đạt được các kết quả độc lập với nhau. Sau năm đó, Sylvester đã công bố các công trình chứng minh số hoàn hảo lẻ chia hết cho 105 và không có số hoàn hảo lẻ không chia hết cho 3 với ít hơn 8 nhân tử nguyên tố. Năm 1913, L.E.Dickson đã chứng minh tập các ước nguyên tố phân biệt của các số hoàn hảo lẻ là hữu hạn. Đến năm 1972, Robbins của Viện Kĩ thuật Brooklyn và Pomerance của Đại học Harvard đã chứng minh được một số hoàn hảo lẻ phải chia hết cho ít nhất 7 nhân tử nguyên tố phân biệt. Năm 1957, Kanold chứng minh số hoàn hảo lẻ có ít nhất 20 chữ số, con số này tăng lên thành 30 năm 1973 với công trình của Tuckerman. Đến cuối 1973 là 50 chữ số và năm 1976 là 200 chữ số với công lao của các nhà toán học Buxton, Elmore và Stubblefield. Carl Pomerance, trong luận án tiến sĩ năm 1972 đã chứng minh được số hoàn hảo lẻ phải có ít nhất 7 thừa số nguyên tố phân biệt. Năm 2003, Pomerance viết thư cho Joshua Zelinsky, trong đó ông đưa ra một lập luận về xác suất, từ đó phỏng đoán rằng không tồn tại số hoàn hảo lẻ. Người ta cũng đã biết rằng mọi số hoàn hảo đều là số Ore. Trong đó số Ore (được đặt tên theo Oystein Ore-người đưa ra định nghĩa vào năm 1948) là một số nguyên dương thỏa mãn trung bình điều hòa của các ước của nó là một số nguyên, chẳng hạn 6 là một số Ore vì 4 1 1 + 1 2 + 1 3 + 1 6 = 2. 24 Hiện nay mới chỉ có một ít các số Ore được phát hiện là 1, 6, 28, 140, 270, 496, 672, 1638, 2970, 6200, 8128, 8190. Liên quan đến số hoàn hảo lẻ, có một giả thuyết (vẫn còn là bài toán mở) nói rằng chỉ có duy nhất một số Ore lẻ là 1. Thử làm một bản tổng kết, đến thời điểm hiện tại, tất cả những gì mới nhất chúng ta biết về số hoàn hảo lẻ được gói gọn trong các điều kiện để một số hoàn hảo lẻ n tồn tại: 1. n không chia hết cho 105. 2. n thuộc vào một trong 3 dạng n ≡ 1 (mod 12), n ≡ 117 (mod 468) hoặc n ≡ 81 (mod 324). 3. n > 101500 (kết quả mới nhất vừa mới công bố năm 2012). 4. n có dạng n = qαp2e11 . . . p 2ek k , trong đó (a) q, p1, . . . , pk là các số nguyên tố phân biệt. (b) q ≡ α ≡ 1 (mod 4). (c) Ước nguyên tố nhỏ nhất của n phải nhỏ hơn 2k + 8 3 . (d) Hoặc qα > 1062 hoặc p2eii > 10 62 với i nào đó (e) n < 24 k+1 . 5. Ước nguyên tố lớn nhất của n lớn hơn 108, ước nguyên tố lớn thứ hai phải lớn hơn 104 và ước nguyên tố lớn thứ ba phải lớn hơn 100. 6. n có ít nhất 101 thừa số nguyên tố và ít nhất 9 thừa số nguyên tố phân biệt. Nếu 3 không phải là một ước của n thì n có ít nhất 12 thừa số nguyên tố phân biệt. Hi vọng với những thành tựu mới đạt được liên tục và sự phát triển không ngừng của các máy tính siêu hiện đại, không lâu nữa chúng ta sẽ biết là số hoàn hảo lẻ có tồn tại hay không! 25 Chương 2 Các ước nguyên tố của số Mersenne 2.1 Ước lượng cận trên của tổng nghịch đảo các ước nguyên tố của số Mersenne Khi nghiên cứu phân bố số nguyên tố, người ta dựa vào đánh giá cấp tăng của tổng nghịch đảo các số nguyên tố. Đó là một trong những kết quả sâu sắc nhất của Toán học, với việc sử dụng hàm zeta Riemann. Vấn đề cũng được đặt ra tương tự với "phân bố" các số nguyên tố là các ước của số Mersenne. Trong chương này, chúng tôi giới thiệu một số kết quả nổi bật theo hướng này của P. Erdo˝s và cộng sự (xem [trích bài P. Erdo˝s]). 2.1.1 Phát biểu kết quả Các ước của các số Mesenne đã được nghiên cứu bởi nhiều tác giả. Gần đây, C. Pomerance [On primitive divisors of Mersenne numbers, Acta Arith. 46 (1986), 355-367.] đã thu được những kết quả về độ lớn của tổng nghịch đảo của các ước nguyên tố của các số Mersenne bằng chứng minh hoặc bác bỏ một số giả thuyết của P. Erdo˝s [On the sum ∑ d|2n−1 d −1, Israel J. Math. 9 (1971), 43-48]. Đặt f(n) = ∑ p|2n−1 1 p , n > 1; 26 tức f(n) là tổng nghịch đảo của các ước nguyên tố phân biệt của số Mersenne thứ n. P. Erdo˝s [On the sum ∑ d|2n−1 d −1, Israel J. Math. 9 (1971), 43-48] đã chỉ ra rằng có một hằng số dương c sao cho f(n) < log log log n+ c, (1) với mọi n lớn. Nhận xét rằng nếu n = m!, thì p|2n − 1 với tất cả các số nguyên tố p ≤ m và vì vậy f(n) > ∑ 2<p6m 1 p > log logm+ c > log log log n+ c, trong đó c là hằng số nào đó. Như vậy, đánh giá (1) là tốt nhất có thể, miễn là tìm được hằng số c nhỏ nhất. (Từ nay về sau, để đơn giản, ta luôn ký hiệu hằng số bởi chữ c, nên giá trị của c là khác nhau tuỳ thuộc công thức). Mặt khác, tổng nghịch đảo của các ước nguyên tố có thể nhỏ tùy ý. Ví dụ, ta có thể suy ra f(n) < c/ log n nếu n là số nguyên tố, bởi vì trong trường hợp này, mỗi ước nguyên tố của 2n − 1 lớn hơn n, và số các ước nguyên tố phân biệt thì bé hơn cn/ log n. Ngoài ra, từ một kết quả của P. Kiss và B. M. Phong, đối với các số Lucas, suy ra rằng bậc trung bình của f(n) nhỏ hơn một hằng số trong khoảng (x, x+ loglogx) khi x đủ lớn. Trong chương này ta chỉ ra rằng f(n) có thể "lớn" nhưng không "quá lớn", đối với tuỳ ý các số nguyên liên tiếp, và sẽ đưa ra công thức tiệm cận cho bậc trung bình của f(n) đúng trong một khoảng "ngắn". Định lí 2.1 Với mọi số dương C và số nguyên s tuỳ ý, tồn tại các số nguyên liên tiếp n, n+ 1, n+ 2, ..., n+ s sao cho f(n+ i) > C với i = 0, 1, ..., s. Thực ra, chúng ta có thể chứng minh dạng mạnh hơn của Định lí 2.1. Giả sử logk n ký hiệu logarit tự nhiên lặp lại k lần. Định lí 2.2 Với mỗi số nguyên k ≥ 2, tồn tại vô số n thỏa mãn min{f(n), f(n+ 1), ..., f(n+ k − 1)} > logk+2 n+ c logk+3 n, trong đó c là một hằng số tuyệt đối. 27 Có thể đặt ra câu hỏi bất đẳng thức trong Định lí 2.2 chính xác đến mức nào. Có thể thấy, chẳng hạn (trường hợp k = 2) min{f(n), f(n+ 1)} > log4 n+ c log5 n, với vô số n, là một kết quả yếu, và ta có thể hy vọng min{f(n), f(n+ 1)} = O(log3 n). Thực ra điều này không đúng. Chúng ta có Định lí 2.3 Tồn tại một hằng số c sao cho min{f(n), f(n+ 1)} ≤ c(log3 n)2/3(log4 n)1/3, với mọi n lớn. Vẫn còn một khoảng cách lớn giữa Định lí 2.2 trong trường hợp k = 2 và Định lí 2.3. Hầu như chắc chắn rằng Định lí 2.2 cho đánh giá chặt chẽ hơn. Chú ý rằng Định lí 2.3 không mâu thuẫn với Định lí 2.2 vì hệ số c trong định lí đó là số âm (do f(n) < 1). Xét hàm số g(n) = ∑ p (p− 1, n) p(p− 1) , trong đó, tổng xét với tất cả các số nguyên tố p. Về mặt nào đó g(n) là mô hình của f(n), vì ta có thể xem g(n) như lấy 1/p với "trọng" (p−1, n)/(p− 1), trong khi "xác suất" để p|2n− 1 là (p− 1, n)|(p− 1), vì p|2n− 1 khi và chỉ khi 2 là một (p− 1)/(p− 1, n) lũy thừa mod p. Người ta chứng minh rằng bậc lớn nhất của min{g(n), g(n+ 1), ..., g(n+ k − 1)}, là logk+2 n + O(logk+3 n) với mỗi k > 1, nhưng ta không trình bày chứng minh ở đây. Dễ thấy tồn tại một hằng số c0 > 0 sao cho x∑ n=1 f(n) = c0x+ o(x), 28 với mọi số nguyên x. Chúng ta chỉ ra rằng đánh giá trung bình này vẫn đúng với một khoảng rất ngắn. Định lí 2.4 Nếu z = z(x) là một hàm số có giá trị nguyên, mà z log log log x →∞ khi x→∞, thì với mỗi số tự nhiên x, x+z∑ n=x f(n) = c0z + o(z). Trong suốt chương này các chữ cái p, q sẽ kí hiệu các số nguyên tố. 2.1.2 Một số bài toán Từ Định lí 2.4 suy ra rằng 1 x . x∑ n=1 f(n)→ c0 khi x→∞. Đặt fT (n) = ∑ p|2n−1 p<T 1 p . Dễ chứng minh rằng với T > 0 1 x . x∑ n=1 fT (n)→ cT (n→∞), và cT → c0 khi T → ∞. Ngoài ra chúng ta có thể chứng minh rằng nếu y →∞ chậm một cách thích hợp thì 1 y . ∑ x<n6x+y fT (n)→ cT . Nhận xét rằng Định lí 2.4 là tốt nhất, nghĩa là nó sai nếu z  log log log x. Ta cần lưu ý rằng như đã thấy ở trên, f(n) log log log n là có thể. 29 Có thể chứng minh rằng mật độ của những số nguyên n mà f(n) 6 C tồn tại và là một hàm số liên tục của C. Sự phân bố như vậy vẫn đúng trong khoảng tuỳ ý x < n 6 x + g(x) log log log x, trong đó g(x) → ∞ chậm một cách thích hợp. Chúng ta bỏ qua chứng minh. Có lẽ những vấn đề sau là đáng quan tâm. Đúng hay không x+z∑ n=x ′f(n) = coz + o(z), khi z > log log log x, trong đó dấu phẩy ở tổng có nghĩa là số hạng lớn nhất của tổng bị xóa? Theo tinh thần của Định lí 2.3 có lẽ điều đó đúng dưới giả thiết sau đây. z/((log3 x) 2/3)(log4 x) 1/3)→∞. Như đã thấy trong Định lí 2.2, ta không hi vọng làm tốt hơn so với kết quả z/ log4 x→∞. Tổng quát hơn, có thể là đối với mỗi k cố định, x+z∑ n=x (k)f(n) = coz + o(z), khi z/ logk+3 x→∞, trong đó ∑(k) nghĩa là k số hạng lớn nhất bị bỏ khỏi tổng. Trong lời giới thiệu, ta nhận xét rằng, sự kiện f(p)  1/ log p rõ ràng khá tầm thường. Thực ra bằng cách sử dụng sự kiện các số nguyên tố q|2p − 1 thỏa mãn q ≡ 1(modp) và bất đẳng thức Brun - Titchmarsh, ta có thể chứng minh f(p) (log log p)/p. Ta giả sử pf(p) không giới nội. Chú ý rằng tồn tại tập hợp vô hạn "lớn" S các số nguyên tố p (lớn theo nghĩa là tổng nghịch đảo các phần tử của tập hợp S lấy đến x xấp xỉ bằng log log x, sao cho f(p) = o(1/p) với p ∈ S. Chúng ta kết thúc phần này với lời giải một bài toán khác của P. Erdo˝s [On primitive divisors of Mersenne numbers, Acta Arith. 46 (1986), 355 - 30 367]. Trong bài đó, P. Erdo˝s đưa ra giả thuyết: f(n) 6 max m6n ∑ p|m p>2 1 p + o(1) khi n→∞. Để chỉ ra điều đó không đúng, giả sử x đủ lớn và giả sử n là bội chung nhỏ nhất của mọi số nguyên dương cho đến x. Chú ý 2n−1 hiển nhiên chia hết cho mọi số nguyên tố lẻ p với p− 1|n. Mọi số nguyên tố lẻ p 6 x thỏa mãn điều kiện này. Nhưng từ một kết quả của P. Erdo˝s [On the normal number of prime factors of p-1 and some related questions concerning Euler’s φ− function, Quart. J. Math. Oxford Ser. 6 (1935), 205-213] , tồn tại những hằng số c > 0, α > 0, sao cho với mọi x đủ lớn và mọi t với t 6 x1+c, tồn tại ít nhất αpi(t) số nguyên tố p 6 t với p− 1|n. Như vậy ∑ x<p<x1+c p|2n−1 1 p  1. Do đó f(n)− ∑ 2<p6x 1 p > ∑ x<p<x1+c p|2n−1 1 p  1. Nhưng từ Định lí số nguyên tố,∑ 2<p6x 1 p = max m6n ∑ p|m p>2 1 p + o(1). Điều này kết thúc chứng minh phủ định giả thuyết đã nêu trong [On primitive divisors of Mersenne numbers, Acta Arith. 46 (1986), 355-367]. Có lẽ điều sau đây là đúng: f(n) 6 max m6n ∑ p−1|m p>2 1 p + o(1). 2.1.3 Chứng minh các Định lí 2.1 - 2.3 Trước hết, ta đưa vào một kí hiệu và nhắc lại một số tính chất cơ bản của dãy các số Mersenne. 31 Với mọi số nguyên dương lẻ m, tồn tại các số hạng trong dãy 2n−1, n = 1, 2, . . ., chia hết cho m. Kí hiệu r(m) là hạng của sự xuất hiện của m trong dãy; nghĩa là r(m) là một số nguyên dương sao cho m|2r(m) − 1 nhưng m . 2n−1 nếu 0 < n < r(m). Ta biết rằng, m|2n−1 khi và chỉ khi r(m)|n; Hơn nữa r(p)|p− 1 với mọi số nguyên tố lẻ p và r(m1m2) = [r(m1), r(m2)] với các số nguyên lẻ tuỳ ý nguyên tố cùng nhau m1,m2 ([,] kí hiệu Bội chung nhỏ nhất của các số). Để chứng minh Định lí 2.1 ta cần một kết quả bổ trợ. Bổ đề 2.1 Đối với các số thực dương C và số nguyên dương m tuỳ ý, tồn tại số nguyên n sao cho (m,n) = 1 và f(n) > C. Chứng minh. Giả sử C > 0 là số thực và m là một số nguyên. Ta có thể chọn các số nguyên tố p1, p2, . . . , pt có dạng 8km− 1 sao cho t∑ i=1 1 pi > C. Đối với các số nguyên tố đó, 2(pi−1)/2 ≡ 1 (mod pi), i = 1, 2, . . . , t, vì 2 là thặng dư bình phương modulo pi, cho nên r(pi) ∣∣∣pi − 1 2 . Vì vậy với các số p1p2 . . . pt, hạng của sự xuất hiện n := r(p1p2 . . . pt) = [r(p1), r(p2), . . . , r(pt)], thỏa mãn (n,m) = 1 và pi|(2n − 1) với i = 1, 2, . . . , t. Do đó f(n) > t∑ i=1 1 pi > C, thỏa mãn và bổ đề được chứng minh. Từ bổ đề này, Định lí 2.1 được suy ra. Chứng minh Định lí 2.1. 32 Do Bổ đề 2.5 ta có thể xây dựng các số nguyên n0, n1, . . . , ns sao cho (ni, nj) = 1 với mọi i 6= j và f(ni) > C với i = 0, 1, . . . , s. Do định lý Trung Quốc về phần dư, tồn tại các số nguyên n, n+ 1, . . . , n+ s sao cho ni|n + i với mọi i mà 0 6 i 6 s và từ tính chất của dãy 2n − 1 đã nói ở trên, ta có f(n+ i) > f(ni) > C, i = 0, 1, . . . , s, Điều này kết thúc chứng minh định lí. Chứng minh Định lí 2.2. Giả sử k > 2. Giả sử αj(n) = exp ( (logj n)/(logj+1 n) 2 ) , và giả sử Aj(n) là bội chung nhỏ nhất của các số nguyên cho đến αj(n). Giả sử B0(n) = Ak+1(n) và giả sử Bj(n) là ước lớn nhất của Ak+1−j(n) nguyên tố cùng nhau với Ak+2−j(n) với j = 1, . . . , k − 1. Khi đó (i) B0(n), . . . , Bk−1(n) nguyên tố cùng nhau từng đôi một, (ii) B0(n) . . . Bk−1(n) 6 A2(n) = n0(1), Đẳng thức cuối cùng được suy ra từ Định lí số nguyên tố. Do đó, từ định lí Trung Quốc về phần dư, tồn tại vô số số nguyên n với Bj(n)|n+ j với j = 0, 1, . . . , k − 1. (2.1) Giả sử (2.1) đúng với n. Khi đó, B0(n)|n, nên p−1|n với mọi số nguyên tố p 6 αk+1(n). Vì vậy f(n) > ∑ 2<p6αk+1(n) 1 p = log logαk+1(n) +O(1) = logk+2 n− 2 logk+3 n+O(1). (2.2) Giả sử (2.1) đúng với n và 1 6 j 6 k − 1. Giả sử Sj là tập hợp các số nguyên tố p sao cho (i) p 6 αk+1−j(n), (ii) p ≡ 7 (mod 8), (iii) ((p− 1)/2, Ak+2−j(n)) = 1. 33 Chú ý rằng nếu một số nguyên tố q|Ak+2−j(n), thì q 6 αk+2−j(n) 6 (logαk+1−j(n))o(1) . Vì Sj là tập hợp các số nguyên tố p thỏa mãn (i),(ii) sao cho (p− 1)/2 chỉ gồm các ước nguyên tố thuộc αk+2−j(n), từ sàng A. Sellberg (xem H. Halberstam và H-E.richert [Sieve Methods, Academic Press, Lon don 1974], Định lí 7.1) và một dạng mạnh của Định lí số nguyên tố đối với cấp số cộng suy ra rằng∑ p∈Sj p6t 1 ∼ 1 4 pi(t) ∏ 2<q6αk+2−j(n) ( 1− 1 q − 1 ) đều với exp ( (logαk+1−j(n)) ε ) 6 t 6 αk+1−j(n), với mọi ε > 0. Do đó∑ p∈Sj 1 p ∼ 1 4 log logαk+1−j(n) ∏ 2<q6αk+2−j(n) ( 1− 1 q − 1 )  log logαk+1−j(n) logαk+2−j(n)  logk+2−j n (logk+2−j n)/(logk+3−j n)2 = (logk+3−j n) 2. (2.3) Nhưng nếu p ∈ Sj và (2.1) đúng với n, thì p|2n+j − 1. Do đó, từ (2.3), f(n+ j) (logk+3−j n)2 > (logk+2 n)2, với j = 1, . . . , k− 1. Kết hợp với (2.2), điều này kết thúc chứng minh định lí.. Để chứng minh Định lí (2.3) trước hết ta chứng minh bổ đề sau. Bổ đề 2.2 ∑ x<p6xe p|2n−1 1 p  exp − ∑ log log x<q<log x q.n 1 q  một cách đều với mọi x > 3 và mọi số tự nhiên n. 34 Chứng minh. Giả sử m = ∏ log log x<q<(log x)1/7 q-n q. Khi đó ∑ x<p6xe p|2n−1 1 p 6 ∑ x<p6xe (p−1,m)=1 1 p + ∑ q|m ∑ x<p6xe p≡1 (mod q) p|2n−1 1 p . (2.4) Khi đó, bằng cách sử dụng sàng, ta có ∑ x<p6xe (p−1,m)=1 1 p  exp −∑ q|m 1 q  exp − ∑ log log x<q<log x q-n 1 q  . (2.5) G