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 -