ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THÚY HẰNG HÀM SINH BỞI CÁC ƯỚC SỐ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN, NĂM 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THÚY HẰNG HÀM SINH BỞI CÁC ƯỚC SỐ VÀ ỨNG DỤNG Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS.TS NÔNG QUỐC CHINH THÁI NGUYÊN, NĂM 2015 i Mục lục Mục lục i Mở đầu 1 Hàm đếm ước số d(n) 1.1 Một số kiến thức số học 1.1.1 Phép chia tập số nguyên 1.1.2 Ước số chung lớn (ƯSCLN) 1.1.3 Số nguyên tố 1.2 Hàm đếm ước 2 5 Giá trị trung bình vài hàm số ước số 2.1 Giá trị trung bình vài hàm số ước số 2.1.1 Định lí Ramanujan 2.2 Số hoàn hảo số liên quan học sinh 14 học sinh 14 14 19 Một số toán áp dụng 3.1 Tổng hiệu tích cặp số 3.2 Tập bội số tập hợp cho trước 3.3 Tập số thừa 24 24 34 38 Kết luận 45 Tài liệu tham khảo 46 Mở đầu Trong toán học đặc biệt lý thuyết số, hàm sinh ước số hàm số học liên quan đến tính tốn ước số nguyên Hàm gắn với phép đếm số ước số số nguyên dạng toán liên quan đến biểu diễn ước số Các kết gắn với nghiên cứu gần nhà toán học Ấn Độ Ramanujan Luận văn nhằm mục đích tìm hiểu chi tiết tính chất hàm sinh ước số xét ứng dụng việc giải tốn liên quan số học Ngoài phần Mở đầu Kết luận, luận văn chia thành ba chương đề cập đến vấn đề sau đây: Chương trình bày ước số tính chất liên quan Chương trình bày giá trị trung bình hàm sinh ước số Chương trình bày số tốn ứng dụng số học Tơi xin bày tỏ lòng biết ơn sâu sắc Phó Giáo sư, Tiến sĩ Nơng Quốc Chinh, người thầy trực tiếp hướng dẫn, cung cấp tài liệu truyền đạt kinh nghiệm nghiên cứu cho Tôi xin chân thành cảm ơn thầy, cô giáo khoa Tốn - Tin, phịng Đào tạo trường Đại học Khoa học - Đại học Thái Nguyên, Trường THPT Hòn Gai bạn bè đồng nghiệp giúp đỡ tạo điều kiện cho tơi hồn thành luận văn Chương Hàm đếm ước số d(n) 1.1 1.1.1 Một số kiến thức số học Phép chia tập số nguyên Định nghĩa 1.1 Cho hai số nguyên a b , với b = Nếu có số nguyên q cho a = bq ta nói b chia hết a hay a chia hết cho b b ước a ký hiệu b | a hay a b Tính chất 1.1 ±1 | a với a ∈ Z a với a ∈ Z, a = a a với a ∈ Z, a = b | a a | b a = ±b b | a c | b kéo theo c | a Với i ∈ {1; 2; ; n}, ∀xi ∈ Z, b | a kéo theo b | n x j i=0 Định lý 1.1 (Định lý chia Euclid) Với số nguyên a b, b = 0, tồn số nguyên q, r cho a = bq + r; ≤ r < |b| (1.1) Chứng minh a) Sự tồn tại: Gọi M tập hợp bội số b không vượt a: M = {bx | x ∈ Z, bx ≤ a} Ta có M ⊂ Z M = ∅ chẳng hạn −|b|.|a| ∈ M M bị chặn trên, có số lớn nhất, ta gọi bq Số nguyên bq + |b| bội b bq + |b| ∈ / M , ta có bq ≤ a < bq + |b|, từ suy ≤ a − bq < |b| Đặt r = a − bq ta a = bq + r, ≤ a − bq < |b| b) Tính nhất: Giả sử có q, r q1 , r1 thỏa mãn điều kiện trên, tức a = bq + r, a = bq1 + r1 , ≤ r < |b|, ≤ r1 < |b|, Khi ta bq + r = bq1 + r1 ⇒ r − r1 ≤ b(q − q1 ) Nhưng |r − r1 | < |b|, |b||q − q1 | < |b|, nghĩa |q − q1 | < Hệ thức buộc q − q1 = nghĩa q = q1 , từ suy r = r1 (điều phải chứng minh) 1.1.2 Ước số chung lớn (ƯSCLN) Định nghĩa 1.2 Cho hai số nguyên a, b số khác Số dương d gọi ƯSCLN a, b ký hiệu d := (a, b) d | a d | b ( d ước số chung a b) Nếu c | a c | b c | d Nói cách khác, d ƯSCLN hai số a b d ước chung a b đồng thời d số lớn ước số chung a b Nếu (a, b) = ta nói hai số a b nguyên tố Nhận xét 1.1 Trong trường hợp a, b có số hiển nhiên ƯSCLN chúng số Tính chất 1.2 (ac, bc) = (a, b).c với c = a b (a, b) ; = với c ước chung a,b c c c Nếu (a, b) = (ac, b) = (c, b) Nếu (a, b) = b ac b c (b, a1 ) = (b, a2 ) = ⇒ (b, a1 a2 ) = Nếu a c1 , a c2 mà (c1 , c2 ) = a c1 c2 Thuật tốn tìm ƯSCLN hai số nguyên Chú ý 1.1 Nếu số nguyên a, b, q, r có hệ thức a = bq + r ta có (a, b) = (b, r) a) Cho a, b ∈ Z Nếu hai số ước số kia, chẳng hạn b | a hiển nhiên b) Nếu khơng xảy trường hợp ta có hệ thức sau biểu thị dãy phép chia có dư: a = bq0 + r1 , < r1 < |b| b = r1 q1 , < r2 < r1 r1 = r2 q2 + r3 , < r3 < r2 rn−2 = rn−1 qn−1 + rn , < rn < rn−1 rn−1 = rn qn Dãy phép chia có dư liên tiếp gọi thuật toán Euclid thực hai số a, b Dãy phải dãy hữu hạn thuật toán Euclid phải kết thúc với số dư rn+1 = Theo ý ta có (a, b) = (b, r1 ) = = (rn−1 , rn ) = rn Như vậy, ƯSCLN hai số a, b số dư cuối khác thuật toán Euclid thực hai số a, b 1.1.3 Số nguyên tố Định nghĩa 1.3 Số nguyên tố số tự nhiên lớn khơng có ước khác ngồi Định lý 1.2 Ước nhỏ khác số tự nhiên lớn số nguyên tố Định lý 1.3 Cho a số tự nhiên p số nguyên tố, a nguyên tố với p, a chia hết cho p Định lý 1.4 Nếu số nguyên tố p ước tích nhiều số phải ước thừa số Định lý 1.5 Nếu số nguyên tố p ước tích nhiều số ngun tố p phải trùng với số nguyên tố Định lý 1.6 (Về phân tích tắc số tự nhiên) Mọi số tự nhiên lớn phân tích thành tích thừa số nguyên tố phân tích (khơng kể thứ tự thừa số) Chú ý 1.2 Nói chung, thừa số ngun tố phân tích lặp lại, gọn, thừa số lặp lại viết dạng lũy thừa: a = pα1 pα2 pαk k (1.2) Trong pi = pj , ∀i = j, cịn αi ∈ N, αi ≥ 1, ≤ i ≤ k Và (1.2) gọi phân tích tiêu chuẩn số tự nhiên a 1.2 Hàm đếm ước Định nghĩa 1.4 Hàm số học hàm số có miền xác định tập số nguyên dương miền giá trị tập số phức Ví dụ 1.1 a) Hàm d(n) đếm ước khác số tự nhiên n ≥ hàm số học b) Hàm phi-Euler ϕ(n) hàm số học n = c) Hàm δ : Z+ → C, δ(n) = hàm số học n ≥ d) Hàm O : Z+ → C, O(n) = hàm số học Định nghĩa 1.5 Một hàm số học f gọi hàm nhân tính với cặp số m, n nguyên tố nhau, ta có f (n.m) = f (n).f (m) Trong trường hợp đẳng thức với m, n (không thiết nguyên tố nhau) hàm f gọi hàm nhân tính mạnh Ví dụ 1.2 Ta có µ(1) = 1, µ(8) = 0, µ(6) = 1, µ(4) = 0, µ(2) = −1, µ(7) = −1, µ(5) = −1, µ(9) = 0, µ(3) = −1 µ(10) = Định nghĩa 1.6 Hàm số học xác định số ước dương số nguyên dương n gọi hàm đếm ước kí hiệu d(n) Như d(1) = d(6) = 4, d(2) = d(7) = 2, d(3) = d(8) = 4, d(4) = d(9) = Giả sử pνp (n) n= p|n Mọi ước n có dạng: pap , d= p|n với ap số nguyên thỏa mãn: ≤ ap ≤ νp (n) Vì số mũ ap nhận vp (n) + giá trịn khác nên ta có (νp (n) + 1) d(n) = p|n Định lý 1.7 Hàm d(n) hàm nhân tính Chứng minh Cho m n hai số nguyên tố nhau, pνp (m), m= p|m q νq (n) n= q|n Vì (m, n) = nên tập hợp số nguyên tố ước m tập hợp số nguyên tố ước n rời Vì pνp (m) mn = p|m q νq (n) q|n phân tích thành nhân tử mn, d(mn) = (νp (m) + 1) p|m (νq (n) + 1) = d(m)d(n) q|n Vậy định lý chứng minh Ví dụ 1.3 Tính d(n) với 11 ≤ n ≤ 20 Lời giải d(11) = d(111 ) = + = d(12) = d(22 31 ) = (2 + 1)(1 + 1) = d(13) = d(131 ) = + = d(14) = d(21 71 ) = (1 + 1)(1 + 1) = d(15) = d(31 31 ) = (1 + 1)(1 + 1) = d(16) = d(24 ) = + = 32 = r|l αγ≤n/2r2 ,(α,γ)=1   +O αγ 1 ac≤n/2  = n r|l = = 3n π2 π2 1 n log r π2 2r2 r|l r|l n log r 2r n log r 2r 2 + O log   n +O 2r d(k) k≤n/2 + O(nσ−1 (n) log n) + O(x log x) + O(σ(n) log n) nσ−1 (n) log2 n + O nσ−1 (n) log2 n + O (σ(n) log(n)) π = nσ(n) log2 n + O(nσ(n) log2 n) π = Tiếp theo ta tính R, với R số nghiệm phương trình (3.8) xảy đồng thời ac ≤ x bd ≤ x Cố định số nguyên dương a c, ta kí hiệu ψ(a, c, l) số cặp thứ tự (b, d) số nguyên dương thỏa mãn ab − cd = l 0 Giả sử ε > chọn K1 = K1 (ε) thỏa mãn ∞ k=K1 < ε, a k +1 ∞ ∞ B(x) B(x) 0≤ − = x x k=1 k=K ∞ Bk (x) ≤ x +1 k=K 1 < ε a k +1 Khi tập Bk có mật độ tiệm cận, nghĩa tồn số Bk (x) ≥ thỏa mãn Bk (x) d(Bk ) = lim = βk x→∞ x Hơn nữa, β1 = d(B1 ) = 1/a1 > Với số nguyên dương l, mật độ tập hợp số nguyên chia hết cho số số nguyên a1 , a2 , , al β1 + β2 + · · · + βl , l βk ≤ 0< k=1 Do đó, chuỗi l βk , k=1 hội tụ tới giá trị β > Ta chứng minh tập bội số M (A) có mật độ β, nghĩa Bk (x) lim = β x→∞ x 38 Với ε > tồn số nguyên K2 = K2 (ε) thỏa mãn ∞ βk < ε k=K2 +1 Giả sử K = max{K1 , K2 } ta cần chọn số x0 = x0 (ε) thỏa mãn ε Bk (x) − βk < , x k với x ≥ x0 k = 1, , K Khi ∞ B(x) −β x = k=1 K < k=1 K ≤ k=1 Bk (x) − βk x K Bk (x) − βk + 2ε x k=1 Bk (x) − βk + 2ε x < 3ε Vậy định lí chứng minh xong Định lý 3.5 Nếu A tập vô hạn số nguyên với hàm đếm A(x) = O x , log2 x với x ≤ 2, tập hợp bội số M (A) có mật độ tiệm cận Chứng minh Ta có chuỗi vơ hạn a−1 hội tụ Theo định lí (3.4) tập bội số M (A) a∈A tập có mật độ tiệm cận 3.3 Tập số thừa Trong phần ta nghiên cứu số hoàn hảo số thừa, đơn giản ta gọi chung cho chúng tên số thừa Như số nguyên dương n thừa σ(n) ≥ 2n 39 Nhận xét 3.1 Nếu n số thừa bội số n số thừa Thực vậy, ta có σ(n) ≥ 2n Giả sử a = tn bội n Do σ hàm nhân tính nên ta có σ(a) = σ(t)σ(n) ≥ (t + 1)(2n) ≥ 2tn = 2a Vậy a số thừa Định nghĩa 3.4 Số nguyên dương n gọi số thừa nguyên thủy n số thừa (nghĩa σ(n) ≥ 2n), n khơng có ước thực số thừa (nghĩa với d|n, < d < n, ta có σ(d) < 2d) Nhận xét 3.2 Tập hợp tất số thừa chứa tất bội số số thừa nguyên thủy Thật vậy, n số thừa nguyên thủy, hiển nhiên bội số n số thừa Dưới ta chứng minh tập hợp tất số thừa có mật độ tiệm cận Định nghĩa 3.5 - Số nguyên dương n gọi số k - thừa σ(n) ≥ kn Ta kí hiệu Ak tập tất số nguyên số k- thừa - Số nguyên dương n gọi số k - thừa nguyên thủy σ(n) ≥ kn σ(d) < kd với ước thực d n Ta kí hiệu P Ak tập tất số k - thừa nguyên thủy Nhận xét 3.3 Ta có Ak = M (P Ak ), nghĩa tập Ak tập bội số tập P Ak (hiển nhiên) Bổ đề 3.4 Số lượng số nguyên dương n ≤ x mà ước số nguyên pr ≥ log4 x với r ≥ O(x log−2 x) Chứng minh Nếu p số nguyên tố thỏa mãn p ≥ log2 x p2 chia hết n n chia hết cho lũy thừa số nguyên tố pr ≥ log4 x với r ≥ Số số nguyên n ≤ x x/p2 Nếu p < log2 x, cho up số nguyên bé thỏa mãn pup ≥ log4 x Số 40 số nguyên n ≤ x chia hết cho lũy thừa số nguyên tố pr ≥ log4 x [x/pup ] Cho N1 (x) kí hiệu cho số nguyên n ≤ x chia hết cho lũy thừa số nguyên pr ≥ log4 x Thì N1 (x) ≤ p≥log2 x ≤ x p≥log2 x ≤ x p≥log2 x x + p2 p 1, a < n Từ a ước thực số nguyên thủy k – thừa n, ta có σ(a) < ka Từ k số ngun ta có σ(a) ≤ ka − Vì 20y σ(a) ≤k− x1/(96y) Từ p2 > x1/(3y) > log4 x với x đủ lớn, điều kiện (i) suy p2 không ước n Vì n = mp với (m, p) = σ(m) < km từ n số nguyên thủy k – thừa Ta suy σ(n) σ(m) σ(p) =