Luận văn Thạc sĩ Toán học: Tính chất số học của dãy các số nguyên

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

Thêm vào BST

Báo xấu

49
lượt xem 3
download

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

Trong các kì thi học sinh giỏi toán các cấp, các bài toán liên quan tới các tính chất số học của dãy các số nguyên thường xuyên được đề cập. Những dạng toán này thường được xem là thuộc loại khó vì phần kiến thức về chuyên đề này không nằm trong chương trình chính thức của giáo trình số học bậc trung học phổ thông. Chuyên đề nằm trong chương trình bồi dưỡng HSG ở các lớp THCS phục vụ các kỳ thi HSG quốc gia và khu vực. Để đáp ứng nhu cầu bồi dưỡng giáo viên và bồi dưỡng học sinh giỏi về chuyên đề về dãy các số nguyên, tác giả chọn đề tài luận văn ”Tính chất số học của dãy các số nguyên”.

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: Tính chất số học của dãy các số nguyên

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- BÙI THU NGA TÍNH CHẤT SỐ HỌC CỦA DÃY CÁC SỐ NGUYÊN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- BÙI THU NGA TÍNH CHẤT SỐ HỌC CỦA DÃY CÁC SỐ NGUYÊN Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. Nguyễn Văn Mậu THÁI NGUYÊN - 2019
LỜI CẢM ƠN Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên. Tác giả xin bày tỏ lòng biết ơn sâu sắc đối với GS.TSKH Nguyễn Văn Mậu (Trường ĐH Khoa học Tự nhiên, ĐHQGHN), thầy đã trực tiếp hướng dẫn tận tình và động viên tác giả trong suốt thời gian nghiên cứu vừa qua. Xin chân thành cảm ơn tới các quý thầy, cô giáo đã trực tiếp giảng dạy lớp cao học Toán K11, các bạn học viên, và các bạn đồng nghiệp đã tạo điều kiện thuận lợi, động viên giúp đỡ tác giả trong quá trình học tập và nghiên cứu tại trường. Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân luôn khuyến khích động viên tác giả trong suốt quá trình học cao học và viết luận văn này. Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp của các thầy cô và các bạn đọc để luận văn được hoàn thiện hơn. Xin chân thành cảm ơn! Thái Nguyên, tháng 10 năm 2019 Tác giả Bùi Thu Nga ii
Mục lục MỞ ĐẦU 1 Chương 1. MỘT SỐ TÍNH CHẤT SỐ HỌC CỦA DÃY SỐ NGUYÊN 2 1.1 Lớp các hàm số học cổ điển và các dãy số liên quan . . . . . . . . . 2 1.1.1 Phi hàm Euler . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Hàm tổng các ước . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Hàm số M¨obius . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.4 Hàm đếm các ước số . . . . . . . . . . . . . . . . . . . . . . 12 1.1.5 Một số đẳng thức giữa các hàm số học . . . . . . . . . . . . 14 1.2 Một số dạng toán số học về dãy số nguyên . . . . . . . . . . . . . . 18 1.2.1 Các dạng toán về số chính phương trong dãy số . . . . . . . 18 1.2.2 Các dạng toán về tính chia hết và đồng dư trong dãy số . . 32 1.3 Một số dạng toán về dãy số nguyên qua các kỳ Olympic . . . . . . 34 1.3.1 Một số dạng toán về số chính phương trong dãy số . . . . . 34 1.3.2 Đồng dư và chia hết trong dãy số . . . . . . . . . . . . . . . 46 Chương 2. CÁC DÃY SỐ LIÊN QUAN ĐẾN ĐA THỨC NGUYÊN VÀ PHƯƠNG TRÌNH ĐA THỨC 59 2.1 Sử dụng đa thức nguyên giải bài toán đồng dư trong dãy số . . . . 59 2.2 Thiết lập phương trình để khảo sát tính chất số học của dãy số . . 73 KẾT LUẬN 80 TÀI LIỆU THAM KHẢO 81 iii
Mở đầu Trong các kì thi học sinh giỏi toán các cấp, các bài toán liên quan tới các tính chất số học của dãy các số nguyên thường xuyên được đề cập. Những dạng toán này thường được xem là thuộc loại khó vì phần kiến thức về chuyên đề này không nằm trong chương trình chính thức của giáo trình số học bậc trung học phổ thông. Chuyên đề nằm trong chương trình bồi dưỡng HSG ở các lớp THCS phục vụ các kỳ thi HSG quốc gia và khu vực. Để đáp ứng nhu cầu bồi dưỡng giáo viên và bồi dưỡng học sinh giỏi về chuyên đề về dãy các số nguyên, tôi chọn đề tài luận văn ”Tính chất số học của dãy các số nguyên”. Tiếp theo, khảo sát một số lớp bài toán từ các đề thi HSG Quốc gia và các tỉnh thành trong cả nước những năm gần đây. Cấu trúc luận văn gồm 2 chương: Chương 1. Một số tính chất số học của dãy số nguyên. Chương 2. Các dãy số liên quan đến đa thức nguyên và phương trình đa thức. Tiếp theo, cuối các chương đều trình bày các bài tập áp dụng và giải các đề thi HSG quốc gia và Olympic liên quan. 1
Chương 1. MỘT SỐ TÍNH CHẤT SỐ HỌC CỦA DÃY SỐ NGUYÊN Trong lý thuyết số, các hàm số học có vai trò hết sức quan trọng. Trong chương này, ta xét một số hàm số học cổ điển (Phi hàm Euler, hàm M˝obuis, hàm đếm các ước và hàm tổng) và xét các tính chất số học của dãy sinh bởi chúng. Ta chủ yếu khảo sát lớp hàm số học nhận giá trị nguyên. Những trường hợp đặc biệt sẽ được xét riêng và có chú giải chi tiết. Phần lý thuyết trong phần này được lựa chọn từ các tài liệu [1]-[4]. 1.1 Lớp các hàm số học cổ điển và các dãy số liên quan Định nghĩa 1.1 (xem [1],[4]). Hàm số học là hàm số có miền xác định là tập các số nguyên dương và miền giá trị là tập các số thực hoặc phức. Định nghĩa 1.2 (Hàm nhân tính). Một hàm số học f được gọi là hàm nhân tính nếu với mỗi cặp số m, n nguyên tố cùng nhau, ta có f (nm) = f (n)f (m). Trong trường hợp đẳng thức đúng với mọi m, n nguyên dương (không nhất thiết nguyên tố cùng nhau) hàm f gọi là hàm nhân tính mạnh. Định lý 1.1 (Tính chất của hàm nhân tính). Nếu f là hàm nhân tính thì f ([m, n])f ((m, n)) = f (m)f (n) với mọi số nguyên dương m và n. Chứng minh. Cho p1 , p2 , . . . , pr là các số nguyên tố chia hết m hoặc n. Khi đó r Y n= pki i i=1 và r Y m= plii i=1 với k1 , . . . , kr , l1 , . . . , lr là các số nguyên không âm. 2
Suy ra r max(ki ,li ) Y [m, n] = pi i=1 và r min(ki ,li ) Y (m, n) = pi . i=1 Do {max(ki , li ), min(ki , li )} = {ki , li } và vì f là hàm nhân tính, ta thu được r r max(ki ,li ) min(ki ,li ) Y Y f ([m, n])f ((m, n)) = f (pi ) f (pi ) i=1 i=1 Yr r Y = f (pki i ) f (plii ) i=1 i=1 = f (m)f (n). Vậy, ta thu được điều phải chứng minh. Hệ quả 1.1. Xét dãy số {un } với un = f (n), trong đó f là hàm số học nhân tính. Khi đó, nếu n là hợp số và có dạng chính tắc m Y n= pαk k k=1 thì m Y un = f (pαk k ). k=1 Vì vậy, về sau, ta quan tâm nhiều đến số nguyên tố và dãy các số nguyên tố. Định nghĩa 1.3. Dãy các số nguyên tố là dãy P = {2, 3, 5, 7, 11, 13, 17, 19, 23, . . . , pk , . . . } với pk là các số nguyên tố. Ngoài dãy các số nguyên tố, còn có các dãy tạo bởi các lũy thừa của các số nguyên tố. P Tính chất 1.1. Nếu f là một hàm nhân tính thì hàm F (n) = f (d) cũng là d|n hàm nhân tính. 3
Chứng minh. Ta sẽ chỉ ra rằng, nếu m, n là các số nguyên dương và (m, n) = 1 thì F (m.n) = F (m)F (n). Giả sử (m, n) = 1, ta có X F (mn) = f (d). d|mn Vì (m, n) = 1, mỗi ước của số mn có thể viết duy nhất dưới dạng tích các ước d1 của m, d2 của n và d1 , d2 nguyên tố cùng nhau, đồng thời mỗi cặp ước nguyên tố d1 của m, d2 của n tương ứng với d = d1 d2 của mn. Do đó, ta có thể viết X F (mn) = f (d1 d2 ). d1 |m d2 |n Vì f là hàm có tính chất nhân tính và (d1 , d2 ) = 1, nên X X X F (mn) = f (d1 )f (d2 ) = f (d1 ) f (d2 ) = F (m)F (n). d1 |m d1 |m d2 |n d2 |n 1.1.1 Phi hàm Euler Tiếp theo, ta xét một số hàm số học cơ bản. Định nghĩa 1.4 (Phi hàm Euler ϕ(n)). Cho số tự nhiên n ≥ 1. Ta ký hiệu ϕ(n) là số các số tự nhiên bé hơn n và nguyên tố cùng nhau với n. Quy ước ϕ(1) = 1. Định lý 1.2 (xem [4]). Hàm ϕ(n) là hàm nhân tính. Chứng minh. Ta có thể giả thiết a > 1, b > 1. Các số nguyên dương không vượt quá ab được liệt kê như sau: 1 2 a a+1 a+2 . . . . . . . . . 2a 2a + 1 2a + 2 3a ka + 1 ka + 2 . . . . . . . . . (k + 1)a (b − 1)a + 1 (b − 1)a + 2 ba Các số đó sắp thành bảng có dạng ax + y , trong đó 0 ≤ x ≤ b − 1, 1 ≤ y ≤ a. Xét các số ở cột thứ y . Ta có (ax + y, a) = (y, a). Vì một số nguyên tố với ab khi và chỉ khi nó nguyên tố với a và b, do đó các số này phải nằm ở cột thứ y mà (y, a) = 1. Có cả thẩy ϕ(a) cột như vậy. Xét một cột thứ y , với (y, a) = 1. Các số ở trong cột này là y, a + y, 2a + y, . . . , (b − 1)a + y. 4
Giả sử rx là số dư khi chia ax + y cho b. Như vậy (ax + y, b) = (rx , b). Dễ dàng thấy rằng vì (a, b) = 1 nên rx1 6= rx2 với x1 6= x2 . Như vậy ta có đẳng thức tập hợp r0 , r1 , . . . , rb−1 = 0, 1, . . . , b − 1. Vậy số các x mà (ax + y, b) = 1 chính là số các x mà (rx , b) = 1 tức chính là ϕ(b). Vậy cả thẩy có ϕ(a)ϕ(b) số nguyên tố với a và nguyên tố với b. Đó chính là các số nguyên tố với ab. Nói cách khác ϕ(ab) = ϕ(a)ϕ(b). Từ định lý này ta suy ra công thức tính ϕ(n) như sau. Định lý 1.3 (xem [20, 30 - 33]). Giả sử n = pα1 1 . . . pαk k là phân tích chính tắc của n > 1. Khi đó 1 1 1 ϕ(n) = n 1 − 1− ... 1 − . p1 p2 pk Chứng minh. Theo Định lý 1.2, ta có ϕ(n) = ϕ(pα1 1 ) . . . ϕ(pαk k ). Định lý sẽ được chứng minh nếu ta chứng tỏ rằng ứng với p là một số nguyên 1 tố thì ϕ(pα ) = pα (1 − ). Thật vậy, vì p là nguyên tố nên với mỗi k ≤ pα thì p .. (k, p) = 1 hoặc k . p. h pα i α Số các số k ≤ p và là bội của p là = pα−1 . p Vậy 1 ϕ(pα ) = pα − pα−1 = pα (1 − ). p Bài toán 1.1. Tính ϕ(360). Lời giải. Với n = 360 = 23 .32 .5 thì 1 1 1 ϕ(360) = 360 1 − 1− 1− = 96. 2 3 5 Bài toán 1.2. Cho n là một số nguyên dương. Chứng minh rằng X ϕ(d) = n. d|n Lời giải. Tổng trên đây được lấy theo các ước số của n. Ta phân chia tập hợp các số tự nhiên từ 1 đến n thành các lớp theo cách sau đây. Lớp Cd gồm các số nguyên m, 1 ≤ m < n, mà (m, n) = d. Như vậy m thuộc Cd nếu và chỉ nếu d là ước chung của m, n và (m|d, n|d) = 1. Như vậy, số phần tử của Cd là số các số nguyên dương không vượt quá n|d và nguyên tố cùng nhau 5
với n|d; tức là Cd gồm ϕ(n|d) phần tử. Vì mỗi số nguyên m từ 1 đến n thuộc và chỉ một lớp Cd nào đó (d = (m, n)) nên n bằng tổng của số các thành phần trong các lớp Cd , d là ước của n. Ta có X n n= ϕ . d d|n Mặt khác, khi d chạy qua mọi ước của n thì n|d cũng chạy qua mọi ước của n, nên từ đó suy ra X n= ϕ(d). d|n Nhận xét 1.1. Tầm quan trọng của hàm ϕ(n) trong số học được thể hiện trong Định lý Euler. Sau đây là một dạng mở rộng của Định lý Euler. Định lý 1.4 (Định lý Euler mở rộng). Cho a và m là hai số tự nhiên. Khi đó am ≡ am−ϕ(m) (mod m). Chứng minh. Ta phải chứng minh A = am − am−ϕ(m) = am−ϕ(m) (aϕ(m) − 1) chia hết cho m. Giả sử m có phân tích chính tắc là m = q1α1 q2α2 . . . qkαk . . . Ta sẽ chứng minh rằng nếu (a, qi ) = 1 thì (aϕ(m) − 1) .. q αi , còn nếu a .. q thì . . am−ϕ(m) ..q αi , và như vậy A .. m. Thật vậy, nếu (a, qi ) = 1 thì theo Định lý Euler αi . (aϕ(qi ) − 1) .. qiαi . Mặt khác, 1 ϕ(qiαi ) = qiαi (1 − ). qi là ước của ϕ(m) (suy ra từ công thức tính ϕ(m)). Do đó . αi . (aϕ(m) − 1)..(aϕ(qi ) − 1) .. q αi . . Nếu a .. qi thì . am−ϕ(m) .. q m−ϕ(m) . 6
Mặt khác, rõ ràng m − ϕ(m) ≥ αi (vì có ít nhất αi số không nguyên tố với m là q1α1 q2α2 . . . qiαi ). Do đó . . am−ϕ(m) .. q m−ϕ(m) .. qiαi . Định lý được chứng minh. Định lý 1.5 (Định lý Fermat). Cho p là một số nguyên tố và a là một số nguyên không chia hết cho p. Khi đó, ta có ap−1 ≡ 1 (mod p). Chứng minh. Theo giả thiết, ta có ϕ(p) = p − 1 và a là nguyên tố với p nên theo Định lý Euler, ta thu được ap−1 ≡ 1 (mod p). Định lý 1.6 (Định lý Fermat dạng khác). Cho p là một số nguyên tố và a là một số nguyên tùy ý khi ấy ta có ap ≡ a (mod p). Chứng minh. Nếu a chia hết cho p thì hiển nhiên ap ≡ a (mod p). Nếu a không chia hết cho p thì theo Định lý 1.5, ta có ap−1 ≡ 1 (mod p) cho nên sau khi nhân hai vế của đồng dư thức này với a, ta thu được ap ≡ a (mod p). Nhận xét 1.2. Ngược lại, từ Định lý 1.6 ta có thể suy ra Định lý 1.5. Thật vậy, từ ap ≡ a (mod p) và a là một số nguyên không chia hết cho số nguyên tố p thế thì a nguyên tố với p nên bằng cách chia cho a, ta thu được ap−1 ≡ 1 (mod p). Chính vì vậy, người ta nói Định lý 1.6 là dạng khác của Định lý Fermat. Bài toán 1.3. Tìm các số nguyên x để 9x + 5 là tích của hai số nguyên liên tiếp. Lời giải. Giả sử 9x + 5 = n(n + 1) với n ∈ Z, suy ra 36x + 20 = 4n2 + 4n. Suy ra 36x + 21 = (2n + 1)2 hay 3(12x + 7) = (2n + 1)2 . Số chính phương (2n + 1)2 chia hết cho 3 nên nó cũng chia hết cho 9. Mặt khác (12x + 7) không chia hết cho 3 nên 3(12x + 7) không chia hết cho 9. Mâu thuẫn trên chứng tỏ không tồn tại số nguyên x nào để 9x + 5 = n(n + 1). 7
1.1.2 Hàm tổng các ước Tiếp theo, ta xét hàm tổng các ước của một số tự nhiên. Định nghĩa 1.5 (xem [4]). Cho số nguyên dương n. Ta ký hiệu σ(n) là tổng các ước nguyên dương của n. σ(1) = 1 σ(6) = 1 + 2 + 3 + 6 = 12 σ(2) = 1 + 2 = 3 σ(7) = 1 + 7 = 8 σ(3) = 1 + 3 = 4 σ(8) = 1 + 2 + 4 + 8 = 15 σ(4) = 1 + 2 + 4 = 7 σ(9) = 1 + 3 + 9 = 13 σ(5) = 1 + 5 = 6 σ(10) = 1 + 2 + 5 + 10 = 18. Nếu n ≥ 2 thì σ(n) ≥ n + 1. Ta có thể sử dụng phép phân tích thành nhân tử của n để tính σ(n). Bài toán 1.4. Tính σ(180). Lời giải. Ta có 180 = 22 32 5. Mọi ước d của 180 có dạng d = 2a 3b 5c , với 0 ≤ a ≤ 2, 0 ≤ b ≤ 2 và o ≤ c ≤ 1. Ta có X σ(180) = d d|180 = 1 + 2 + 4 + 5 + 6 + 9 + 10 + 12 + 15 + 18 + 20 + 30 + 36 + 45 + 60 + 90 + 180 = (1 + 2 + 3)(1 + 3 + 9)(1 + 5) = 546. Nhận xét 1.3. Ta có thể tính σ(n) theo cách trên với mọi số nguyên dương n. Nếu d là ước của n thì d có thể viết dưới dạng Y d= pap , p|n với 0 ≤ ap ≤ νp (n). Khi đó, ta có X Y νX p (n) σ(n) = d= pa p d|n p|n ap =o Y pνp (n)+1 − 1 = . p−1 p|n 8
Đây chính là công thức biểu diễn σ(n) của n. Bài toán 1.5. Tính σ(20). Lời giải. Ta có 2 123 − 1 52 − 1 σ(20) = σ(2 .5 ) = . = 48. 1 4 Định lý 1.7 (xem [1],[4]). Hàm số học σ(n) là hàm nhân tính. Chứng minh. Giả sử m và n là hai số nguyên tố cùng nhau. Do không có số nguyên tố nào là ước của cả m và n, ta có Y pνp (mn)+1 − 1 σ(mn) = p−1 p|mn Y pνp (m)+1 − 1 Y pνp (n)+1 − 1 = = σ(m)σ(n). p−1 p−1 p|m p|n Vậy định lý được chứng minh. Định lý 1.8 (xem [1],[4]). a) n là số nguyên tố khi và chỉ khi σ(n) = n + 1. n b) σ(n) là một số lẻ nếu và chỉ nếu n là số chính phương hoặc là số chính phương. 2 Chứng minh. a) Nếu n là số nguyên tố thì σ(n) = n + 1. Ngược lại, nếu σ(n) = n + 1 và n là hợp số thì n có ước là 1, a và n với (1 < a < n). Vậy σ(n) ≥ n + 1 + a > n + 1. Nếu n = 1 thì σ(n) = 1 < n + 1. b) Nếu n = m2 hoặc n = 2m2 thì n = 2α pα1 1 pα2 2 . . . pαk k , ở đó p1 , p2 , . . . , pk là các số nguyên tố lẻ còn αi là chẵn. Khi đó σ(n) = σ(2α )σ(pα1 1 )σ(pα2 2 ) . . . σ(pαk k ). Ta có σ(2α ) = 2α+1 − 1 là số lẻ, σ(pαi i ) = 1 + pi + · · · + pαi i là một số lẻ vì là tổng của một số lẻ là các số lẻ. Vậy σ(n) lẻ. Ngược lại, giả sử σ(n) lẻ, và giả sử n = 2α pα1 1 pα2 2 . . . pαk k . Khi đó với mỗi i, thì σ(pαi i ) là số lẻ. Mặt khác σ(pαi i ) = 1 + pi + · · · + pαi i ≡ α1 + 1 (mod 2), nên αi là chẵn. Do đó, n nếu α chẵn thì n là số chính phương. Nếu α lẻ thì là một số chính phương. 2 9
Bài toán 1.6. Tìm tất cả các số tự nhiên n có tính chất n chia hết cho ϕ(n), trong đó ϕ là phi hàm Euler. Lời giải. Hiển nhiên, nếu n = 1 thì ϕ(n)|n. Ta xét n > 1. Giả sử n có khai triển chính tắc dưới dạng n = pk11 . . . pki i . Ta có 1 1 ϕ(n) = n 1 − ... 1 − . p1 pi Từ điều kiện ϕ(n)|n, chẳng hạn n = xϕ(n), suy ra p1 . . . pi = x (p1 − 1) . . . (pi − 1) . Như vậy, phải có pi nào đó bằng 2 (nếu ngược lại thì vô lí, vì vế trái là số lẻ, vế phải là số chẵn). Giả sử p1 = 2, ta có 2p2 . . . pi = x (p2 − 1) . . . (pi − 1) . Do p2 , . . . , pi khác 2, nên từ đẳng thức trên, suy ra rằng n có nhiều nhất là một ước nguyên tố lẻ, chẳng hạn p2 . Đặt p2 = 2y + 1. Ta có 2p2 = x(2y). Do p2 nguyên tố, nên suy ra x = p2 , y = 1. Vậy p2 = 3 và n có dạng n = 2k 3m , k ≥ 1, m ≥ 0. Dễ dàng thử lại rằng, các số n nói trên thỏa mãn điều kiện ϕ(n)|n. 1.1.3 Hàm số M¨ obius Định nghĩa 1.6. Hàm số M¨obius được định nghĩa như sau:  1 nếu n = 1 µ(n) = (−1)k nếu n là tích của k số nguyên tố phân biệt 0 nếu n chia hết cho bình phương của một số nguyên tố.  10
Định nghĩa 1.7 (xem [1],[4]). Một số nguyên được gọi là số không chính phương nếu nó không chia hết cho bình phương của một số nguyên tố. Như vậy µ(n) 6= 0 nếu và chỉ nếu n là số không chính phương. Ví dụ 1.1. Ta có µ(1) = 1, µ(6) = 1, µ(2) = −1, µ(7) = −1, µ(3) = −1, µ(8) = 0, µ(4) = 0, µ(9) = 0, µ(5) = −1, µ(10) = 1. Định lý 1.9. Hàm số M¨obius µ(n) là hàm nhân tính, và X 1 nếu n = 1, µ(d) = (1.1) 0 nếu n > 1. d|n Chứng minh. Tính nhân tính được suy ra trực tiếp từ định nghĩa của hàm M¨obius. Nếu m, n là hai số nguyên tố cùng nhau có k và l ước là các số chính phương thì mn có k + l ước là các số chính phương, và µ(n)µ(n) = (−1)k (−1)l = (−1)k+l = µ(mn). Tiếp theo, ta chứng minh công thức (1.1). Nếu n = 1, thì X µ(d) = µ(1) = 1. d|n Nếu n ≥ 2, cho n = pr11 . . . prkk là khai triển chính tắc (thành thừa số nguyên tố) của số nguyên n thì r ≤ 1. Định nghĩa 1.8. Ta gọi căn của n là ước không chính phương lớn nhất của n, nghĩa là rad (n) = p1 p2 . . . pr là tích của tất cả các thừa số nguyên tố khác nhau là ước của n. Giả sử m = rad (n). Nếu d chia hết n và µ(d) 6= 0 thì d là số không chính phương và vì vậy d chia hết m. k Do m là tích của k số nguyên tố, ta suy ra rằng có đúng i ước của m có tố i khác nhau, nghĩa là số các ước d của thể được viết như là tích của i số nguyên k m thỏa mãn điều kiện ω(d) = i là i . 11
Vì vậy X X k X X µ(d) = µ(d) = µ(d) d|n d|m i=0 d|m ω(d)=i k k k X X X i i = (−1) = i (−1) i=0 d|m ω(d)=i i=1 k = (1 − 1) = 0. Ta có điều phải chứng minh. Định lý 1.10 (Định lý M¨obius). Giả sử f là hàm nhân tính với f (1) = 1 thì X Y µ(d)f (d) = (1 − f (p)). d|n p|n Chứng minh. Ta thấy định lý đúng với n = 1. Với n ≥ 2, giả sử m = rad (n) là tích của các số nguyên tố khác nhau chia hết n. Do µ(d) = 0 nếu d là số không chính phương, ta thu được X X Y Y µ(d)f (d) = µ(d)f (d) = (1 − f (p)) = (1 − f (p)). d|n d|m p|m p|n Định lý được chứng minh xong. Tiếp theo, ta định nghĩa hàm số học (hàm đơn vi) 1(n) = 1 với mọi n ∈ N. Sử dụng tích chập Dirichlet, ta có µ∗1=δ và vì vậy hàm M¨obius là khả nghịch với nghịch đảo của 1. 1.1.4 Hàm đếm các ước số Trong toán học và đặc biệt là trong lý thuyết số, hàm sinh bởi các ước số là một hàm số học liên quan đến tính toán các ước số của một số nguyên dương. Hàm này gắn với phép đếm số các ước số của một số nguyên và các dạng toán liên quan đến biểu diễn các ước số của một số nguyên dương cho trước. Các kết quả này gắn với các nghiên cứu gần đây của nhà toán học Ấn Độ Ramanujan. Định nghĩa 1.9 (xem [1],[4], [6]). Hàm số học xác định số các ước dương của một số nguyên dương n được gọi là hàm đếm các ước và kí hiệu là d(n). 12
Như vậy, d(1) = 1, d(6) = 4, d(2) = 2, d(7) = 2, d(3) = 2, d(8) = 4, d(4) = 3, d(9) = 3. Nhận xét rằng khi n có dạng Y n= pνp (n) , p|n thì mọi ước của n có dạng Y d= pap , p|n trong đó ap là số nguyên thỏa mãn điều kiện 0 ≤ ap ≤ νp (n). Vì mỗi số mũ ap có thể nhận vp (n) + 1 giá trị khác nhau, nên ta có đẳng thức Y d(n) = (νp (n) + 1). p|n Định lý 1.11 (xem [4-6]). Hàm d(n) là một hàm nhân tính. Chứng minh. Xét cặp m và n là hai số nguyên tố cùng nhau, Y m= pνp (m) p|m và Y n= q νq (n). q|n Do (m, n) = 1 nên tập hợp các số nguyên tố là ước của m và tập hợp các số nguyên tố là ước của n là rời nhau. Vì vậy Y Y mn = pνp (m) q νq (n) p|m q|n là phép phân tích thành nhân tử của mn, và Y Y d(mn) = (νp (m) + 1) (νq (n) + 1) = d(m)d(n). p|m q|n Vậy định lý đã được chứng minh. 13
Bài toán 1.7. Tính d(20). Lời giải. Ta có d(20) = d(22 .51 ) = (2 + 1)(1 + 1) = 6. Bài toán 1.8. Chứng minh rằng n là số nguyên tố khi và chỉ khi d(n) = 2. Lời giải. Nếu n là số nguyên tố thì n là một số tự nhiên lớn hơn 1 và không có ước nào ngoài 1 và chính nó. Do đó d(n) = 2. Nếu d(n) = 2 thì số các ước số của số nguyên dương n là 2. Như vậy n là một số nguyên tố. Bài toán 1.9. Chứng minh rằng d(n) là số nguyên tố khi và chỉ khi n = pq−1 với q và p là các số nguyên tố. Lời giải. Nếu d(n) là số nguyên tố, giả sử đó là số q . Khi đó, ta có d(n) = (q − 1) + 1. Như vậy n = pq−1 với p là số nguyên tố. Ngược lại, nếu n = pq−1 với q và p là các số nguyên tố thì hiển nhiên d(n) = (q − 1) + 1 = q . Vậy nên d(n) là số nguyên tố. Ta thu được điều phải chứng minh. 1.1.5 Một số đẳng thức giữa các hàm số học Tiếp theo, ta xét một số đẳng thức giữa các hàm d(n), σ(n) và ϕ(n). Bài toán 1.10 (xem [4],[6-7]). Cho dãy số nguyên dương xn xác định theo quy luật sau x0 = a, xn+1 = d(xn ), ∀n ≥ 0. Chứng minh rằng ∀a ∈ N∗ , tồn tại chỉ số n0 (phụ thuộc a) sao cho xn = 2 với mọi n ≥ n0 . √ Lời giải. Ta có d(n) ≤ 2 n < n nếu n > 4. Với n = 4 và n = 3, thử trực tiếp cho thấy d(4) = 3 < 4 và d(3) = 2 < 3. Với n = 2 thì d(2) = 2. Vậy, ta có d(n) < n, ∀n > 2 và d(2) = 2. Suy ra xn+1 < xn nếu xn > 2. Vì (xn ) là các số nguyên dương nên bắt đầu từ chỉ số n0 nào đó, ta phải có xn0 = 2. Khi ấy xn = 2, ∀n ≥ n0 . Bài toán 1.11 (xem [4], [6]). Chứng minh rằng nếu σ(n) = 2n + 1 thì n là bình phương của một số lẻ. 14
Lời giải. Vì σ(n) = 2n + 1 là một số lẻ. Do đó, ta có n = 2α m2 , trong đó α ≥ 0 còn m là số lẻ. Ta cần chứng minh α = 0. Ta có σ(n) = 2n + 1 = 2α+1 m2 + 1. Do tính chất nhân tính của hàm σ(n), ta lại có σ(n) = σ(2α ).σ(m2 ) = (2α+1 − 1).σ(m2 ). . Vậy nên 2α+1 m2 + 1 = (2α+1 − 1).σ(m2 )..2α+1 − 1. Ta lại có 2α+1 m2 + 1 = 2α+1 m2 + 1 − m2 + m2 . = m2 (2α+1 − 1) + (m2 + 1) .. 2α+1 − 1. . Suy ra m2 + 1 .. 2α+1 − 1. Nếu a > 0 thì 2α+1 − 1 có dạng 4k − 1. Do đó nó có ước nguyên tố p dạng 4k − 1. Vậy nên m2 ≡ −1 (mod p). p−1 Suy ra mp−1 ≡ (−1) 2 = (−1) (mod p). Điều này trái với Định lý Fermat. Do vậy α = 0. Bài toán 1.12 (xem [4], [6]). Chứng minh rằng với mỗi số tự nhiên k , tồn tại ít nhất một số nguyên dương n để cho ϕ(n + k) = ϕ(n). Lời giải. Nếu k chẵn thì ϕ(k + k) = ϕ(2k) = ϕ(2)ϕ(k) = ϕ(k). Vậy ta có thể chọn n = k . Xét trường hợp k lẻ. Gọi p là số nguyên tố bé nhất trong tập hợp các số nguyên tố không phải là ước của k . Ta có ϕ(pk) = ϕ(p)ϕ(k) = (p − 1)ϕ(k). Giả sử p1 , p2 , . . . , pr là các ước nguyên tố của k . Mọi ước nguyên tố của p − 1 cũng nằm trong tập (p1 , p2 , . . . , pr ) do cách chọn p. Vậy thì 1 1 ϕ((p − 1)k) = (p − 1)k 1 − ... 1 − = (p − 1)ϕ(k). p1 pr Suy ra ϕ(pk) = ϕ((p − 1)k). Vậy có thể chọn n = (p − 1)k . Bài toán 1.13. Chứng minh rằng Y d = nd(n)/2 . d|n 15
Lời giải. Giả sử n = pa với p là số nguyên tố và a là số nguyên dương. Ta có các ước của pa là 1, p, p2 , . . . , pa . Do đó Y a(a+1) d = 1.p.p2 . . . pa = p1+2+···+a = p 2 . d|n Mặt khác, d(n) = a + 1, nên d(n) a+1 a(a+1) n 2 = (pa ) 2 =p 2 . Như vậy Y d = nd(n)/2 . d|n Giả sử số nguyên dương n có phân tích chính tắc (ra thừa số nguyên tố) dạng n = pa11 pa22 . . . pas s . Khi đó Y a1 (a1 +1) a2 (a2 +1) as (as +1) (a1 +1)(a2 +1)...(as +1) d = p1 2 p2 2 . . . ps 2 = (pa11 pa22 . . . pas s ) 2 . d|n Mặt khác, d(n) = (a1 + 1)(a2 + 1) . . . (as + 1). Vì thế d(n) (a1 +1)(a2 +1)...(as +1) n 2 = (pa11 pa22 . . . pas s ) 2 . Như vậy Y d = nd(n)/2 . d|n Bài toán 1.14. Chứng minh rằng với mọi số tự nhiên n ≥ 2, ta có σ(n) + ϕ(n) ≥ 2n (n ≥ 2). Lời giải. Giả sử các ước của n là 1 = d1 < d2 < . . . < dk = n. n Trong các số tự nhiên không vượt quá n, có là số bội của di . Mỗi số không di vượt quá n và không nguyên tố cùng nhau với n phải là bội của một ước nào đó (> 1) của n. Vì thế ta có n n n n − ϕ(n) ≤ + + ··· + . d2 d3 dk Mặt khác, n n n + + ··· + = dk−1 + dk−2 + · · · + d1 = σ(n) − n. d2 d3 dk Vậy nên n − ϕ(n) ≤ σ(n) − n, tức là σ(n) + ϕ(n) ≥ 2n (n ≥ 2). Khi n là nguyên tố, ta có đẳng thức σ(n) + ϕ(n) = 2n. 16