Luận văn Thạc sĩ Toán học: Một số bài toán về lũy thừa của các số nguyên

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:54

Thêm vào BST

Báo xấu

24
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn này là sưu tầm và trình bày lại lời giải cho một số bài toán thi Olympic về lũy thừa của các số nguyên. Đây là một trong những dạng toán hay gặp trong các đề thi học sinh giỏi, các đề thi Olympic toán học. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số bài toán về lũy thừa của các số nguyên

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– ĐỖ TRỌNG NGUYÊN MỘT SỐ BÀI TOÁN VỀ LŨY THỪA CỦA CÁC SỐ NGUYÊN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên, 11/2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– ĐỖ TRỌNG NGUYÊN MỘT SỐ BÀI TOÁN VỀ LŨY THỪA CỦA CÁC SỐ NGUYÊN LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp toán sơ cấp Mã số: 8 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGÔ VĂN ĐỊNH Thái Nguyên, 11/2019
i Mục lục Mở đầu 1 1 Biểu diễn số nguyên thành tổng riêng của lũy thừa của các nhân tử nguyên tố 3 1.1 Thặng dư bậc hai và luật thuận nghịch bậc hai . . . . . . . . . . . 3 1.2 ∗ Định nghĩa tập Sk,l . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Tính chất ∗ của tập Sk,l . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Tìm phần ∗ tử thuộc Sk,` . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Số Fibonacci và số Lucas dạng cx2 18 2.1 Dãy Fibonacci và dãy Lucas . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Một số tính chất số học của các số Fibonacci và các số Lucas . . . 21 2.3 Số Fibonacci và số Lucas dạng cx2 . . . . . . . . . . . . . . . . . . 25 3 Một số bài toán về lũy thừa của các số nguyên trong các kỳ thi Olympic Toán học quốc tế 37 3.1 Lũy thừa bậc hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Lũy thừa bậc ba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3 Lũy thừa của các số nguyên bậc bốn trở lên . . . . . . . . . . . . . 47 Kết luận 50 Tài liệu tham khảo 51
1 Mở đầu Mục đích của luận văn là trình bày lại một số bài toán liên quan đến lũy thừa của các số nguyên. Đây là một trong những vấn đề thú vị của lý thuyết số, được nhiều người quan tâm nghiên cứu và đã có rất nhiều kết quả phong phú. Bài toán đầu tiên chúng tôi quan tâm đến là bài toán biểu diễn các số nguyên thành tổng riêng lũy thừa của các nhân tử nguyên tố. Ký hiệu Sk là tập tất cả các số nguyên n có thể biểu diễn thành tổng lũy thừa k của tất cả các nhân tử nguyên tố phân biệt của n. Hiện nay, với k ≥ 2, chúng ta chưa có nhiều thông tin về tập hợp Sk , thậm chí, người ta mới chỉ tìm ra một số phần tử của S3 . De Koninck và Luca [3] đã đặt vấn đề nghiên cứu về các số nguyên có thể biểu diễn thành tổng riêng lũy thừa của các nhân tử nguyên tố. Các tác giả này đã khai thác được một số thông tin về các số nguyên này. Chúng tôi tập trung tìm hiểu và trình bày các kết quả này trong Chương 1 của luận văn. Bài toán thứ hai mà chúng tôi quan tâm là bài toán tìm các số Fibonacci và các số Lucas có dạng cx2 . Các số Fibonacci Fn và các số Lucas Ln là những số nổi tiếng, được nhiều nhà toán học quan tâm nghiên cứu. Đây cũng là hai dãy số nguyên có nhiều tính chất đẹp đã được tìm ra. Riêng bài toán nghiên cứu về các số Fibonacci và các số Lucas có dạng cx2 cũng đã được nhiều nhà toán học nghiên cứu. Trong Chương 2 của luận văn, chúng tôi tập trung tìm hiểu và trình bày lại kết quả của Cohn [2] về lời giải cho bài toán này khi c = 1, 2 và kết quả của Keskin và Yosma [5] về lời giải cho các phương trình Ln = 2Lm x2 , Fn = 2Fm x2 , Ln = 6Lm x2 , Fn = 3Fm x2 và Fn = 6Fm x2 . Vấn đề cuối cùng mà chúng tôi quan tâm trong luận văn này là sưu tầm và trình bày lại lời giải cho một số bài toán thi Olympic về lũy thừa của các số nguyên. Đây là một trong những dạng toán hay gặp trong các đề thi học sinh giỏi, các đề thi Olympic toán học. Nội dung này chúng tôi tham khảo trong cuốn
2 sách [1] của Andreescu và Andrica và được trình bày trong Chương 3 của luận văn. 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 của TS. Ngô Văn Định, Trường Đại học Khoa học - Đại học Thái Nguyên. Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới TS. Ngô Văn Định, người đã định hướng chọn đề tài và tận tình hướng dẫn để tôi hoàn thành luận văn này. Tôi xin bày tỏ lòng biết ơn chân thành tới Phòng Đào tạo, các thầy cô giáo dạy cao học chuyên ngành Phương pháp toán sơ cấp, trường Đại học Khoa học - Đại học Thái Nguyên đã giúp đỡ tôi trong suốt quá trình học tập và hoàn thành luận văn tốt nghiệp. Xin cảm ơn những người thân trong gia đình và tất cả những người bạn thân yêu đã hết sức thông cảm, chia sẻ và tạo điều kiện tốt nhất cho tôi để tôi có thể học tập, nghiên cứu và thực hiện luận văn của mình. Xin chân thành cảm ơn. Thái Nguyên, tháng 11 năm 2019 Người viết luận văn Đỗ Trọng Nguyên
3 Chương 1 Biểu diễn số nguyên thành tổng riêng của lũy thừa của các nhân tử nguyên tố Trong chương này, chúng tôi quan tâm đến bài toán biểu diễn số nguyên thành tổng lũy thừa của các nhân tử nguyên tố của nó. Ta ký hiệu Sk là tập tất cả các số nguyên có thể biểu diễn thành tổng lũy thừa k của các nhân tử nguyên tố của nó. Dễ dàng thấy rằng S1 chính là tập tất cả các số nguyên tố. Hiện nay, với k ≥ 2, người ta mới chỉ tìm thấy một số ví dụ về phần tử thuộc S3 mặc dù số phần tử của mỗi tập Sk có thể là vô hạn. Trong [4], De Koninck và Luca đã mở rộng nghiên cứu tập các số nguyên có thể biểu diễn thành tổng ∗ là tập tất cả riêng lũy thừa của các nhân tử nguyên tố. Cụ thể, nếu ký hiệu Sk,` các số nguyên có thể biểu diễn thành tổng ` lũy thừa k của các nhân tử nguyên [∞ ∗ tố phân biệt thì hai tác giả này đã chỉ ra được tập Sk,` có vô hạn phần tử k=2 khi ` ≥ 3 là số nguyên lẻ. Ngoài ra, hai tác giả này cũng đã chỉ ra một số tính ∗ . Mục đích chất khác liên quan và một số thuật toán tìm một số phần tử của Sk,` của chương là trình bày lại các kết quả này của De Koninck và Luca. 1.1 Thặng dư bậc hai và luật thuận nghịch bậc hai Trước khi trình bày nội dung chính của chương ở các mục sau, chúng tôi nhắc lại trong mục này một số kiến thức về thặng dư bậc hai, ký hiệu Legendre
4 và luật thuận nghịch bậc hai, đó là những công cụ sẽ được sử dụng ở phần sau của luận văn. Nội dung của các kiến thức này chúng tôi tham khảo trong cuốn sách “Elementary Number Theory with Applications” của Koshy [8]. Định nghĩa 1.1.1. Cho m là một số nguyên và a là một số nguyên sao cho (m, a) = 1. Khi đó số a được gọi là một thặng dư bậc hai của m nếu tồn tại một số nguyên x sao cho x2 ≡ a (mod m). Ví dụ 1.1.2. Xét với m = 4, ta thấy 12 ≡ 32 ≡ 1 (mod 4). Vậy 4 có một thặng dư bậc hai là 1. Xét với m = 13, ta thấy 12 ≡ 1 ≡ 122 (mod 13), 22 ≡ 4 ≡ 112 (mod 13), 32 ≡ 9 ≡ 102 (mod 13), 42 ≡ 3 ≡ 92 (mod 13), 52 ≡ 12 ≡ 82 (mod 13), 62 ≡ 10 ≡ 72 (mod 13). Vậy 13 có 6 thặng dư bậc hai là 1, 3, 4, 9, 10 và 12. Theo định nghĩa ở trên, số nguyên a là thặng dư bậc hai của m khi và chỉ khi phương trình đồng dư bậc hai x2 ≡ a (mod m) có nghiệm. Tiêu chuẩn Euler dưới đây cho ta một điều kiện cần và đủ để một số nguyên dương a là thặng dư bậc hai của m trong trường hợp m là một số nguyên tố lẻ p. Định lý 1.1.3 (Tiêu chuẩn Euler). Cho p là số nguyên tố lẻ. Khi đó một số nguyên dương a không chia hết cho p là một thặng dư bậc hai của p khi và chỉ khi a(p−1)/2 ≡ 1 (mod p). Ví dụ 1.1.4. Để kiểm tra 2 có phải là thặng dư bậc hai của 17 hay không, ta tính 2(17−1)/2 = 28 ≡ 1 (mod 17). Do vậy 2 là một thặng dư bậc hai của 17. Tương tự như vậy, ta có 3(17−1)/2 = 38 ≡ 16 ≡ −1 (mod 17). Do đó, 3 không là thặng dư bậc hai của 17. Như vậy tiêu chuẩn Euler cho ta một công cụ kiểm tra tính giải được của phương trình đồng dư x2 ≡ a (mod p). Tuy nhiên việc sử dụng công cụ này sẽ gặp khó khăn trong tính toán khi số nguyên tố p thực sự lớn. Một trong những công cụ hỗ trợ trong các tính toán này là ký hiệu Legendre.
5 Định nghĩa 1.1.5. Cho p là số nguyên tố lẻ và a là số nguyên bất kỳ sao cho p - a. Ký hiệu Legendre (a/p) được xác định bởi công thức  1 nếu a là thặng dư bậc hai của p, (a/p) = −1 cho trường hợp ngược lại. Ví dụ 1.1.6. Theo Ví dụ 1.1.2, 13 có 6 thặng dư bậc hai là 1, 3, 4, 9, 10 và 12 nên theo định nghĩa ký hiệu Legendre, ta có (3/13) = 1, (1/13) = 1, (4/13) = 1, (9/13) = 1, (10/13) = 1, (12/13) = 1, (2/13) = −1, (5/13) = −1, (6/13) = −1, (7/13) = −1, (8/13) = −1, (11/13) = −1. Sử dụng ký hiệu Legendre, tiêu chuẩn Euler có thể được phát biểu lại như sau. Định lý 1.1.7 (Tiêu chuẩn Euler). Cho p là số nguyên tố lẻ và a là một số nguyên dương thỏa mãn p - a. Khi đó, ta có (a/p) ≡ a(p−1)/2 (mod p). Hệ quả 1.1.8. Cho p là một số nguyên tố lẻ. Khi đó, ta có (−1/p) = (−1)(p−1)/2 . Nhận xét 1.1.9. Từ hệ quả trên ta có −1 là thặng dư bậc hai của p khi và chỉ khi p ≡ 1 (mod 4). Dưới đây là một số tính chất cơ bản của ký hiệu Legendre và luật thuận nghịch bậc hai mà chúng tôi nhắc lại không chứng minh. Mệnh đề 1.1.10. Cho p là một số nguyên tố lẻ, và a, b là các số nguyên bất kỳ thỏa mãn p - ab. Khi đó (1) Nếu a ≡ b (mod p) thì (a/p) = (b/p). (2) (a/p)(b/p) = (ab/p). (3) (a2 /p) = 1. Định lý 1.1.11 (Luật thuận nghịch bậc hai). Cho p và q là các số nguyên tố lẻ phân biệt. Khi đó ta có p−1 q−1 (p/q)(q/p) = (−1) 2 2 .
6 Luật thuận nghịch bậc hai được phát biểu lại dưới dạng gắn với thực tiễn tính toán như hệ quả sau. Hệ quả 1.1.12. Cho p và q là các số nguyên tố lẻ. Khi đó, ta có  (p/q) nếu p ≡ 1 (mod 4) hoặc q ≡ 1 (mod 4), (q/p) = −(p/q) nếu p ≡ q ≡ 3 (mod 4). Ví dụ 1.1.13. Xét với số nguyên tố 17. Vì 17 ≡ 1 (mod 4) nên ta có (17/3) = (3/17). Ở ví dụ trước ta thấy 3 không là thặng dư bậc hai của 17. Do đó, 17 cũng không là thặng dư bậc hai của 3. Xét trường hợp p = 47 và q = 3. Vì 47 ≡ 3 (mod 4) nên ta có (3/47) = −(47/3). Ta lại có 47(3−1)/2 = 47 ≡ 2 (mod 3) ≡ −1 (mod 3) nên 47 không là thặng dư bậc hai của 3 nhưng 3 là thặng dư bậc hai của 47. Mệnh đề dưới đây cho ta điều kiện cần và đủ để 2 và −2 là thặng dư bậc hai của số nguyên tố p. Mệnh đề 1.1.14. Cho p là một số nguyên tố lẻ. Khi đó (2/p) = 1 khi và chỉ khi p ≡ 1 (mod 8) (1.1) và (−2/p) = 1 khi và chỉ khi p ≡ 1 (mod 8) hoặc p ≡ 3 (mod 8). (1.2) ∗ 1.2 Định nghĩa tập Sk,l Từ mục này đến cuối chương, chúng tôi trình bày lại các kết quả của De Koninck và Luca [4] và kết quả của De Koninck [3] về bài toán biểu diễn số nguyên thành tổng riêng lũy thừa của các nhân tử nguyên tố. Định nghĩa 1.2.1. Cho số tự nhiên n, ký hiệu ω(n) là số nhân tử nguyên tố phân biệt trong phân tích tiêu chuẩn của n thành tích các nhân tử nguyên tố. Ví dụ 1.2.2. Trong phân tích nhân tử nguyên tố của n = 378 = 2 · 33 · 7 có 3 nhân tử nguyên tố phân biệt nên w(n) = 3. Tương tự, ta có w(15) = w(3 · 5) = 2,
7 w(2548) = w(22 · 72 · 13) = 3, w(2836295) = w(5 · 7 · 11 · 53 · 139) = 5. Định nghĩa 1.2.3. Cho số nguyên k ≥ 2, đặt X pk , Sk = n : ω(n) ≥ 2 và n = p|n trong đó tổng được lấy trên tập tất cả các nhân tử nguyên tố phân biệt của n. Nói một cách khác, Sk là tập các số nguyên có thể biểu diễn thành tổng lũy thừa k của các nhân tử nguyên tố của nó. Ví dụ 1.2.4. Ta có 378 = 2 · 33 · 7 = 23 + 33 + 73 , 2548 = 22 · 72 · 13 = 23 + 73 + 133 , 2836295 = 5 · 7 · 11 · 53 · 139 = 53 + 73 + 113 + 533 + 1393 , 4473671462 = 2 · 13 · 179 · 593 · 1621 = 23 + 133 + 1793 + 5933 + 16213 , 23040925705 = 5 · 7 · 167 · 1453 · 2713 = 53 + 73 + 1673 + 14533 + 27133 . Do đó, 5 số nguyên trên thuộc S3 . Hiện nay, theo chúng tôi được biết, người ta vẫn chưa tìm được số tự nhiên nào thuộc Sk với k = 2 hoặc k ≥ 4, mặc dù những tập này rất có thể là tập vô hạn phần tử. Như vậy, đối với tập Sk ta chưa có nhiều thông tin. Định nghĩa dưới đây cho ta tập số nguyên rộng hơn Sk , gồm các số nguyên có thể biểu diễn thành tổng riêng lũy thừa k của các nhân tử nguyên tố. Định nghĩa 1.2.5. Cho số nguyên k ≥ 2, đặt ∗ X Sk∗ pk , = n : ω(n) ≥ 2 và n = p|n trong đó dấu ∗ chỉ ra rằng tổng được lấy trên tập con của tập nhân tử nguyên tố của n.
8 Ví dụ 1.2.6. Ta có 870 = 2 · 3 · 5 · 29 = 22 + 52 + 292 , nên 870 ∈ S2∗ . Nhận xét 1.2.7. Rõ ràng với mỗi k ≥ 2, ta có Sk∗ ⊇ Sk . Từ đây ta quy ước ký hiệu các nhân tử nguyên tố phân biệt của một số nguyên là p1 , p2 , .... Để nghiên cứu tính chất của Sk∗ , De Koninck đã chia nhỏ tập Sk∗ thành các tập con như sau: Định nghĩa 1.2.8. Cho số nguyên k ≥ 2 và ` ≥ 3, đặt ∗ Sk,` = {n : n = pk1 + pk2 + · · · + pk` }, trong đó p1 , p2 , . . . , p` là các nhân tử nguyên tố phân biệt của n. Ví dụ, với k = 3, ` = 3, thì ∗ S3,3 = {n : n = p31 + p32 + p33 }, với p1 , p2 , p3 là các ước nguyên tố của n. Lưu ý rằng, do ta xét với ω(n) ≥ 2 nên trường hợp ` = 1 không xảy ra. Hơn nữa trường hợp ` = 2 cũng không thể xảy ra vì khi đó p1 , p2 không thể là nhân tử nguyên tố của n. Dựa vào Định nghĩa 1.2.8 và 1.2.5 ta thấy ∞ [ Sk∗ = ∗ Sk,` . `=3 ∗ 1.3 Tính chất của tập Sk,l ∗ , đặc biệt, Trong mục này, chúng tôi trình bày một số tính chất của tập Sk,l [∞ ∗ chúng tôi trình bày chứng minh tính vô hạn của tập Sk,` khi ` ≥ 3 là số k=2 nguyên lẻ cho trước. Trước tiên, ta xét tập S2∗ . Ký hiệu P (n) là ước nguyên tố lớn nhất của n. Mệnh đề 1.3.1. Nếu n ∈ S2∗ thì P (n) luôn xuất hiện trong tổng riêng lũy các nhân tử nguyên tố mà từ đó dẫn đến n thuộc S2∗ .
9 Chứng minh. Thật vậy, giả sử ngược lại, n có biểu diễn n = p1α1 · · · pαr r = p2i1 + · · · + p2i` ∈ S2∗ , trong đó p1 < p2 < · · · < pr , i1 < i2 < · · · < i` ≤ r − 1, với r ≥ 3. Ta có p1 · · · pr−2 pr−1 pr ≤ n < `p2i` ≤ rp2r−1 , hay p1 · · · pr−2 pr < rpr−1 < rpr . Suy ra p1 · · · pr−2 < r, điều này là không thể với r ≥ 3. Suy ra điều cần chứng minh. Xn Định nghĩa 1.3.2. Cho f (x) = ai xi là một đa thức với hệ số nguyên bậc i=0 n ≥ 1. Ta nói f (x) là đa thức bất khả quy nếu f (x) không phân tích được thành tích của hai đa thức hệ số nguyên với bậc lớn hơn hay bằng 1. Ví dụ 1.3.3. Các đa thức bậc nhất là đa thức bất khả quy, đa thức x2 + 1 là bất khả quy. Để chứng minh tập S3∗ là vô hạn, ta cần sử dụng giả thuyết của Schinzel dưới đây. Giả thuyết 1.3.4 (Giả thuyết Schinzel, [10]). Nếu f1 (x), . . . , fs (x) là các đa thức hệ số nguyên bất khả quy với hệ số cao nhất (hệ số của lũy thừa lớn nhất của x) dương sao cho không tồn tại số nguyên n > 1 nào là ước của tích f1 (x) . . . fs (x) với mọi x nguyên, thì tồn tại vô số số nguyên x để f1 (x), . . . , fs (x) đều là số nguyên tố. ∗ là tập vô hạn. Với Giả thuyết Schinzel ta có thể chứng minh S3,3 ∗ là tập vô hạn. Định lý 1.3.5. Nếu Giả thuyết Schinzel đúng thì S3,3 Chứng minh. Giả sử k là số nguyên sao cho r = k 2 − 9k + 21 và p = k 2 − 7k + 13 đều là số nguyên tố. Trong trường hợp này, ta có 2rp(r + k) = 2(k 2 − 9k + 21)(k 2 − 7k + 13)(k 2 − 8k + 21) = 2(k 4 − 16k 3 + 97k 2 − 264k + 273)(k 2 − 8k + 21) = 2k 6 − 48k 5 + 492k 4 − 2752k 3 + 8844k 2 − 15456k + 11466 (1.3)
10 và 23 + r3 + p3 = 8 + (k 2 − 9k + 21)3 + (k 2 − 7k + 13)3 = 8 + k 6 − 27k 5 + 306k 4 − 1863k 3 + 6426k 2 − 11907k + 9261 + k 6 − 21k 5 + 186k 4 − 889k 3 + 2418k 2 − 3549k + 2197 = 2k 6 − 48k 5 + 492k 4 − 2752k 3 + 8844k 2 − 15456k + 11466. (1.4) Từ (1.3) và (1.4) ta được 2rp(r + k) = 23 + r3 + p3 . ∗ . Bây giờ, do đa Do đó, đặt n = 2rp(r + k) = 23 + r3 + p3 thì ta có ngay n ∈ S3,3 thức r(k) = k 2 − 9k + 21 và p(k) = k 2 − 7k + 13 là các đa thức bất khả quy và thỏa mãn các giả thiết của giả thuyết Schinzel. Nếu giả thuyết Schinzel đúng thì đảm bảo rằng tồn tại vô số số nguyên k sao cho các số r(k) và p(k) là số nguyên tố, ∗ . từ đó tồn tại vô số n ∈ S3,3 Ví dụ 1.3.6. Thay k = 2 vào các giá trị r và p trong chứng minh của Định lý 1.3.5 thì ta được r = k 2 − 9k + 21 = 7, p = k 2 − 7k + 13 = 3, n1 = 2rp(r + k) = 2 · 7 · 3 · 9 = 2 · 33 · 7 = 378 = 23 + 33 + 73 . ∗ . Tương tự, với k = 6 ta được Vậy n1 = 378 ∈ S3,3 r = k 2 − 9k + 21 = 3, p = k 2 − 7k + 13 = 7, n2 = 2rp(r + k) = 2 · 3 · 7 · 9 = 2 · 33 · 7 = 378 = 23 + 33 + 73 . ∗ . Tương tự với k = 10, 82 và 94 ta lần lượt thu được Vậy n2 = n1 ∈ S3,3 n3 = 109306 = 2 · 31 · 43 · 41 = 23 + 313 + 433 , n4 = 450843455098 = 2 · 6007 · 6163 · 6089 = 23 + 60073 + 61633 ,
11 n5 = 1063669417210 = 2 · 8011 · 8191 · 8105 = 23 + 80113 + 81913 . ∗ . Nên n3 , n4 , n5 ∈ S3,3 Nhận xét 1.3.7. Không phải mọi giá trị của S3∗ có thể được sinh ra theo cách trên. Ví dụ, các số sau thuộc S3∗ nhưng không thể chứng minh được theo cách này: 23391460 = 22 · 5 · 23 · 211 · 241 = 23 + 2113 + 2413 , 173871316 = 22 · 223 · 421 · 463 = 23 + 4213 + 4633 , 4473671462 = 2 · 13 · 179 · 593 · 1621 = 23 + 133 + 1793 + 5933 + 16213 , 23040925705 = 5 · 7 · 167 · 1453 · 2713 = 53 + 73 + 1673 + 14533 + 27133 , 13579716377989 = 19 · 157 · 173 · 1103 · 23857 = 193 + 1573 + 1733 + 11033 + 238573 , 21467102506955 = 5 · 73 · 313 · 1439 · 27791 = 53 + 73 + 3133 + 14393 + 277913 , 119429556097859 = 7 · 53 · 937 · 6983 · 49199 = 73 + 533 + 9373 + 69833 + 491993 , 126548475909264420 = 22 · 3 · 5 · 11 · 83 · 101 · 45569 · 501931 = 23 + 53 + 833 + 455693 + 5019313 . Rõ ràng nếu Giả thuyết Schinzel là đúng thì từ định lý trên ta có thể suy ra ∞ [ ∗ tính vô hạn của tập hợp Sk,3 . Tuy nhiên, định lý sau đây cho ta tính vô hạn k=2 ∞ [ ∗ của tập hợp Sk,3 mà không cần đến Giả thuyết Schinzel. k=2 ∞ [ ∗ Định lý 1.3.8. # Sk,3 = +∞. k=2 Chứng minh. Tính chất này được suy ra ngay từ thực tế rằng với mỗi phần tử ∗ , ta có thể tìm một phần tử tương ứng n0 ∈ S ∗ n ∈ Sk,3 k(2r+1),3 với r = 1, 2, . . .. ∗ thì n có biểu diễn Thật vậy, nếu n ∈ Sk,3 n = pk1 + pk2 + pk3
12 với p1 , p2 , p3 là ước nguyên tố phân biệt của n. Nói riêng, điều này có nghĩa pa | (pkb + pkc ) với mỗi hoán vị (a, b, c) của các số nguyên 1, 2, và 3. Ta kết luận rằng cho trước số nguyên r bất kỳ, số k(2r+1) k(2r+1) k(2r+1) n0 = p1 + p2 + p3 ∗ thuộc Sk(2r+1),3 . Thật vậy, ta chỉ cần chỉ ra pa | (pbk(2r+1) + pck(2r+1) ) với mỗi hoán vị (a, b, c) của các số nguyên 1, 2 và 3. Nhưng điều này được suy ra từ kết quả rằng (pkb + pkc ) | (pk(2r+1) b k(2r+1) + pc k(2r+1) ); vì pa | (pkb + pkc ), suy ra pa | (pb k(2r+1) + pc ) và do đó n0 ∈ Sk(2r+1),3 ∗ ∗ , định lý được chứng minh. . Vì 378 ∈ S3,3 Nhận xét 1.3.9. Từ Định lý 1.3.5 và 1.3.8 ta thấy rằng nếu Giả thuyết Schinzel ∗ đúng thì #S3(2r+1),3 = +∞ với bất kỳ r ≥ 1. Tổng quát hơn, Định lý 1.3.8 được mở rộng cho ` là số lẻ. Định lý 1.3.10. Cho số nguyên lẻ bất kỳ ` ≥ 5, ta có ∞ [ ∗ # Sk,l = +∞. k=2 Định lý này là hệ quả trực tiếp của hai bổ đề sau. Bổ đề 1.3.11. Cho t = 2s ≥ 2 là số nguyên chẵn và p1 , . . . , pt là các số nguyên tố thỏa mãn (i) pi ≡ 3 (mod 4) với mọi i = 1, . . . , t; (ii) gcd(pi , pj − 1) = 1 với mọi i, j ∈ {1, . . . , t}; (iii) gcd(pi − 1, pj − 1) = 2 với mọi i 6= j ∈ {1, . . . , t}. Giả sử thêm rằng a1 , . . . , at là các số nguyên và n1 , . . . , nt là số nguyên dương sao cho các điều kiện dưới đây được thỏa mãn: (iv) gcd(2ni + 1, pi − 1) = 1 với mọi i = 1, . . . , t; Pt ni (v) pi | j=1 pj + ani i với mọi i = 1, . . . , t; (vi) s = t/2 số trong t ký hiệu Legendre (ai /pi ) với i = 1, . . . , t đều bằng 1 và s số còn lại đều bằng −1.
13 Khi đó tồn tại vô hạn số nguyên tố p sao cho S ∗p−1 ,t+1 chứa ít nhất 1 phần tử. 2 Chứng minh. Lấy a thỏa mãn a ≡ 2ni + 1 (mod (pi − 1)/2), a ≡ 3 (mod 4), a ≡ ai (mod pi ) (1.5) với mọi i = 1, . . . , t. Theo Định lý thặng dư Trung Hoa và các điều kiện (i)-(iii) luôn tồn tại số a như trên. Vì ni lẻ, (pi −1)/2 cũng lẻ và a ≡ 3 (mod 4), ta kết luận rằng đồng dư a ≡ 2ni + 1 (mod (pi − 1)/2) kéo theo a ≡ 2ni + 1 (mod 2(pi − 1)). t Y pi (pi − 1) Bây giờ đặt M = 4 . Chú ý rằng theo điều kiện (i)-(iv), a nguyên 2 i=1 tố cùng nhau với M . Do đó, theo định lý Dirichlet về số nguyên tố trong cấp số cộng, suy ra tồn tại vô số số nguyên tố p thỏa mãn p ≡ a (mod M ). Rõ ràng các số nguyên tố này thỏa mãn dùng đồng dư (1.5) giống như a. Gọi p là một số nguyên tố như vậy và đặt t X (p−1)/2 n= pi + p(p−1)/2 . i=1 Chú ý rằng vì p ≡ 2ni + 1 (mod 2(pi − 1)), ta được (p − 1)/2 ≡ ni ( mod pi − 1). Do đó, theo định lý Fermat và điều kiện (v) ta được t X t X n≡ pnj i +p ni ≡ pnj i + ani i ≡ 0 (mod pi ) j=1 j=1 với mọi i = 1, . . . , t. Cuối cùng, điều kiện (i), (v) và luật thuận nghịch bậc hai chỉ ra rằng từ t = 2s số (pi /p) = −(p/pi ) = −(ai /pi ), có đúng một nửa bằng 1 và nửa còn lại bằng −1. Do đó, một nửa số p(p−1)/2 i đồng dư 1 modulo p và một nửa còn lại đồng dư −1 modulo p, chỉ ra n là bội của p. Do đó, n là bội của pi với i = 1, . . . , t và của p, kéo theo n ∈ S ∗p−1 ,t+1 . 2 Bổ đề 1.3.12. Nếu s ≥ 2 thì tồn tại các số nguyên tố pi và các số nguyên ai , ni với i = 1, . . . , t thỏa mãn điều kiện của Bổ đề 1.3.11. Chứng minh. Ta có nhận xét t − 1 ≥ 3. Chọn các số nguyên tố p1 , . . . , pt−1 sao cho pi ≡ 11 (mod 12) với mọi i = 1, . . . , t − 1, gcd(pi , pj − 1) = 1 với mọi i, j ∈
14 {1, . . . , t − 1}, gcd(pi − 1, pj − 1) = 2 với mọi i 6= j ∈ {1, . . . , t − 1} và cuối cùng p1 + · · · + pt−1 nguyên tố cùng nhau với p1 · · · pt−1 . Chú ý rằng N = p1 + · · · + pt−1 là số lẻ. Ta có thể xây dựng được các số nguyên tố như trên bắt đầu với p1 = 11 và bằng cách đệ quy, tiếp tục định nghĩa p2 , . . . , pt−1 là các số nguyên tố theo cấp số cộng thích hợp. Lấy ni = 1 với mọi i = 1, . . . , t. Gọi q1 , . . . , q` là tất cả các ước nguyên tố của N. Chọn các số nguyên a1 , . . . , at−1 sao cho s trong các ký hiệu Legendre (−ai /pi ) bằng −1 và s − 1 ký hiệu còn lại bằng 1. Bây giờ chọn một số nguyên tố pt sao cho pt ≡ 11 (mod 12), pt nguyên tố cùng nhau với pi − 1 với i = 1, . . . , t − 1, pt ≡ −ai − N (mod pi ) với i = 1, . . . , t − 1, và (qi /pt ) = 1 với mọi i = 1, . . . , `. Để thỏa mãn các đồng dư thức này ta chỉ cần chọn pt ≡ 1 (mod qu ) nếu qu ≡ 1 (mod 4) và pt ≡ −1 (mod qu ) nếu qu ≡ 3 (mod 4), trong đó u = 1, . . . , `. Chú ý rằng cách chọn phù hợp với kết quả pt ≡ 11 (mod 12) nếu một trong các qu là 3. Cho đến bây giờ, các số nguyên tố p1 , . . . , pt thỏa mãn các điều kiện (i)-(iii) Y` của Bổ đề 1.3.11. Cuối cùng, đặt at = −N. Ta có (−at /pt ) = (qu /pt )αu = 1. Ở u=1 đây, αu là lũy thừa của qu trong −at . Do đó có đúng s ký hiệu Legendre (−ai /pi ) bằng 1 và các ký hiệu còn lại bằng −1 và vì tất cả các số nguyên tố pi đồng dư 3 modulo 4, điều tương tự cũng đúng nếu ta thay −ai bằng ai . Do đó, điều kiện (vi) của Bổ đề 1.3.11 thỏa mãn. Bây giờ, ta kiểm tra điều kiện (v) đúng với ni = 1 với mọi i = 1, . . . , t, bởi vì với mọi i = 1, . . . , t ta có t X n pj j + ani i ≡ N + pt + ai (mod pi ) ≡ 0 (mod pi ), j=1 trong khi t X n p j j + at = N + p t − N ≡ 0 (mod pt ), j=1 và điều kiện (iv) hiển nhiên bởi vì 2ni + 1 = 3 và pi − 1 ≡ 10 (mod 12) không là bội của 3 với i = 1, . . . , t. Nhận xét 1.3.13. Lập luận bên trên không đúng với s = 1. Thật ra, trong trường hợp này t − 1 = 1, do đó p1 + · · · + pt−1 = p1 và không nguyên tố cùng nhau với p1 .
15 ∗ 1.4 Tìm phần tử thuộc Sk,` Để tìm phần tử của Sk∗ , ta có thể tiến hành như sau: nếu n ∈ Sk,` ∗ thì tồn tại số nguyên dương Q và các số nguyên tố p1 , p2 , . . . , p` sao cho n = Qp1 · · · p`−1 p` = pk1 + · · · + pk`−1 + pk` , ∗ là p | (pk + · · · + pk ). với điều kiện cần để n thuộc Sk,` ` 1 `−1 ∗ , ta kiểm tra các nhân tử nguyên tố p của r k + q k Ví dụ, để tìm n ∈ Sk,3 với 2 ≤ r < q chạy qua các số nguyên tố cho tới giá trị x cho trước, và sau đó r k + q k + pk kiểm tra nếu Q = là số nguyên hay không. Nếu Q là số nguyên thì rpq ∗ . n = Qrqp thuộc Sk,3 Ví dụ, cho k = 2, chọn r = 2, q = 5 thì r2 + q 2 = 29 có ước nguyên tố là r 2 + q 2 + p2 29 + 292 p = 29. Kiểm tra ta được Q = = = 3 là một số nguyên. Do rpq 2 · 5 · 29 đó, n = Qrqp = 3 · 2 · 5 · 29 = 870 = r2 + q 2 + p2 = 22 + 52 + 292 thuộc S2,3∗ . Với r = 3, q = 5 thì r2 + q 2 = 34 có ước nguyên tố là p = 2 và 17. Kiểm tra ta được với r 2 + q 2 + p2 34 + 22 38 p = 2 thì Q = = = không là một số nguyên nên loại, với rpq 3·5·2 30 r 2 + q 2 + p2 34 + 172 323 p = 17 thì Q = = = không là một số nguyên nên loại. rpq 3 · 5 · 17 255 Tiến hành theo cách này (với ` = 3, 4), ta tìm được các phần tử sau thuộc S2∗ : 870 = 2 · 3 · 5 · 29 = 22 + 52 + 292 , 188355 = 3 · 5 · 29 · 433 = 52 + 292 + 4332 , 298995972 = 22 · 3 · 11 · 131 · 17291 = 32 + 112 + 1312 + 172912 , 1152597606 = 2 · 3 · 5741 · 33461 = 22 + 57412 + 334612 , 1879906755 = 3 · 5 · 2897 · 43261 = 52 + 28972 + 432612 , 5209105541772 = 22 · 3 · 11 · 17291 · 2282281 = 32 + 112 + 172912 + 22822812 . Mặc dù ta không thể tìm được bất kỳ phần tử nào thuộc S4 nhưng ta tìm được một vài phần tử thuộc S4∗ , mặc dù chúng rất lớn. Dưới đây là 6 phần tử thuộc S4∗ : 107827277891825604
16 = 22 · 3 · 7 · 31 · 67 · 18121 · 34105993 = 34 + 314 + 674 + 181214 , 48698490414981559698 = 2 · 34 · 7 · 13 · 17 · 157 · 83537 · 14816023 = 24 + 174 + 835374 , 3137163227263018301981160710533087044 = 22 · 32 · 7 · 11 · 191 · 283 · 7541 · 1330865843 · 2086223663996743 = 34 + 74 + 1914 + 13308658434 , 129500871006614668230506335477000185618 = 2 · 32 · 7 · 132 · 31 · 241 · 15331 · 21613 · 524149 · 1389403 · 3373402577 = 24 + 2414 + 33734025774 , 225611412654969160905328479254197935523312771590 = 2 · 32 · 5 · 7 · 132 · 37 · 41 · 109 · 113 · 127 · 151 · 541 · 911 · 5443 · 3198662197 · 689192061269 = 54 + 74 + 1134 + 1274 + 9114 + 6891920612694 , 17492998726637106830622386354099071096746866616980 = 22 · 5 · 7 · 23 · 31 · 97 · 103 · 373 · 1193 · 8689 · 2045107145539 · 2218209705651794191 = 24 + 1034 + 3734 + 11934 + 20451071455394 . ∗ , S ∗ , S ∗ và S ∗ . Chú ý rằng các số trên cho ta các phần tử thuộc S4,3 4,4 4,5 4,6 Các phần tử nhỏ nhất thuộc S2∗ , S3∗ , . . . , S10 ∗ tương ứng là các số sau: 870 = 2 · 3 · 5 · 29 = 22 + 52 + 292 , 378 = 2 · 33 · 7 = 23 + 33 + 73 , 107827277891825604 = 22 · 3 · 7 · 31 · 67 · 18121 · 34105993 = 34 + 314 + 674 + 181214 , 178101 = 32 · 7 · 11 · 257 = 35 + 75 + 115 , 594839010 = 2 · 3 · 5 · 17 · 29 · 37 · 1087 = 26 + 56 + 296 275223438741 = 3 · 23 · 43 · 92761523 = 37 + 237 + 437 26584448904822018 = 2 · 3 · 7 · 17 · 19 · 113 · 912733109 = 28 + 178 + 1138
17 40373802 = 2 · 34 · 7 · 35603 = 29 + 39 + 79 420707243066850 = 2 · 32 · 52 · 29 · 32238102917 = 210 + 510 + 2910 . ∗ khi Định lý 1.3.10 cho ta một cách để xây dựng vô hạn phần tử thuộc Sk,` cho trước một số nguyên lẻ ` dương cố định. Tuy nhiên, trong thực hành, các phần tử thu được rất lớn. Thật vậy, với trường hợp k = 5. Sử dụng ký hiệu của Bổ đề 1.3.11, ta có t = 4; khi đó ta có thể chọn {p1 , p2 , p3 , p4 } = {11, 47, 59, 227}. Như gợi ý trong Bổ đề 1.3.12, đặt ni = 1 với i = 1, 2, 3, 4. Tập số nguyên ai thích hợp là {a1 , a2 , a3 , a4 } = {8, 32, 10, 110}, mà có tập ký hiệu Legendre (ai /pi ) : i = 1, 2, 3, 4 = {−1, 1, −1, 1}. Tìm nghiệm a của hệ phương trình đồng dư  pi −1 a ≡ 3 (mod 2 ) (i = 1, 2, 3, 4)   a≡3 (mod 4)   a ≡ ai (mod pi ) (i = 1, 2, 3, 4),  4 Y pi (pi − 1) ta thu được a = 4619585064883. Với M = 4 = 10437648923020, ta chú 2 i=1 ý rằng gcd(a, M ) = 1. Số nguyên tố nhỏ nhất p ≡ a (mod M ) là p = 10M + a = ∗ xây dựng theo 108996074295083. Điều này có nghĩa số nguyên nhỏ nhất n ∈ Sk,5 thuật toán của ta là 4 X p−1 p−1 n= pi 2 + p 2 , i=1 là một số thực sự lớn.