Các hàm trong lý thuyết số và ứng dụng

  • Số trang: 26 |
  • Loại file: PDF |
  • Lượt xem: 51 |
  • Lượt tải: 0
thuvientrithuc1102

Đã đăng 15346 tài liệu

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ĐẶNG THỊ MỸ LINH CÁC HÀM TRONG LÝ THUYẾT SỐ VÀ ỨNG DỤNG Chuyên ngành : PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số : 60.46.40 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng - Năm 2012 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS.TS. Nguyễn Gia Định Phản biện 1: TS. Nguyễn Ngọc Châu Phản biện 2: PGS.TS. Trần Đạo Dõng Luận văn được bảo vệ trước Hội đồng chấm luận văn tốt nghiệp Thạc sĩ khoa học họp tại Đại học Đà Nẵng vào ngày 01 tháng 12 năm 2012. * Có thể tìm hiểu luận văn tại: − Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng − Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng 1 MỞ ĐẦU 1. Lịch sử, tính thời sự của vấn đề và sự liên quan đến các lĩnh vực khác Khoảng 4 thập niên gần đây, sự phát triển của Tin học đã làm thay đổi nhiều ngành truyền thống của lý thuyết số (ở đây chúng ta thường dùng thuật ngữ "số học"). Ngày nay, nhiều thành tựu mới nhất của số học có ứng dụng trực tiếp vào các vấn đề của đời sống, như thông tin, mật mã, kỹ thuật máy tính... và việc sử dụng rộng rãi máy tính trong nghiên cứu số học đã tạo nên một phương hướng mới của số học, đó là: số học và thuật toán. Số học ngày nay đã trở thành một khoa học thực nghiệm. Trong lý thuyết số, các hàm số học đóng một vai trò rất quan trọng, có nhiều ứng dụng của chúng trong nhiều ngành của toán học và khoa học máy tính. Một trong những kiến thức nâng cao mà học sinh cần hiểu biết thấu đáo để có thể áp dụng giải những bài toán số học là về các hàm số học. Ngoài ra, các hàm số học như hàm π , hàm li và hàm ζ Riemann cũng có một vai trò hết sức quan trọng trong các bài toán liên quan đến số nguyên tố. Hàm π xác định bởi π(x) là số các số nguyên tố không vượt quá số thực x. Năm 1793, Gauss đưa ra dự đoán: lim x→+∞ π(x) x log x = 1, được gọi là Định lý số nguyên tố (Prime Number Theorem). Các nhà toán học Gauss, Legrendre, Chebyshev, Riemann đã cố gắng chứng minh định lý này nhưng không thành công. Chứng minh đầu tiên của định lý này vào năm 1896 bởi Hadamard và Vallée-Poussin. Đây là kết quả quan trọng nhất trong lý thuyết số cho đến thời điểm này. Năm 1980, Selberg và Erdös đưa ra một chứng minh sơ cấp khác. Năm 1980, D.J. Newman đưa ra một chứng minh đơn giản hơn và trong chứng minh của mình, Newman sử dụng cơ sở giải tích phức. Nhờ vào x Định lý số nguyên tố, trong thực tế, người ta thường xấp xỉ π(x) bởi hàm . log x Gần đây, người ta sử dụng hàm li: Z x dt li(x) = 2 log t 2 để nhận được xấp xỉ tốt hơn cho hàm π(x). Đối với hàm ζ , vào năm 1737, Euler đưa ra định nghĩa : +∞ X 1 ζ(s) = ns n=1 với mọi số thực s > 1. Năm 1859, Riemann xét hàm ζ với giá trị phức để chứng minh Định lý số nguyên tố (nhưng bất thành!). Từ đó hàm ζ có một vai trò khá lớn trong số học và nhận được một số tính chất quan trọng trong số học. Xuất phát từ những vấn đề trên, chúng tôi quyết định chọn đề tài "Các hàm trong lý thuyết số và ứng dụng" với hy vọng sẽ tìm hiểu sâu về lý thuyết và ứng dụng của các hàm trong số học nhằm góp phần làm phong phú thêm các kết quả trong lĩnh vực này. Chúng tôi hy vọng đây là một tài liệu tham khảo tốt cho những người bắt đầu tìm hiểu về các hàm quan trọng trong lý thuyết số và ứng dụng của chúng trong các bài toán của số học và hy vọng các ví dụ minh họa và các bài toán ứng dụng góp phần làm phong phú thêm các kết quả trong lĩnh vực này. 2. Mục đích nghiên cứu Mục tiêu của đề tài nhằm nghiên cứu các hàm quan trọng trong lý thuyết số thể hiện qua phần lý thuyết và phần ứng dụng để giải một số lớp bài toán hay và khó trong số học. 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của đề tài là các hàm: hàm Möbius, hàm Euler, hàm Mangoldt, hàm Liouville, τ -hàm, σ -hàm suy rộng, hàm Legendre, π -hàm, li-hàm, ζ -hàm Riemann. Phạm vi nghiên cứu của đề tài là lý thuyết và ứng dụng các hàm trong lý thuyết số. 4. Phương pháp nghiên cứu Nghiên cứu tài liệu, phân tích, giải thích, đánh giá, tổng hợp và tham gia các buổi seminar của thầy hướng dẫn để trao đổi các kết quả đang nghiên cứu. 3 5. Ý nghĩa khoa học và thực tiễn của đề tài Tổng quan các kết quả của các tác giả đã nghiên cứu liên quan đến Các hàm trong lý thuyết số và ứng dụng nhằm xây dựng một tài liệu tham khảo cho những ai muốn nghiên cứu về các hàm quan trọng trong lý thuyết số và ứng dụng của chúng trong các bài toán của số học. Chứng minh chi tiết và làm rõ một số mệnh đề, cũng như xây dựng một hệ thống các bài toán cùng lời giải với các mức độ khó dễ khác nhau nhằm làm cho người đọc dễ dàng tiếp cận vấn đề được đề cập. 6. Cấu trúc của luận văn Chương 1 - Các hàm số học, nghiên cứu về các hàm số học thường sử dụng trong lý thuyết số, như hàm Mobius, hàm Euler, hàm Mangoldt, hàm Liouville, τ -hàm, σ -hàm suy rộng, hàm Legrendre và các khái niệm dẫn xuất cùng các tính chất liên quan. Chương 2 - Các hàm π , li và ζ Riemann, khảo sát các hàm số thực có vai trò quan trọng trong số học là π -hàm, li-hàm, ζ -hàm Riemann và trình bày các tính chất cơ bản của các hàm này, như là Định lý số nguyên tố và các hằng đẳng thức đối với ζ -hàm Riemann. Chương 3 - Các bài toán liên quan đến các hàm trong lý thuyết số, ứng dụng để giải các bài toán liên quan đến các hàm trong Chương 1 và Chương 2. CHƯƠNG 1 CÁC HÀM SỐ HỌC Các khái niệm và kết quả trong chương này có thể tìm thấy trong các tài liệu [1], [2] và [3]. 1.1 Hàm số học và tích chập Dirichlet Định nghĩa 1.1. Ánh xạ f : N∗ → C được gọi là một hàm số học. Như vậy, hàm số học cũng là một dãy số phức {cn }∞ n=1 với cn = f (n). Tuy nhiên, do người ta muốn khai thác các tính chất hàm nhiều hơn tính chất dãy 4 nên ta gọi f là một hàm số học hay một hàm lý thuyết số. Ví dụ 1.1. Các hàm sau đây là các hàm số học 0(n) = 0 ∀n ∈ N∗ , u(n) = 1 ∀n ∈ N∗ , N (n) = n ∀n∈ N∗ , N α (n) = nα ∀n ∈ N∗ ,    1 nếu n = 1 1 e(n) = = , n 0 nếu n > 1 P ω(n) = 1 = số các ước nguyên tố của n. p|n Chú ý 1.1. . Định nghĩa 1.2. Cho f, g là hai hàm số học. Khi đó, ta định nghĩa các phép toán đại số trên hai hàm số học f, g với mọi n ∈ N∗ như sau: - Phép cộng: (f + g)(n) = f (n) + g(n). - Phép nhân:(f.g)(n) = f (n).g(n).  f f (n) - Phép chia: (n) = với g(n) 6= 0. g g(n) - Phép nhân vô hướng: (λf )(n) = λf (n) với λ ∈ C. Định nghĩa 1.3. Cho f, g là hai hàm số học. Tích chập Dirichlet (hay phép nhân Dirichlet) của f và g , kí hiệu f ∗ g ,làmột hàm số học xác định như P P n sau: (f ∗ g)(n) = f (d)g(k) = f (d)g . d dk=n d|n Ví dụ 1.2. (N ∗ u)(6) = N (1)u(6) + N (2)u(3) + N (3)u(2) + N (6)u(1). Mệnh đề 1.1. Cho f, g, h là các hàm số học. Tích chập Dirichlet của các hàm số học có các tính chất sau: a) Tính kết hợp: (f ∗ g) ∗ h = f ∗ (g ∗ h). b) Tính giao hoán: f ∗ g = g ∗ f . c) Tính phân phối đối với phép cộng: f ∗ (g + h) = f ∗ g + f ∗ h. d) Tính giản ước được: f = g ⇔ f ∗ h = g ∗ h với h 6= 0. e) Tính tương thích phép nhân vô hướng: λ(f ∗ g) = (λf ) ∗ g = f ∗ (λg). f) Tính có đơn vị: f ∗ e = e ∗ f = f . Với các tính chất trên, ta thấy tập tất cả các hàm số học với các phép toán cộng, nhân và phép tích chập Dirichlet tạo thành một đại số trên C. Hơn nữa, đó là đại số kết hợp, giao hoán và có đơn vị. 5 Định lý 1.1. Nếu f là một hàm số học với f (1) 6= 0 thì tồn tại duy nhất hàm số học f −1 , gọi là nghịch đảo Dirichlet của f , sao cho f ∗ f −1 = f −1 ∗ f = e. Ngoài ra, f −1 được cho bởi công thức đệ quy 1 −1 X  n  −1 −1 −1 , f (n) = f f (d), với n > 1. f (1) = f (1) f (1) d d|n d 1 Chú ý 1.3. µ ∗ u = e. Định lý 1.4 (Công thức ngược Möbius). Cho f, glà hai hàm số học. Khi đó P P n g(n) = f (d) khi và chỉ khi f (n) = g(d)µ . d d|n d|n Định lý 1.5. Hàm f là hàm nhân tính hoàn toàn khi và chỉ khi f là hàm nhân tính có f −1 (n) = µ(n)f (n). Định lý 1.6 (Công thức tổng - tích). Nếu f là hàm nhân tính thì X Y µ(d)f (d) = (1 − f (p)), d|n p|n với p là số nguyên tố. 1.3 Hàm Euler Định nghĩa 1.9. Hàm Euler ϕ(n) là hàm xác định với mọi n ∈ N∗ , được định nghĩa là số các số nguyên dương không vượt quá n và nguyên tố cùng nhau với n. Tức là ϕ(n) = #{i ∈ N∗ /i ≤ n và (i, n) = 1}. Ở đây, ký hiệu #A là số phần tử của tập hợp A. 7 Chú ý 1.4. ϕ(n) = n  X m=1  1 . U CLN (n, m) Ví dụ 1.8. Định lý 1.7. Với n ≥ 1, ta có công thức tổng P ϕ(d) = n. d|n Định lý 1.8. Với n ≥ 1, ta có thể biểu diễn hàm Euler dưới dạng tổng như P P µ(d) n sau ϕ(n) = µ(d) = n . d d d|n d|n Định lý 1.9. Với n≥ 1, hàm  Euler có thể được biểu diễn dưới dạng tích Q 1 như sau ϕ(n) = n 1− , với p là số nguyên tố. p p|n Mệnh đề 1.5. Cho số nguyên tố p và một số nguyên α ≥ 1. Khi đó ϕ(pα ) = pα − pα−1 .   d Mệnh đề 1.6. Với d = (m, n) thì ϕ(mn) = ϕ(m)ϕ(n) . Từ đó suy ra ϕ(d) hàm ϕ(n) không phải là hàm nhân tính hoàn toàn. Mệnh đề 1.7. Hàm Euler ϕ(n) là hàm nhân tính. Mệnh đề 1.8. Nếu a|b thì ϕ(a)|ϕ(b). Mệnh đề 1.9. ϕ(n) là chẵn với n ≥ 3. Ngoài ra, nếu n có r nhân tử nguyên tố lẻ phân biệt thì 2r |ϕ(n). Định lý 1.10 (Euler). Nếu n là một số nguyên dương và a là số nguyên tố cùng nhau với n thì aϕ(n) ≡ 1 (mod n) 1.4 Hàm Mangoldt Λ(n) Tiếp theo ta có hàm số học Mangoldt Λ đóng một vai trò trung tâm trong việc phân bố các số nguyên tố. Định nghĩa 1.10. Với mỗi số nguyên n ≥ 1, ta định nghĩa  log p nếu n = pm với số nguyên tố p và m ≥ 1 nào đó, Λ(n) = 0 trong các trường hợp khác. Vì Λ(1) = 0, hàm Mangoldt không phải là hàm nhân tính. 8 Ví dụ 1.9. Định lý 1.11. Nếu n ≥ 1 ta có log n = P Λ(d). d|n Định lý 1.12. Nếu n ≥ 1 ta có Λ(n) = P µ(d) log d|n 1.5 P n = − µ(d) log d. d d|n Hàm Liouville λ(n) Một ví dụ quan trọng về hàm nhân tính hoàn toàn là hàm Liouville λ được định nghĩa như sau: Định nghĩa 1.11. Hàm Liouville là một hàm số học được định nghĩa như sau  1 λ(n) = (−1)a1 +a2 +...+ak nếu n = 1, nếu n = pa11 pa22 . . . pakk . Định nghĩa này chứng tỏ ngay rằng λ là hàm nhân tính hoàn toàn. Định lý dưới đây mô tả tổng ước của hàm λ. Định lý 1.13. Với mỗi n ≥ 1, ta có  1 nếu n là một bình phương, X λ(d) = 0 trong trường hợp khác. d|n Ngoài ra, λ−1 (n) = |µ(n)| với mọi n. 1.6 τ -hàm Định nghĩa 1.12. Hàm τ (n) được định nghĩa là số các ước dương của một P số nguyên dương n, kể cả 1 và n. Tức là τ (n) = 1. d|n d≥1 Ví dụ 1.10. Mệnh đề 1.10. Với n ∈ N∗ , ta có công thức τ (n) = (u ∗ u)(n). Mệnh đề 1.11. Hàm τ (n) là hàm nhân tính. Định lý 1.14. Giả sử số nguyên dương n được phân tích ra thừa số nguyên k Q a1 a2 ak tố như sau n = p1 p2 ...pk . Khi đó τ (n) = (ai + 1). i=1 Ví dụ 1.11. τ (126) = τ (2.32 .7) = (1 + 1)(2 + 1)(1 + 1) = 12. 9 1.7 σ-hàm suy rộng Định nghĩa 1.13. Hàm σα (n) được định nghĩa là tổng các lũy thừa bậc α của các ước dương của một số nguyên dương n, kể cả 1 và n, với α là một P α số phức bất kỳ. Tức là σα (n) = d . d|n d≥1 Ví dụ 1.12. σ2 (10) = 12 + 22 + 52 + 102 = 130. Mệnh đề 1.12. Với n ∈ N∗ , ta có công thức σα (n) = (N α ∗ u)(n). Mệnh đề 1.13. Hàm σα (n) là hàm nhân tính. Chú ý 1.5. Hàm σα (n) là hàm nhân tính nhưng không nhân tính hoàn toàn. Chú ý 1.6. Khi α = 0, σ0 (n) là số các ước dương của n, đó chính là τ (n). Khi α = 1, σ1 (n) là tổng các ước dương của n, thường được ký hiệu là σ(n). Định lý 1.15. Giả sử số nguyên dương n được phân tích ra ! thừa số nguyên α(ai +1) Q pi −1 tố như sau n = pa11 pa22 ...pakk . Khi đó σα (n) = . pαi − 1 pi |n  (1+1)   (2+1)   (1+1)  2 − 1 3 − 1 7 − 1 = Ví dụ 1.13. σ(126) = σ(2.32 .7) = 2−1 3−1 7−1 312. Định lý 1.16. Số các số nguyên tố là vô hạn. Định nghĩa 1.14. Số nguyên dương n được gọi là số hoàn hảo nếu σ(n) = 2n. Định lý 1.17. Số nguyên dương chẵn n là số hoàn hảo khi và chỉ khi n = 2m−1 (2m − 1), trong đó m là một số nguyên sao cho m ≥ 2 và 2m − 1 là số nguyên tố. 1.8 Hàm Legendre Định nghĩa 1.15. Với mọi số nguyên dương n, hàm Legendre ep (n) được định nghĩa là số mũ của số nguyên tố p trong phân tích thành thừa số nguyên tố của n!. Tức là ep (n) = vp (n!). Ở đây, vp (a) là số mũ của p trong phân tích của a. 10 Ví dụ 1.14. e2 (6) = v2 (6!) = v2 (1.2.3.4.5.6) = v2 (24 .32 .5) = 4. Chú ý 1.7. Hàm Legendre không phải là hàm nhân tính, cũng không phải là hàm cộng tính. Định lý 1.18 (Công thức Legendre). Với mỗi số nguyên tố p và mỗi số nguyên dương n, ta có công thức ep (n) = b lnln np c   X n pi i=1 = n − Sp (n) , p−1 với Sp (n) là tổng các chữ số trong khai triển p - phân của n (khai triển theo cơ số p của n). Ví dụ 1.15. e7 (400) =  400  7 +  400  72 +  400  73 CHƯƠNG = 57 + 8 + 1 = 66. 2 CÁC HÀM π, li và ζ RIEMANN Các khái niệm và kết quả trong chương này có thể tìm thấy trong tài liệu [3]. 2.1 π-hàm và li-hàm Định nghĩa 2.1. Hàm π(x) được định nghĩa là số các số nguyên tố không P 1. Ở đây, p là số nguyên tố. vượt quá số thực x. Tức là π(x) = p≤x Ví dụ 2.1. π(2) = 1, π(6) = 3, π(21) = 8, π(59) = 17, π(100) = 25. Z x dt Định nghĩa 2.2. Hàm li(x) được định nghĩa như sau li(x) = , với 2 log t log t là logarit cơ số e của t. Chú ý 2.1. Hàm li(x) được xác định trong quá trình tìm xấp xỉ cho hàm π(x). Năm 1793, Gauss đã dùng hàm x/ log(x) để xấp xỉ cho hàm π(x). Tuy nhiên, sau này, người ta nhận thấy rằng tỷ số π(x)/li(x) dần đến 1 nhanh hơn tỷ số π(x) log(x)/x khi x dần đến vô cùng, cho nên li(x) là một xấp xỉ tốt hơn đối với π(x). 11 2.2 Định lý số nguyên tố Định lý 2.1. Cho x là một số nguyên dương, π(x) là số các số nguyên tố không vượt quá x. Khi đó x π(x) ∼ log x hay π(x) lim = 1. x→∞ x/ log x Chú ý 2.2 (Lịch sử bài toán). Từ việc kiểm tra bảng các số nguyên tố bé hơn 106 , Gauss cùng với Legendre đã độc lập phát biểu rằng với x lớn, tỷ số π(x) ≈ 1 và phỏng đoán nó sẽ tiến tới 1 khi x dần đến vô cùng. Gauss x/ log(x) và Legendre đã cố gắng chứng minh điều này nhưng không thành công. Năm 1851, Chebyshev đã tạo ra một bước tiến quan trọng với chứng minh π(x) có giới hạn, thì giới hạn đó phải bằng 1. rằng nếu tỷ số x/ log(x) Năm 1859, Riemann chứng minh điều này với phương pháp giải tích, dùng giải tích phức để nghiên cứu hàm π(x). Ông cho rằng sự phân bố của các số nguyên tố liên quan đến các 0 - điểm không tầm thường của hàm zeta ∞ 1 P Riemann ζ(s) = , chính là các điểm trên đường thẳng {s ∈ C/Re(s) = s n=1 n 1 }. Tuy nhiên, những kiến thức cần cho việc chứng minh của ông chưa phát 2 triển đầy đủ. Và Riemann đã không thể hoàn thành chứng minh của mình trước khi ông qua đời vào năm 1866. Ba mươi năm sau, với những công cụ giải tích đã có sẵn, năm 1896, J. Hadamard và C. J. de la Vallée Poussin độc lập chứng minh thành công rằng π(x) log(x) = 1. x→∞ x lim Kết quả đáng chú ý này được gọi là Định lý số nguyên tố, và phép chứng minh của nó là một trong những thành tựu rực rỡ của lý thuyết giải tích số. Năm 1949, Atle Selberg và Paul Erdös gây ra bất ngờ khi khám phá chứng minh sơ cấp của định lý số nguyên tố. 12 2.3 Một bất đẳng thức của π-hàm Định lý 2.2. Với mỗi số nguyên dương n, n ≥ 2, ta có bất đẳng thức sau 1 n n − < π(n) < 6. . 6 log n log n Bất đẳng thức này được biết là bất đẳng thức Chebyshev đối với hàm π(n). Chứng minh. Tham khảo cuốn toàn văn của luận văn. 2.4 ζ-hàm Riemann Định nghĩa 2.3. Hàm Riemann zeta ζ được định nghĩa như sau +∞ X 1 ζ(s) = , ns n=1 với mọi số thực s > 1. Chú ý 2.3. Hàm ζ(s) được định nghĩa bởi Leonhard Euler (1707 - 1783) lần đầu tiên năm 1737. Hơn một thế kỷ sau, năm 1859, Riemann đã khám phá ra hàm zeta với giá trị phức của s khi đang cố gắng chứng minh định lý số nguyên tố. Trong công trình của mình, Riemann đã xây dựng sáu giả thuyết, để từ đó có thể sử dụng chứng minh Định lý số nguyên tố. Tuy nhiên, cho đến nay, chỉ có năm giả thuyết đã được chứng minh. Giả thuyết thứ sáu chính là giả thuyết Riemann nổi tiếng, được biết đến như một trong những vấn đề mở khó nhất của Toán học. 2.5 Một số tính chất cơ bản của ζ-hàm Mệnh đề 2.1 (Đồng nhất thức Euler). Với s là số thực bất kì, s > 1, ta có Y 1 , ζ(s) = 1 − p−s p trong đó tích được mở rộng trên tất cả các số nguyên tố p. Hệ quả 2.1. Theo đồng nhất thức Euler, ta có hệ quả sau ζ(2s) Y 1 = . ζ(s) 1 + p−s p 13 Mệnh đề 2.2. Với s là một số thực, s > 1, ta có 1 = s−1 Z+∞ 1 dx ≤ ζ(s) ≤ 1 + xs Z+∞ 1 1 1 dx = 1 + . xs s−1 1 π2 1 Mệnh đề 2.3. Ta có ζ(2) = = . 2 6 n=1 n Tính chất ở trên được biết là bài toán Basel. +∞ P Mệnh đề 2.4. Với mọi số nguyên s chẵn và s ≥ 2, ζ(s) là một bội hữu tỷ của π s . Mệnh đề 2.5. Cho n ∈ N. Khi đó ζ(−n) = (−1)n Bn+1 . n+1 Mệnh đề 2.6. Ta có ζ(3) là một số vô tỷ. ∞ P 1 với giá trị thực của a và s, s > 1 và s n=0 (n + a) Z∞ Z∞ s−1 −ax x e dx. Ở đây, Γ(s) = e−t ts−1 dt. 0 < a ≤ 1. Khi đó Γ(s)ζ(s, a) = −x 1−e Mệnh đề 2.7. Cho ζ(s, a) = 0 0 CHƯƠNG 3 CÁC BÀI TOÁN LIÊN QUAN ĐẾN CÁC HÀM TRONG LÝ THUYẾT SỐ Các khái niệm và kết quả trong chương này có thể tìm thấy trong các tài liệu [2], [3], [4] và [5]. 3.1 Các bài toán liên quan đến hàm Möbius Bài toán 3.1. Cho f là một hàm nhân tính và n = pa11 pa22 . . . pakk với k ∈ N, là dạng phân tích thành thừa số nguyên tố của số nguyên n. Chứng minh k P Q rằng µ(d)f (d) = (1 − f (pi )). d|n i=1 14 P Giải. Đặt g(n) = µ(d)f (d) = d|n P µ(d)f (d)u d|n n d = (µ.f ∗ u)(n). Do µ, f, u là các hàm nhân tính nên g cũng là hàm nhân tính. Với n = pa , ta có g(pa ) = 1 − f (p). Từ đó sử dụng tính chất g là hàm nhân tính để xét n = pa11 pa22 . . . pakk , suy ra điều phải chứng minh. Bài toán 3.2. Chứng minh rằng µ(n)µ(n + 1)µ(n + 2)µ(n + 3) = 0 với mọi số nguyên dương n. P Bài toán 3.3. Chứng minh rằng µ(d) = µ2 (n). d2 |n Giải. Xét các trường hợp n = 1, n = p1 p2 . . . pk và n = p1 a1 p2 a2 . . . pi ai pi+1 . . . pk với các a1 , a2 , . . . , ai ≥ 2 để suy ra điều cần chứng minh. Bài toán 3.4. Tìm một số nguyên dương n thỏa điều kiện sau µ(n) + µ(n + 1) + µ(n + 2) = 3. Bài toán 3.5. Cho n là một số nguyên lớn hơn 1. Giả sử n có phân tích thành thừa số nguyên tố là n = pa11 pa22 . . . pakk . Chứng minh rằng X µ(d)ϕ(d) = (2 − p1 )(2 − p2 ) . . . (2 − pk ). d|n Giải. Áp dụng công thức tổng - tích của µ hàm suy ra điều cần chứng minh. P 1 Bài toán 3.6. Tìm hàm f (n) thỏa mãn điều kiện f (d) = , với n là một n d|n số nguyên dương. 1 Giải. Đặt g(n) = . Áp dụng công thức ngược Möbius, ta được n X 1 n f (n) = µ . d d d|n Với n = pa , thay vào (3.1) ta được f (pa ) = 1 (1 − p). pa Với n = pa11 pa22 . . . pakk . Thay vào (3.1), ta có 1 f (pa11 pa22 . . . pakk ) = (1 − p1 )(1 − p2 ) . . . (1 − pk ). n 1Q Vậy hàm f (n) cần tìm phải có dạng f (n) = (1 − p). n p|n (3.1) 15 3.2 Các bài toán liên quan đến hàm Euler Bài toán 3.7. Chứng minh rằng số nguyên dương n là hợp số khi và chỉ khi √ ϕ(n) ≤ n − n. √ n với mọi số nguyên dương n. Bài toán 3.8. Chứng minh rằng ϕ(n) ≥ 2 Giải. Giả sử n có phân tích ra thừa số nguyên tố như sau n = 2a0 pa11 pa22 . . . pakk . Nếu a0 > 0, ta có      1 1 1 1− ... 1 − ϕ(n) = n 1 − 2 p1 pk = 2a0 −1 pa11 −1 pa22 −1 . . . pakk −1 (p1 − 1)(p2 − 1)(pk − 1). Mặt khác, với mọi số nguyên tố p ≥ 3 thì p − 1 > √ p, nên √ √ √ ϕ(n) ≥ 2a0 −1 p1a1 −1 pa22 −1 . . . pakk −1 p1 p2 . . . pk 2a0 a1 −1/2 a2 −1/2 a −1/2 p1 = p2 . . . pkk . 2 1 a Lại có a − ≥ với mọi số nguyên dương a. Nên 2 2 a /2 a /2 a /2 2a0 /2 p11 p22 . . . pkk ϕ(n) ≥ 2 p a a 2a0 p11 p22 . . . pakk = , 2 hay √ n . 2 √ √ n Nếu a0 = 0, tương tự ta cũng có ϕ(n) > n > . 2 Vậy bài toán đã được chứng minh. ϕ(n) ≥ Bài toán 3.9. Tìm số nguyên dương n thỏa điều kiện ϕ(n) chia hết n. Giải. Xét n = 1. Với n > 1, áp dụng công thức hàm Euler dạng tích, suy ra n chia hết cho 2 và n chỉ có một ước nguyên tố lẻ là 3. Thử lại và kết luận các số n cần tìm là n = 2m 3n với m ≥ 1, n ≥ 0. n Bài toán 3.10. Tìm số nguyên dương n thỏa điều kiện ϕ(n) = . 2 16 Giải. Áp dụng công thức hàm Euler dạng tích, suy ra n chỉ có một ước nguyên tố là 2. Kết luận các số n cần tìm là n = 2x với x ≥ 1. Bài toán 3.11. Tìm số nguyên dương n thỏa điều kiện ϕ(n) = ϕ(2n). Giải. Xét các trường hợp n = 1, n chia hết cho 2 và n không chia hết cho 2, suy ra n phải có dạng n = 2x + 1 với x ≥ 0. Bài toán 3.12. Tìm số nguyên dương n sao cho ϕ(n) là một lũy thừa của 2. Giải. Với n = 1 thì ϕ(1) = 1 = 20 , là một lũy thừa của 2. Xét n > 1. + Xét n = 2x với x ≥ 1. Theo công thức hàm Euler dạng tích, ta có   1 = 2x−1 , ϕ(n) = ϕ(2x ) = 2x 1 − 2 là một lũy thừa của 2. + Xét n có ước nguyên tố khác 2. Giả sử n có phân tích ra thừa số nguyên tố như sau n = pa11 pa22 . . . pakk . Theo công thức hàm Euler dạng tích, ta có      1 1 1 1− ... 1 − ϕ(n) = n 1 − p1 p2 p  k    p2 − 1 pk − 1 a1 a2 a k p1 − 1 = p1 p2 . . . pk ... p1 p2 pk = pa11 −1 pa22 −1 . . . pkak −1 (p1 − 1)(p2 − 1) . . . (pk − 1). Do ϕ(n) là một lũy thừa của 2, nên nếu pi khác 2 thì pi phải có số mũ là 1. Đặt n = 2a1 p2 p3 . . . pk , ta có ϕ(n) = 2a1 −1 (p2 − 1)(p3 − 1) . . . (pk − 1). Để ϕ(n) là một lũy thừa của 2, thì (pi − 1) phải là một lũy thừa của 2 với mọi i = 2, k . Suy ra pi − 1 = 2xi , hay pi = 2xi + 1. 17 Mặt khác, ta có 2xi + 1 là số nguyên tố khi xi = 0 hoặc xi = 2ti . Vậy n phải có k  Q t a 1 dạng n = 2 . 22 i + 1 với k ≥ 1. i=1 Vậy các số n cần tìm là n = 2x với x ≥ 0 hoặc n = k Q 2a1 .  t 22 i + 1 với i=1 k ≥ 1. Bài toán 3.13. Tìm số nguyên dương n thỏa điều kiện ϕ(n) = 12. Giải. Các giá trị của n thỏa điều kiện là 13, 21, 26, 28, 36, 42. Bài toán 3.14. Tìm số nguyên dương n thỏa điều kiện ϕ(n) chia hết cho 4. Giải. Áp dụng công thức hàm Euler dạng tích, ta có các trường hợp sau: n có dạng n = 23 .n1 với n1 > 0, hoặc n có dạng n = 22 .n2 với n2 > 1 là một số lẻ, hoặc n có ít nhất hai ước nguyên tố lẻ hoặc n có một ước nguyên tố lẻ có dạng n 22 3 + 1 với n3 ≥ 1. 3.3 Các bài toán liên quan đến τ -hàm Bài toán 3.15. Cho f là một hàm số học có f (1) = 1. Chứng minh rằng f là hàm nhân tính hoàn toàn khi và chỉ khi f ∗ f = f.τ . Giải. Điều kiện cần: Cho f là hàm nhân tính hoàn  n toàn. Chứng minh f ∗ f = f.τ . P Với n ∈ N∗ , ta có f ∗ f (n) = f (d)f . Do f là hàm nhân tính hoàn d d|n P P P  n = f (n) = f (n) 1 = f (n)τ (n). Suy ra toàn nên f ∗ f (n) = f d d d|n d|n d|n f ∗ f = f.τ . Điều kiện đủ: Cho f là hàm thỏa f (1) = 1 và f ∗ f = f.τ . Chứng minh f là hàm nhân tính hoàn toàn. Theo giả thiết, ta có f ∗ f = f.τ , nên (f ∗ f )(n) = f (n).τ (n) với mọi n ∈ N∗ . 18 Mặt khác, τ = u ∗ u, do đó n n X X f (d)f = f (n).(u ∗ u)(n) = f (n). u(d)u d d d|n d|n n X f (n)u(d)u = d d|n X f (n). = d|n Suy ra f (d)f n d = f (n) với mọi n ∈ N∗ và d|n. Như vậy, f phải là hàm nhân tính hoàn toàn. Vậy f là hàm nhân tính hoàn toàn khi và chỉ khi f ∗ f = f.τ . Bài toán 3.16. Tính tích các ước dương của một số nguyên dương n cho trước. Giải. Tích các ước dương của số nguyên dương n là P = n τ (n) 2 . Bài toán 3.17. Tìm tất cả các số nguyên dương n sao cho tích các ước dương khác n của n là n2 . k Q Giải. Áp dụng bài toán 3.16 và công thức τ (n) = (ai + 1), suy ra n phải có i=1 dạng n = p5 hoặc n = p21 p2 . Bài toán 3.18. Chứng minh rằng n X i=1 √ b nc j X n k √ 2 τ (i) = 2 − n , i i=1 với n là số nguyên dương và bkc là phần nguyên của số k . 100 P Áp dụng tính τ (i). i=1 3.4 Các bài toán liên quan đến σ-hàm suy rộng Bài toán 3.19. Chứng minh rằng nếu số nguyên dương n là số hoàn hảo, thì ta có X1 = 2. d d|n
- Xem thêm -