Tài liệu Về hàm tổng gcd

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHAN NGUYỄN NGỌC DUNG VỀ HÀM TỔNG - GCD LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHAN NGUYỄN NGỌC DUNG VỀ HÀM TỔNG - GCD 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ố: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. NÔNG QUỐC CHINH Thái Nguyên - 2016 i Mục lục Danh mục ký hiệu ii Mở đầu 1 Chương 1. Ước chung lớn nhất 4 1.1 Khái niệm và tính chất của ước chung lớn nhất . . . . . . . . . 4 1.2 Thuật toán Euclid . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Một số bài tập liên quan ước chung lớn nhất . . . . . . . . . . . 11 Chương 2. Hàm tổng ước chung lớn nhất 15 2.1 Định nghĩa hàm tổng ước chung lớn nhất . . . . . . . . . . . . . 15 2.2 Một số tính chất của hàm tổng ước chung lớn nhất . . . . . . . 18 2.3 Chuỗi Dirichlet G(s) . . . . . . . . . . . . . . . . . . . . . . . . 21 Chương 3. Ứng dụng 33 3.1 Ứng dụng của hàm tổng ước chung lớn nhất . . . . . . . . . . . 33 3.2 Một số bài tập khó về ước chung lớn nhất . . . . . . . . . . . . 36 Kết luận 44 Tài liệu tham khảo 45 ii Danh mục ký hiệu (m, n) Ước chung lớn nhất của hai số m và n n X g(n) = S(n) = (j, n) j=1 n X Hàm tổng ước chung lớn nhất (2j − 1, n) Hàm đếm điểm mạng j=1 φ(n) Phi hàm Euler ω(n) Số số nguyên tố phân biệt là ước của n d(n) = σ0 (n) = X d0 Hàm ước số d|n ζ(s) = ∞ X n−s , Re(s) > 1 Hàm zeta Riemann n=1 ∞ X g(n) , Re(s) > 2 Chuỗi Dirichlet 2 n n=1 X g(n) Gα (x) = Hàm tổng riêng của chuỗi Dirichlet α n n≤x n X Tích chập Dirichlet (f ∗ g)(n) = f (d)g d G(s) = d|n µ(d) Hàm Möbius 1 Mở đầu Trong toán học, nếu số nguyên a chia hết cho số nguyên d thì số d được gọi là ước của số nguyên a, a được gọi là bội của d. Số nguyên dương d lớn nhất là ước của cả hai số nguyên a, b được gọi là ước chung lớn nhất của a và b, ký hiệu d = (a, b). Ước chung lớn nhất của hai số a và b có nhiều tính chất lý thú, ta có thể áp dụng để giải các bài tập về số học và hình học. Năm 1935, Pillai [5] là người đầu tiên đưa ra định nghĩa hàm tổng ước chung lớn nhất (hàm Pillai) bằng hệ thức g(n) = n X (j, n) j=1 trong đó (j, n) là ước chung lớn nhất của hai số j và n. Ông chứng minh rằng X φ(n) , g(n) = n d d|n trong đó φ(n) là hàm Euler. Hàm tổng ước chung lớn nhất là một hàm số sơ cấp được định nghĩa bằng tổng các ước chung lớn nhất của n số nguyên đầu tiên với n. Trong quá trình phát triển của khoa học kỹ thuật nói chung và toán học nói riêng, kết quả về hàm tổng ước chung lớn nhất đã được nhiều nhà toán học phát triển theo các hướng khác nhau. Năm 2001, một kết quả mới về ứng dụng của hàm tổng ước chung lớn nhất được công bố bởi Kevin A. Broughan. Hàm này xuất hiện khi tìm kiếm đánh giá xấp xỉ cho bài toán đếm điểm mạng. Bài toán đếm điểm mạng (điểm có tọa độ nguyên) của một vật thể là bài toán cổ trong lý thuyết số được đưa ra bởi Gauss và Dirichlet. Hàm tổng ước chung lớn nhất có quan hệ chặt chẽ với bài toán đếm điểm mạng. 2 Sau đó, nhiều nhà toán học trên thế giới đã quan tâm hướng nghiên cứu này và các kết quả về hàm tổng ước chung lớn nhất lần lượt được công bố, theo hướng đi sâu và mở rộng thành hàm tổng ước chung lớn nhất suy rộng. Với mong muốn tìm hiểu sâu hơn về ước chung lớn nhất và hàm tổng ước chung lớn nhất, dưới sự hướng dẫn của PGS. TS. Nông Quốc Chinh tôi mạnh dạn chọn đề tài nghiên cứu: “Về hàm tổng-gcd”. Mục đích nghiên cứu của luận văn là khai thác về ước chung lớn nhất, hàm tổng ước chung lớn nhất cùng các tính chất số học của hàm tổng ước chung lớn nhất dựa trên bài báo “The gcd-Sum Function” của Kevin A. Broughan đăng trong tạp chí Journal of Integer Sequence năm 2001. Nội dung của luận văn gồm ba chương: Chương 1. Ước chung lớn nhất. Trong chương này, chúng tôi trình bày một số khái niệm và các tính chất cơ bản về ước chung lớn nhất của các số tự nhiên. Để tìm ước chung lớn nhất, chúng tôi trình bày thuật toán Euclid. Chương 2. Hàm tổng ước chung lớn nhất. Trong chương này, chúng tôi trình bày các kết quả gần đây về hàm tổng ước chung lớn nhất bao gồm định nghĩa và một số tính chất, chuỗi Dirichlet với số hạng tổng quát là hàm tổng ước chung lớn nhất. Chương 3. Ứng dụng. Trong phần này, chúng tôi trình bày cách ứng dụng của hàm tổng ước chung lớn nhất trong bài toán đếm điểm mạng nguyên. Ngoài ra còn có một số bài tập phổ thông về ước chung lớn nhất. Trong quá trình thực hiện luận văn thạc sĩ, tác giả đã nhận được sự giúp đỡ, tạo điều kiện nhiệt tình và quý báu của nhiều cá nhân, tập thể. Lời đầu tiên tác giả xin được bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS. Nông Quốc Chinh đã tận tình hướng dẫn trong suốt quá trình làm luận văn này. Tác giả xin chân thành cảm ơn toàn thể các thầy cô trong Khoa Toán Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã tận tình hướng dẫn, truyền đạt kiến thức trong suốt thời gian theo học, thực hiện và hoàn thành luận văn. Cảm ơn sự giúp đỡ của bạn bè, người thân và các đồng nghiệp để tôi có 3 thể hoàn thành luận văn này. Thái Nguyên, tháng 5 năm 2016 Tác giả Phan Nguyễn Ngọc Dung 4 Chương 1 Ước chung lớn nhất Trong chương này, chúng tôi trình bày một số khái niệm và các tính chất cơ bản về ước chung lớn nhất của các số tự nhiên. Để tìm ước chung lớn nhất, chúng tôi trình bày thuật toán Euclid. Các bài tập trong toán học phổ thông về ước chung lớn nhất được trình bày trong mục 1.3. 1.1 Khái niệm và tính chất của ước chung lớn nhất Trong lý thuyết số, tập số tự nhiên là N = {0, 1, 2, 3, 4, . . .}, và tập số nguyên là Z = {. . . , −3, −2, −1, 0, 1, 2, 3 . . .}. Định nghĩa 1.1.1. ([7]). Cho a, b ∈ Z ta nói rằng b chia hết a, ký hiệu a | b, nếu tồn tại c ∈ Z để xảy ra ac = b. Trong trường hợp này, ta nói rằng a là ước của b. Ta nói rằng b không chia hết a, ký hiệu a - b, nếu không tồn tại c ∈ Z sao cho ac = b. . Khi a | b ta cũng nói b là bội của a hoặc b chia hết cho a và ký hiệu là b..a. Ví dụ 1.1.2. Ta có 2 | 6 vì với 3 ∈ Z, 2 · 3 = 6, −3 | 15 vì với −5 ∈ Z thì −3 · (−5) = 15, 3 - 7 trong Z vì 7 = 2 · 3 + 1, vì vậy 3 không là ước của 7. 5 Nhận xét 1.1.3. Tất cả mọi số nguyên đều là ước của 0, và 0 chỉ là ước của không. Mọi số nguyên đều có ước là 1 và chính nó, ta gọi chúng là các ước tầm thường. Định nghĩa 1.1.4. ([7]). Một số nguyên n > 1 được gọi là nguyên tố nếu n chỉ có ước là 1 và chính nó. Nếu số n không là số nguyên tố thì ta nói n là hợp số. Ví dụ 1.1.5. Dãy các số nguyên tố đầu tiên trong N là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, . . . và các hợp số đầu tiên là 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, . . . Nhận xét 1.1.6. Số 1 không là hợp số cũng không là số nguyên tố. Định lý 1.1.7. (Định lý cơ bản của số học). Mọi số tự nhiều đều được viết duy nhất dưới dạng tích của các số nguyên tố nếu không kể đến thứ tự các nhân tử. Định nghĩa 1.1.8. Một số nguyên dương d được gọi là ước chung của hai số nguyên a và b khi và chỉ khi d là ước của a và d cũng là ước của b. Định nghĩa 1.1.9. Ước chung lớn nhất của hai số a và b, ký hiệu là (a, b), là số nguyên dương lớn nhất d thỏa mãn d | a và d | b. Tức là (a, b) = max{d ∈ Z : d | a và d | b}. Ví dụ 1.1.10. (1, 2) = 1, (5, 10) = 2, (6, 27) = 3, và với bất kỳ a, (0, a) = (a, 0) = a. Đặc biệt (0, 0) = 0. Định nghĩa 1.1.11. Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu (a, b) = 1. Mệnh đề 1.1.12. Giả sử a và b là các số nguyên với b 6= 0. Khi đó tồn tại duy nhất hai số nguyên q và r sao cho a = bq + r, với 0 ≤ r < |b|. 6 Chứng minh. Để cho đơn giản, giả sử cả a và b đều dương. Gọi Q là tập các số nguyên không âm n sao cho a − bn không âm. Khi đó Q khác rỗng bởi vì 0 ∈ Q và Q bị chặn bởi vì a − bn < 0 với mọi n > a/b. Lấy q là phần tử lớn nhất của Q. Khi đó r = a − bq < b, vì nếu ngược lại q + 1 cũng thuộc Q. Do đó q và r thỏa điều kiền tồn tại. Để chứng minh tính duy nhất, giả sử rằng q 0 và r0 cũng thỏa mãn mệnh đề. Khi đó q 0 ∈ Q vì r0 = a − bq 0 ≥ 0, nên q 0 ≤ q, và ta có thể viết q 0 = q − m với m ≥ 0. Nếu q 0 6= q, thì m ≥ 1, nên r0 = a − bq 0 = a − b(q − m) = a − bq + bm = r + bm ≥ b do r ≥ 0, mâu thuẫn. Do đó q = q 0 và r0 = a − bq 0 = a − bq = r, điều phải  chứng minh. Bổ đề 1.1.13. Với các số nguyên bất kỳ a và b, ta có (a, b) = (b, a) = (±a, ±b) = (a, b − a) = (a, b + a). Chứng minh. Chúng tôi chỉ chứng minh (a, b) = (a, b − a), vì các trường hợp khác được chứng minh tương tự. Giả sử d | a và d | b, khi đó tồn tại c1 và c2 sao cho a = c1 d và b = c2 d. Khi đó b − a = c2 d − c1 d = d(c2 − c1 ), nên d | (b − a). Do đó (a, b) ≤ (a, b − a), vì tập mà ta lấy giá trị cực đại của (a, b) là tập con của (a, b − a). Lập tuận tương tự với a được thay bằng −a và b được thay bằng b − a, chi ra (a, b − a) = (−a, b − a) ≤ (−a, b) = (a, b), chứng tỏ (a, b) = (a, b − a).  Bổ đề 1.1.14. Giả sử a, b, n ∈ Z. Khi đó (a, b) = (a, b − an). Chứng minh. Bằng cách áp dụng liên tiếp Bổ đề 1.1.13 n lần, ta có (a, b) = (a, b − a) = (a, b − 2a) = · · · = (a, b − na).  Bổ đề 1.1.15. Với các số nguyên a, b, n bất kỳ, ta có (an, bn) = (a, b) · |n|. 7 Chứng minh. Để cho đơn giản, giả sử cả a và b đều dương. Chúng ta sẽ chứng minh bổ đề bằng phương pháp quy nạp theo a + b. Phát biểu của bổ đề vẫn đúng trong trường hợp cơ sở khi a + b = 2, vì a = b = 1. Bây giờ giả sử a, b là tùy ý với a ≥ b. Lấy q và r sao cho a = bq + r và 0 ≤ r < b. Khi đó, theo Bổ đề 1.1.13-1.1.14, ta có (a, b) = (b, r). Nhân a = bq + r với n ta thấy rằng an = bnq + rn, nên (an, bn) = (bn, rn). Khi đó b + r = b + (a − bq) = a − b(q − 1) ≤ a < a + b, nên theo quy nạp (bn, rn) = (b, r) · |n|. Vì (a, b) = (b, r), điều này chứng minh  bổ đề. Bổ đề 1.1.16. Giả sử a, b, n ∈ Z thỏa mãn n | a và n | b. Khi đó n | (a, b). Chứng minh. Vì n | a và n | b, tồn tại các số nguyên c1 và c2 sao cho a = nc1 và b = nc2 . Theo Bổ đề 1.1.15, (a, b) = (nc1 , nc2 ) = n(c1 , c2 ), nên n là ước của (a, b). 1.2  Thuật toán Euclid Phương pháp đơn giản để tính (a, b) là phân tích các số a và b thành tích các số nguyên tố bằng Định lý 1.1.7, sau đó chọn các nhân tử chung của hai sự phân tích, ta có số d = (a, b). Ví dụ, nếu a = 2261 và b = 1275, thì a = 7·17·19 và b = 3 · 52 · 17, nên (a, b) = 17. Tuy nhiên, phương pháp này sẽ không phù hợp khi a và b là các số rất lớn. Vì vậy cần có một phương pháp khác hữu hiệu hơn. Đó là thuật toán Euclid. Thuật toán Euclid. (Thuật toán tìm ước chung lớn nhất). Giả sử a và b là các số nguyên với b 6= 0. Thuật toán này tính (a, b). 1. [Giả sử a > b > 0] Ta có (a, b) = (|a|, |b|) = (|b|, |a|), nên ta có thể thay a và b bằng trị tuyệt đối của chúng. Nếu a = b, trả kết quả a và kết thúc. Nếu b = 0, trả kết quả a. 2. [Thương và phần dư] Tìm các số nguyên q và r sao cho a = bq + r, với 0 ≤ r < b và q ∈ Z. 8 3. [Kết thúc?] Nếu r = 0, thì b | a, nên trả kết quả b và kết thúc. 4. [Dịch chuyển và lặp lại] Đặt a ← b và b ← r, quay trở lại Bước 2. Chứng minh. Bổ để 1.1.13-1.1.14 kéo theo (a, b) = (b, r) nên ước chung lớn nhất không thay đổi trong Bước 4. Vì các số dư tạo thành một dãy số nguyên  không âm giảm, thuật toán kết thúc. Bên cạnh những phép tính số học tẻ nhạt, cách tính toán trên là có tính hệ thống, và nó không đòi hỏi phân tích thừa số của số bất kỳ (mà đôi khi ta không biết cách để tính nhanh nếu các số có hàng trăm chữ số). Bổ đề 1.2.1. Tại mỗi thời điểm, thuật toán Euclid cho hai số nguyên a và b, tích của hai số hiện tại (b và r) giảm xuống bằng một nhân tử ít nhất là 2 trong mỗi vòng lặp. Chứng minh. Xét vòng lặp mà cặp {a, b} (a > b) được thay bằng cặp (b, r) (nhắc lại rằng r là phần dư khi chia a cho b). Khi đó ta có r < b và b + r ≤ a. 1  Cho nên a ≥ b + r > 2r, và do đó br < ab. 2 Định lý 1.2.2. Số bước của thuật toán Euclid áp dụng cho hai số nguyên dương a và b nhiều nhất là log2 a + log2 b. Chứng minh. Giả sử ta áp dụng thuật toán Euclid cho hai số a và b và ta thực hiện k bước. Từ Bổ đề 1.2.1 suy ra rằng sau k bước, tích của hai số hiện tại ab nhiều nhất là k . Vì đây là một số nguyên dương nên nó luôn lớn hơn hoặc 2 bằng 1, ta có ab > 2k , và do vậy k ≤ log2 (ab) = log2 a + log2 b. Số bước của thật toán Euclid có cận trên là log2 a + log2 b. Ví dụ 1.2.3. Đặt a = 15 và b = 6. 15 = 6 · 2 + 3, 6 = 3 · 2 + 0, (15, 6) = (6, 3), (6, 3) = (3, 0) = 3.  9 Ta tìm được (15, 6) = 3. Chú ý rằng ta có thể dễ dàng thực hiện một ví dụ với số lớn gấp 10 lần, một nhận xét đóng vai trò quan trọng trong chứng minh của Định lý 1.2.7 bên dưới. Ví dụ 1.2.4. Cho a = 150 và b = 60. 150 = 60 · 2 + 30, (150, 60) = (60, 30), 60 = 30 · 2 + 0, (60, 30) = (30, 0) = 30. Ta tìm được (150, 60) = 30. Ví dụ 1.2.5. Cho a = 9081 và b = 3270. 9081 = 3 · 3270 − 729, 3270 = 4 · 729 + 354, 729 = 2 · 354 + 21, 354 = 17 · 21 − 3, (9081, 3270) = (3270, 729), (3270, 729) = (729, 354), (729, 354) = (354, 21), (354, 21) = (21, 3) = 3. Ta tìm được (9081, 3270) = 3. Ví dụ 1.2.6. (2k − 1, 9k + 4) = (9k + 4 − 4(2k − 1), 2k − 1) = (k + 8, 2k − 1) = (2k − 1 − 2(k + 8), k + 8)   1 (k 6= 17m − 8), = (k + 8, −17) = (k + 8, 17) =  17 (k = 17m − 8). Vậy (2k − 1, 9k + 4) = 17 khi k = 17m − 8 và (2k − 1, 9k + 4) = 1 khi k 6= 17m − 8. Định lý 1.2.7. (Euclid). Cho p là một số nguyên tố và a, b ∈ N. Nếu p | ab thì p | a hoặc p | b. 10 Chứng minh. Nếu p - a thì (p, a) = 1, vì chỉ có 1 và p là ước của p. Theo Bổ đề 1.1.15, (pb, ab) = b. Vì p | pb và theo giả thiết p | ab, suy ra rằng p | (pb, pa) = b(p, a) = b · 1 = b.  Định lý 1.2.8. Ký hiệu d = (a, b). Khi đó tồn tại m, n ∈ Z sao cho d = am + bn. Chứng minh. Ta sẽ chứng minh mọi số sinh ra trong thuật toán Euclid cho (a, b) đều được viết dưới dạng tổng của một số nguyên nhân với a cộng với một số nguyên nhân với b. Điều này đúng với số đầu tiên r = a − qb. Giả sử điều này đúng với hai số liên tiếp ta vừa tính, tức là tồn tại a0 = am + bn, và b0 = ak + bl, trong đó m, n, k, l là các số nguyên. Khi đó, ở bước tiếp theo ta tính phần dư của b0 môđun a0 , bằng a0 − qb0 = (am + bn) − q(ak + bl) = a(m − qk) + b(n − ql), và một lần nữa lại có dạng cần tìm.  Hệ quả 1.2.9. Giả sử a, b, r là các số nguyên sao cho (a, b) = 1. Nếu a là ước của br thì a là ước của r. Chứng minh. Ta có thể viết 1 = am + bn với m, n ∈ Z. Rõ ràng a là ước của mar và nbr, nên m là ước của mar + nbr = r · (am + bn) = r · 1 = r.  Ví dụ 1.2.10. Sử dụng thuật toán Euclid ta có thể tìm hai số nguyên m và n sao cho (a, b) = am + bn. Đầu tiên dùng thuật toán Euclid để tính (a, b) và sau đó thực hiện bước quay lại. Ví dụ, ta đã biết ở Ví dụ 1.2.5 rằng (9081, 3270) = 3. Ta muốn tìm hai số m và n sao cho 3 = 9081m + 3270n. 11 Bây giờ ta làm quay lại khi tính (9081, 3270). Từ 354 = 17 · 21 − 3 suy ra 3 = (−1) · 354 + 17 · 21. Từ 729 = 2 · 354 + 21, 3 = (−1) · 354 + 17 · (729 − 2 · 354) = 17 · 729 + (−1 − 17 · 2) · 354 = 17 · 729 − 35 · 354. Từ 3270 = 4 · 729 + 354 suy ra 3 = 17 · 729 − 35 · (3270 − 4 · 729) = −35 · 3270 + (17 + 35 · 4) · 729 = −35 · 3270 + 157 · 729. Và cuối cùng, từ 9081 = 3 · 3270 − 729 suy ra 3 = −35 · 3270 + 157 · (−9081 + 3 · 3270) = −157 · 9081 + (−35 + 3 · 157) · 3270 = −157 · 9081 + 436 · 3270. 1.3 Một số bài tập liên quan ước chung lớn nhất Để nắm chắc hơn về ước chung lớn nhất, ở đây chúng tôi trình bày một số bài tập về ước chung lớn nhất. Ví dụ 1.3.1. (Putnam 2000). Chứng minh rằng biểu diễn   (m, n) n n m là một số nguyên, trong đó n m
= n! là hệ số nhị thức Newton. m!(n − m)! Giải. Dựa theo Định lý 1.2.8, ta có thể viết (m, n) = xm + yn, 12 trong đó x, y là các số nguyên. Khi đó       n (m, n) n m n =x +y . n m m n m Bây giờ     n! n−1 m (n − 1)! m n = = = n m n m!(n − m)! (m − 1)!(n − m)! m là một số nguyên. Suy ra   (m, n) n n m là một số nguyên. Ví dụ 1.3.2. Một người bán hoa có 36 bông hoa hồng, 27 bông tuy líp và 18 bông cẩm chướng. Cô phải bó thành các bó hoa đều nhau. Hỏi có thể làm bao nhiêu bó hoa trong đó mỗi bó phải có ít nhất một loại hoa mà không có bông hoa nào còn sót lại. Giải. Ta tìm ước chung lớn nhất, nhân tử còn lại trong mỗi số cho ta biết mỗi bó hoa có bao nhiêu bông hoa mỗi loại. hoa hồng 36 = 2 · 18 = 2 · 2 · 9 = 2 · 2 · 3 · 3 = 22 · 32 , hoa tuy líp 27 = ·3 · 9 = 3 · 3 · 3 = 33 , hoa cẩm chướng 18 = 2 · 9 = 2 · 3 · 3 = 2 · 32 . Uớc chung lớn nhất = 33 = 9 bó hoa. Mỗi bó hoa sẽ có 22 = 4 bông hoa hồng, 3 bông tuy líp và 2 bông cẩm chướng. Ví dụ 1.3.3. Giả sử bạn có 60 cái bút chì, 90 bút bi và 120 cái bảng viết và bạn muốn đóng gói bút chì, bút bi, bảng viết để đem đi tặng cho học sinh trong trường. Hỏi số gói quà giống nhau lớn nhất bạn có thể tạo ra từ các đồ trên, và bao nhiêu bút chì, bút bi, bảng viết trong mỗi gói quà? Giải. Ta có bút chì = 22 · 3 · 5, bút bi = 2 · 32 · 5, bảng viết = 263 · 3 · 5 . 13 Ước chung lớn nhất bằng 2 · 3 · 5 = 30 gói quà với mỗi gói quà có 2 bút chì, 3 bút bi và 4 cái bảng. Ví dụ 1.3.4. Giả sử bạn cần làm hai cái vườn cạnh nhau với tường bao quanh toàn bộ mỗi cái vườn. Một cái vườn có diện tích là 180 m2 , vườn còn lại có diện tích là 204 m2 . Nếu tường bao quanh có đơn vị dài là 1 m, hỏi chiều dài lớn nhất của tường rào chung của hai vườn là bao nhiêu? Tường rào dài bao nhiêu? Giải. Vì diện tích bằng chiều dài nhân chiều rộng, ta đi tìm chiều rộng chung lớn nhất giữa hai cái vườn. 180 = 22 · 32 · 5, 204 = 22 · 3 · 17, ƯCLN = 22 · 3 = 12 Giá trị chiều rộng chung lớn nhất là 12 m. Chiều dài của mảnh vườn đầu tiên là 3 · 5 = 15 m vì 15 · 12 = 180 và chiều dài của mảnh vườn thứ hai sẽ là 17 m vì 17 · 12 = 204. Nên ta có một mảnh vườn 12 · 15 cạnh mạnh vườn 12 · 17. Chiều dài tường bao là 12 + 15 + 12 + 15 + 17 + 12 + 17 = 90 m. Ví dụ 1.3.5. Chứng minh rằng với mọi số tự nhiên n thì các số sau nguyên tố cùng nhau: 2n + 3 và 4n + 8. Giải. Để chứng minh hai số nguyên tố cùng nhau, ta chứng minh ước chung lớn nhất của chúng bằng 1. Theo Bổ đề 1.1.14, ta có (2n + 3, 4n + 8) = (2n + 3, 4n + 8 − 2(2n + 3)) = (2n + 3, 2) = 1 do 2n + 3 là số lẻ. Vậy 2n + 3 và 4n + 8 nguyên tố cùng nhau. Ví dụ 1.3.6. Tìm số tự nhiên n để các số sau nguyên tố cùng nhau: 7n + 13 và 2n + 4. Giải. Đặt d = (7n + 13, 2n + 4). Theo Bổ đề 1.1.14, ta có (7n + 13, 2n + 4) = (2(7n + 13), 7(2n + 4)) 14 = (14n + 26, 14n + 28) = (14n + 26, (14n + 28 − 14n − 26)) = (14n + 26, 2). Do đó d ∈ {1, 2}. Nếu d = 2 thì 2 | 7n + 13 ⇒ 2 | 7(n + 1) + 6 ⇒ 2 | 7(n + 1) ⇒ 2 | (n + 1) ⇒ n = 2k − 1. Vậy để 7n + 13 và 2n + 4 nguyên tố cùng nhau thì n phải là số chẵn. 15 Chương 2 Hàm tổng ước chung lớn nhất 2.1 Định nghĩa hàm tổng ước chung lớn nhất Hàm tổng ước chung lớn nhất được Broughan lần đầu tiên đề xuất trong [1]. Định nghĩa 2.1.1. ([1]). Với mọi số tự nhiên n, hàm tổng ước chung lớn nhất được định nghĩa là g(n) = n X (j, n). (2.1) j=1 Dựa vào định nghĩa, ta tính hàm tổng ước chung lớn nhất với một số giá trị ban đầu nhỏ: g(1) = 1 X (j, 1) = (1, 1) = 1 j=1 g(2) = 2 X (j, 2) = (1, 2) + (2, 2) = 1 + 2 = 3 j=1 g(3) = 3 X (j, 3) = (1, 3) + (2, 3) + (3, 3) = 1 + 1 + 3 = 5 j=1 g(4) = 4 X (j, 4) = (1, 4) + (2, 4) + (3, 4) + (4, 4) = 1 + 2 + 1 + 4 = 8 j=1 ......... Trong từ điển bách khoa toàn thư trực tuyến về dãy số nguyên, dãy các giá trị của hàm tổng ước chung lớn nhất là dãy A018804: 16 1, 3, 5, 8, 9, 15, 13, 20, 21, 27, 21, 40, 25, 39, 45, 48, 33, 63, 37, 72, 65, 63, 45, 100, 65, 75, 81, 104, 57, 135, 61, 112, 105, 99, 117, 168, 73, 111, 125, 180, 81, 195, 85, 168, 189, 135, 93, 240, 133, 195, 165, 200, 105, 243, 189, 260, 185, 171, 117, 360, . . . Dựa vào dãy trên, ta có thể đưa ra nhận xét là hàm tổng ước chung lớn nhất không phải là hàm đơn điệu tăng. Hàm số mà cần để áp dụng đếm điểm mạng, được miêu tả dưới đây, là hàm S được định nghĩa bởi S(n) = n X (2j − 1, n). (2.2) j=1 Định lý 2.1.2. ([1]). Hàm S và hàm tổng ƯCLN g liên hệ theo hệ thức    g(n) n lẻ, (2.3) S(n) =   n 2g(n) − 4g( ) n chẵn. 2 Chứng minh. Với mọi n ≥ 1 n X (2j, n) + j=1 Nếu n lẻ thì n X (2j − 1, n) = j=1 n X (2j, n) = j=1 2n X (j, n) = 2g(n). (2.4) j=1 n X (j, n) = g(n). j=1 Từ kết quả này và (2.4) ta thu được phương trình S(n) = g(n). Nếu n chẵn thì n X j=1 (2j, n) = 2 n X n n (j, ) = 4g( ). 2 2 j=1 Và một lần nữa từ (2.4) ta suy ra điều phải chứng minh.  Định lý sau trình bày giá trị của hàm g tại lũy thừa của các số nguyên tố. Mặc dù có thể chứng minh trực tiếp, nhưng chúng tôi trình bày chứng minh bằng quy nạp vì điều này giúp tiết lộ nhiều thông tin cấu trúc của hàm này. Định lý 2.1.3. ([1]). Với mọi số nguyên tố p và số nguyên α ≥ 1: g(pα ) = (α + 1)pα − αpα−1 . (2.5)