Luận văn Thạc sĩ Khoa học: Phân số Ai Cập và biểu diễn đơn vị

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

Thêm vào BST

Báo xấu

16
lượt xem 3
download

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

Toán học Ai Cập rất đặc sắc về nhiều mặt. Một trong những khía cạnh rất kỳ lạ của Toán học cổ Ai Cập liên quan đến "Phân số". Các nhà Toán học cổ Ai Cập chỉ xét những phân số mà ta gọi là "Phân số đơn vị", phân số có tử số bằng 1 và mẫu số là các số nguyên dương.

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ĩ Khoa học: Phân số Ai Cập và biểu diễn đơn vị

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN THỊ HỒNG NHẬT PHÂN SỐ AI CẬP VÀ BIỂU DIỄN ĐƠN VỊ LUẬN VĂN THẠC SĨ KHOA HỌC HÀ NỘI - 2016
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN THỊ HỒNG NHẬT PHÂN SỐ AI CẬP VÀ BIỂU DIỄN ĐƠN VỊ LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành : PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số : 60 46 01 13 Giáo viên hướng dẫn: TS NGUYỄN VĂN NGỌC HÀ NỘI, 2016
Mục lục Mở đầu 1 1 Phân số Ai Cập 3 1.1 Giới thiệu về xây dựng thuật toán . . . . . . . . . . . . . . . . . . 3 1.1.1 Phương pháp tách . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Thuật toán Fibonaci-Sylvester . . . . . . . . . . . . . . . . 5 1.1.3 Thuật toán Golomb . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Số thực hành . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Thuật toán nhị phân . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 Thuật toán Bleicher/Erdo¨s . . . . . . . . . . . . . . . . . . 12 1.2.3 Giả thuyết của Goldbach . . . . . . . . . . . . . . . . . . . 16 1.2.4 Thuật toán Yokota . . . . . . . . . . . . . . . . . . . . . . . 17 1.2.5 Thuật toán Tenenbaum/Yokota . . . . . . . . . . . . . . . . 19 1.2.6 Thuật toán số thực hành "tối ưu" . . . . . . . . . . . . . . 20 1.3 Các thuật toán khác . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.1 Thuật toán giai thừa . . . . . . . . . . . . . . . . . . . . . . 22 1.3.2 Thuật toán Chuỗi Farey . . . . . . . . . . . . . . . . . . . 23 1.3.3 Thuật toán phân số tiếp diễn . . . . . . . . . . . . . . . . . 24 1.3.4 So sánh Thuật toán . . . . . . . . . . . . . . . . . . . . . . 24 1.4 Độ dài và chặn mẫu số . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.1 Chặn mẫu số . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.2 Chặn độ dài . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.4.3 Độ dài và chặn mẫu số . . . . . . . . . . . . . . . . . . . . . 29 1.5 Bài toán liên quan đến số cố định . . . . . . . . . . . . . . . . . . 31 1.6 Paul Erd¨os và các phân số Ai Cập . . . . . . . . . . . . . . . . . . 37 1.6.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.6.2 Giả thuyết của Erd¨os-Straus . . . . . . . . . . . . . . . . . 39 2
1.6.3 Các phân số Ai Cập trù mật . . . . . . . . . . . . . . . . . 40 1.6.4 Thêm các bài toán từ bài toán cũ, mới và kết quả . . . . . 41 1.6.5 Câu chuyên về một giả thuyết không đúng . . . . . . . . . 46 2 Biểu diễn đơn vị thành tổng của các phân số Ai Cập 49 2.1 Biểu diễn đơn vị thành tổng của các phân số Ai Cập với mẫu số nguyên dương đặc biệt . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.1.2 Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . 51 2.1.3 Chứng minh Định lý 2.1 . . . . . . . . . . . . . . . . . . . . 53 2.2 Biểu diễn đơn vị thành tổng của các phân số đơn vị với các mẫu số lẻ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.2 Chứng minh Định lý 2.2 . . . . . . . . . . . . . . . . . . . . 57 2.2.3 Chứng minh Định lý 2.3 . . . . . . . . . . . . . . . . . . . . 59 Kết luận 61 Tài liệu tham khảo 62 3
Mở đầu Toán học Ai Cập rất đặc sắc về nhiều mặt. Một trong những khía cạnh rất kỳ lạ của Toán học cổ Ai Cập liên quan đến "Phân số". Các nhà Toán học cổ Ai Cập chỉ xét những phân số mà ta gọi là "Phân số đơn vị", phân số có tử số bằng 1 và mẫu số là các số nguyên dương. Tại sao lại như vậy? Ở thời Ai Cập cổ đại, ký hiệu toán học trong hệ thập phân dựa trên cơ sở các ký hiệu bằng chữ tượng hình cho mỗi lũy thừa của mười cho đến một triệu. Mỗi kí hiệu trong số này có thể được viết đi viết lại nhiều lần nếu cần thiết để có thể đạt được con số mong muốn. Do đó, để viết được các số tám mươi hay tám trăm, ký hiệu mười hay một trăm sẽ được viết tám lần tương ứng. Bởi vậy phương pháp tính toán của họ không thể xử lí hầu hết các phân số có tử số lớn hơn 1, họ đã phải viết các phân số như là tổng của nhiều phân số có tử số bằng 1. Các phân số đơn vị này được viết như là số nguyên với dấu chấm hay kí hiệu nào đó ở bên trên. Nhưng trong luận văn này chúng ta vẫn dùng qui ước thông dụng để viết phân số. 2 1 1 Để viết phân số , các nhà Toán học cổ Ai Cập không thể viết + vì theo 5 5 5 quy ước viết các số lúc đó, phân số đơn vị chỉ được thể hiện một lần. Thay vì 1 1 2 1 1 viết + phân số được viết là + . Trong toán học cổ Ai Cập ngoài cách 5 5 5 3 15 dùng phân số đơn vị, một số phân số thông dụng họ quy ước viết bằng một số kí tự đặc biệt. Trong luận văn này liệt kê các thuật toán để viết phân số bằng tổng các phân số đơn vị.Tuy nhiên mỗi một phân số không có duy nhất một biểu diễn phân số đơn vị, do đó có sự phân tích tối ưu giữa các thuật toán. Luận văn cũng nghiên cứu việc biểu diễn các phân số thành tổng các phân số đơn vị thêm các điều kiện cố định, như số các số hạng, hay mẫu số lớn nhất. Ngoài ra luận văn còn nghiên cứu lời giải của bài toán về phương trình Diophantine trong các một số trường hợp. Đặc biệt là biểu diễn đơn vị thành tổng các phân số đơn vị. Để thực hiện luận văn tác giả chủ yếu thu thập và nghiên cứu từ các nguồn 1
tài liệu khác nhau, rồi phân tích các thuật toán đưa ra ví dụ minh họa cụ thể. Những tài liệu về phân số Ai Cập bằng Tiếng Việt rất ít. Do đó nếu luận văn được thực hiện thành công thì nó cũng là một tài liệu tham khảo bổ ích cho giáo viên và học sinh. Cấu trúc của luận văn được chia thành ba phần: phần mở đầu, phần nội dung và phần kết luận. Nội dung luận văn được chia làm hai chương: Chương 1. Phân số Ai Cập. Chương 2. Biểu diễn đơn vị thành tổng các phân số đơn vị. Trong thời gian thực hiện luận văn, tác giả đã nhận được sự hướng dẫn chỉ bảo tận tình của TS. Nguyễn Văn Ngọc. Qua đây, tác giả xin được bày tỏ lòng biết ơn sâu sắc và trân trọng những công lao, sự quan tâm, động viên và sự tận tình chỉ bảo của Thầy. Tác giả chân thành cảm ơn các thầy, cô khoa Toán - Cơ - Tin học Trường Đại học Khoa học Tự nhiên, ĐHQG hà Nội đã dạy bảo tận tình, các thầy cô giáo trong Ban giám hiệu, Phòng Đào tạo, Văn phòng Khoa Toán - Cơ - Tin học trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất trong suốt thời gian tác giả học tập và hoàn thiện luận văn. Hà Nội ngày 01/12/2016 Học viên Nguyễn Thị Hồng Nhật 2
Chương 1 Phân số Ai Cập 1.1 Giới thiệu về xây dựng thuật toán Một trong những vấn đề cơ bản liên quan đến phân số Ai Cập là sự tìm kiếm và xây dựng thuật toán-cách để viết bất kỳ phân số thành tổng của các phân số đơn vị, tức là những phân số có tử số bằng 1 và mẫu số là những số nguyên dương. Qua nhiều năm, có nhiều thuật toán khác nhau đã xây dựng cho các mục đích khác nhau, chúng bao gồm từ thuần túy lý thuyết tới thực hành. Rõ ràng là với mỗi một phân số bất kỳ có nhiều hơn môt cách mở rộng thành các phân số Ai Cập phân biệt. Nếu a 1 1 = + ··· + b x1 xn thì sử dụng hệ thức 1 1 1 = + , x x + 1 x(x + 1) ta thu được a 1 1 1 1 = + ··· + + + . b x1 xn−1 xn + 1 xn (xn + 1) Người Ai Cập có thể có hoặc không có một thuật toán để xây dựng mở rộng 2 phân số. Họ tạo ra một bản mở rộng của các số cho tất cả các số lẻ n
Kí hiệu Giả sử p 1 1 = + ··· + , n1 < n2 < · · · < nk . q n1 nk Chúng ta ký hiệu: • D(p, q) = giá trị nhỏ nhất có thể có của nk • D(q) = maxp {D(p, q)|0 < p < q} • L(p, q) = giá trị nhỏ nhất của k • L(q) = maxp {L(p, q)|0 < p < q} • O(f (n)) = vô cùng lớn của của f(n) khi n → ∞ • o(f (n)) = vô cùng bé của f(n) khi n → ∞. • f (x) g(x) : f(x) rất nhỏ so với g(x). • f (s, x) s g(s, x) : f(s,x) rất nhỏ so với g(s,x) theo biến s. Để thuận tiện ta cũng sẽ xác định: • Pi = Số nguyên tố thứ i, trong đó P1 = 2(P2 = 3, P3 = 5, · · · ) Q • k = P1 .P2 . . . Pk • S = {P 2k |k ≥ 0 và P là số nguyên tố} • si = phần tử nhỏ nhất thứ i của S 1.1.1 Phương pháp tách Có lẽ thuật toán thông dụng nhất cho việc tạo ra một mở rộng của phân số đơn vị là phương pháp tách. Nó dựa vào việc sử dụng lặp đi lặp lại của hệ thức 1 1 1 = + x x + 1 x(x + 1) mà nó được gọi là " hệ thức tách". p Cho phân số hữu tỷ < 1. q p 1 Bước1. Viết bằng tổng của phân số đơn vị q q 4
1 Bước 2. Nếu có hai phân số giống nhau trong khai triển (với mỗi số nguyên a 1 a), giữ lại một trong số chúng và thay các phân số khác bằng cách sử a dụng " hệ thức tách". Bước 3. Lặp lại bước 2 cho đến khi đạt được khai triển mà không có hai phân số có mẫu giống nhau. 3 Ví dụ 1.1. 7 3 1 1 1 = + + 7 7 7 7 1 1 1 1 1 = + + + + 7 8 56 8 56 1 1 1 1 1 = + + + + 7 8 8 56 56 1 1 1 1 1 1 1 = + + + + + + 7 8 9 72 56 57 3192 1 1 1 1 1 1 = + + + + + . 7 8 9 56 72 3192 1.1.2 Thuật toán Fibonaci-Sylvester Một thuật toán hữu ích và trực quan hơn nhiều là thuật toán Fibonaci - Sylvester. Nó lần đầu tiên được tìm thấy bởi Fibonaci vào năm 1202 và sau đó là bởi Sylvester. Thuật toán như sau p Cho phân số tối giản < 1. q Bước 1. Kí hiệu p0 = p và q 0 = q. p0 p0 Bước 2. Nếu = 1, đặt 0 là một phần của mở rộng, và ta đã làm xong. Nếu q không thì sử dụng thuật toán chia ta thu được q 0 = sp0 + r, trong đó r < p0 . p0 1 p0 − r 1 Bước 3. Chú ý rằng 0 = + 0 . Vì vậy là một phần của khai q s + 1 q (s + 1) s+1 triển. Bước 4. Đặt p0 = p0 − r và q 0 = q 0 (s + 1) . p0 Bước 5. Rút gọn phân số về phân số tối giản và quay lại bước 2. q0 5
Ví dụ 1.2. 3 1 2 = + 7 3 21 1 1 1 = + + . 3 11 231 Giải thích. Ở đây p0 = p = 3, q 0 = q = 7. Ta có 3 1 p0 − r 1 2 7 = 2.3 + 1, s = 2, r = 1, = + 0 = + . 7 s + 1 q (s + 1) 3 21 Tiếp theo, ta có p0 = 2, q 0 = 21. Ta có 2 1 p0 − r 1 1 21 = 10.2 + 1, s = 10, r = 1, = + 0 = + . 21 s + 1 q (s + 1) 11 231 Với phân số cuối cùng p0 = 1, ta dừng quá trình. Vậy, ta có 3 1 1 1 = + + . 7 3 11 231 Định lý 1.1. Ứng với mỗi thuật toán Fibonaci - Sylvester có một khai triển có không quá p số hạng. Chứng minh . Thuật toán đưa ra p0 1 p0 − r = + . q0 s + 1 q 0 (s + 1) Thực tế, ta biết rằng thuật toán tạo ra hầu hết p số hạng bởi vì tử số luôn nhỏ hơn. Cụ thể: p0 Khi là tối giản, ta biết rằng r > 0. q0 Ở bước 4, ta có p0 = p0 − r, vì vậy p0 mới ≥ p0 cũ − 1. Ở bước 2, ta dừng lại nếu p0 = 1, vì vậy ở đây có thể có hầu hết p số hạng. Mặc dù, trường hợp xấu nhất mà mỗi lần r = 1, và kết quả phân số là luôn luôn tối giản. Khi đó khai triển chắc chắn tạo ra p số hạng. Trên thực tế, trường hợp xấu nhất thường hiếm khi xảy ra. Mặt khác, vấn đề đặt ra đối với phương pháp này là mẫu số tạo ra có thể rất lớn. Ví dụ, thuật 5 toán Fibonaci-Sylvester mở rộng là: 121 5 1 1 1 1 1 = + + + + . 121 25 757 763309 873960180912 1527612795642093418846225 6
So sánh với kết quả tối ưu: 5 1 1 1 = + + . 121 33 121 363 Bản thân Fibonaci đã nhận ra thiếu xót này, chú ý rằng: 4 1 1 1 = + + 49 13 319 319(637) nhưng vì 4 1 1 = + 49 14 98 nên đã đề xuất thử phân số đầu tiên nhỏ hơn nếu như phân số đầu tiên không đưa ra được giải pháp "tối ưu" nào. Ông không định nghĩa giải pháp tối ưu là gì, và điều này khi đó trở thành thuật toán gây nên nhiều tranh cãi. Mays kiểm tra trường hợp xấu nhất của thuật toán - là trường hợp mà trong đó thuật toán đòi hỏi một số số hạng. Các phân số nhỏ nhất phù hợp trường hợp này là như sau: Các số hạng a/b 1 1/2 2 2/3 3 3/7 4 4/17 5 5/31 6 6/109 7 7/253 8 8/97 9 9/271 10 10/1621 11 11/199 1.1.3 Thuật toán Golomb Golomb đã xây dựng một thuật toán đơn giản mà có thể sử dụng để biểu p diễn một số hữu tỷ như là tổng của p hoặc ít hơn các phân số đơn vị. Thuật q toán được thực hiện như sau: 7
p Cho phân số tối giản < 1. q Bước 1: Đặt p0 = p và q 0 = q p0 Bước 2: Nếu p0 = 1, đặt là một phần của mở rộng, và ta đã làm xong. q0 Bước 3: Lấy p00 thỏa mãn p0 .p00 = q 0 r + 1, 0 < p00 < q 0 (p0 là nghịch đảo của p0 theo modul q 0 ) p0 1 r 1 Bước 4: Lưu ý 0 = 00 0 + 00 . Vì vậy 00 0 là một số hạng của khai triển. q p q p p q Bước 5: Đặtq 0 = p00 và p0 = r và quay trở lại bước 2. Ví dụ 1.3. 3 2 1 = + 7 5 35 1 1 1 = + + 3 15 35 Giải thích. Ở đây p0 = p = 3, q 0 = q = 7. Ta có 3 1 r 1 2 3.5 = 7.2 + 1, p00 = 5, r = 2, = 00 0 + 00 = + . 7 p q p 35 5 Tiếp theo, ta có p0 = 2, q 0 = 5. Ta có 2 1 r 1 1 2.3 = 5.1 + 1, p00 = 3, r = 1, = 00 0 + 00 = + . 5 p q p 15 3 Với phân số cuối cùng p0 = r = 1, ta dừng quá trình. Vậy, ta có 3 1 1 1 = + + . 7 3 15 35 Thuật toán này tốt hơn thuật toán Fibonaci-Sylvester trong trường hợp mà mẫu số thỏa mãn hầu hết q(q − 1). Đôi khi mẫu có thể phù hợp hơn cho thuật toán Fibonaci-Sylvester, nhưng ở đây mẫu số không bị giới hạn, như đã thấy ở trên, trong thực tế có thể mở rộng hơn. Định lý 1.2. Đối với thuật toán Golomb D(q) < q(q − 1). Chứng minh . Chú ý rằng ở bước 3, p00 < q 0 , vì vậy p00 ≤ q 0 − 1. Ở bước 4, mẫu số là p00 q, vì vậy mẫu số ≤ (q 0 − 1)q . Chú ý rằng ở bước 5, chúng ta lấy q’ mới = q’ cũ, vì vậy q’ là luôn luôn giảm dần. Do đó, mẫu số không thể lớn hơn q(q − 1). 8
1.2 Số thực hành p Dễ thấy rằng nếu p có thể viết bằng tổng các ước của q thì có thể biểu q diễn thành tổng các phân số đơn vị mà không có mẫu số nào lớn hơn q. Ví dụ, 9 ta có 9 = 4 + 5, chú ý rằng 4 và 5 là các ước của 20, nếu ta muốn mở rộng 20 thì ta viết 9 4+5 1 1 = = + 20 20 5 4 Thực tế Rav(1966) đã chứng minh định lý: m 1 1 1 Định lý 1.3. = + +· · ·+ nếu và chỉ nếu tồn tại các số nguyên dương M n x1 x2 xk M m và N và các ước D1 , · · · , Dk của N thỏa mãn = và D1 + D2 + · · · + Dk = 0 N n (mod M ). Ngoài ra, điều kiện cuối cùng có thể được thay thế bằng điều kiện D1 + D2 + · · · + Dk = M ; và điều kiện (D1 , · · · , Dk ) = 1 có thể được thêm vào mà không ảnh hưởng đến giá trị của định lý. Trong mục tiếp theo, ta sẽ trình bày cách chứng minh của định lý này. Từ tất cả tính chất trên ta đi đến định nghĩa về các con số mà ta gọi là số thực hành. Srinivasan đã định nghĩa đầu tiên các số thực hành vào năm 1948. Định nghĩa 1.1. Số thực hành là một số nguyên N sao cho với tất cả n < N, n có thể được viết như là tổng các ước phân biệt của N. Chẳng hạn, 4 là số thực hành, khi đó 1 = 1, 2 = 2 và 3 = 1 + 2.Mặt khác, 10 thì không phải, vì 4 không thể được viết bằng tổng của 1, 2, 5, và 10. Liên hệ với phân số Ai Cập, tính chất quan trọng nhất của các số thực hành được cho trong định lý sau. Định lý 1.4. Nếu n là một số thực hành và mỗi số q nguyên tố cùng n, và q < 2n thì qn cũng là số thực hành. 5 Vì vậy, nếu chúng ta muốn mở rộng , chúng ta chú ý rằng 12 là số thực 23 hành và do đó 5 5 (12) = 23 23 (12) Khi 23 < 2 (12)và 12 là số thực hành, chúng ta biết rằng 23 (12) cũng là số thực hành. Vì vậy 5 (12) có thể được viết bằng tổng của các ước phân biệt của 23 (12). Thực tế : 5 (12) 46 + 12 + 2 1 1 1 = = + + 23 (12) 23 (12) 6 23 138 9
Fibonaci gần như đã nảy ra ý kiến ở đây, như ông đã đề cập việc tìm ra một số "số mà có trong nó nhiều ước như 12,24,36,48,60,. . . " để nhân. Tuy nhiên, Ông ta thất bại trong việc trình một thuật toán dựa trên cái đã đạt được, (hoặc được định nghĩa những con số mà có "nhiều" ước). Loại tính toán này là cơ sở cho một vài cách xây dựng các thuật toán khác, đôi khi được gọi là thuật toán nhân - khi mà sự mở rộng thu được bởi việc nhân tử số và mẫu số với cùng một số. Chúng ta sẽ tạo ra một thuật toán đầu tiên và chứng minh những cái gì liên quan nó, sau đó mô tả vài thuật toán tạo ra gần đây nhất. Trước khi chúng ta bắt đầu, ta sẽ đưa ra một vài tính chất của các số thực hành như sau: • Nếu n có các ước 1 = d1 < d2 < · · · < dc = n thì n là số thực hành nếu và chỉ nếu r X dr ≥ dr+1 − 1 với mọi r < c − 1 i=1 Trên thực tế, tính chất này được sử dụng trong chương trình máy tính để kiểm tra tính thực hành. • Nếu n có một tập hợp con của các ước 1 = d1 , d2 , · · · , dc = n trong đó mỗi tập hợp có ít nhất là hai ước, thì n là số thực hành. • Nếu n là một số thực hành và m là một số tự nhiên ≤ n, mn là thực hành thì mk nk cũng là số thực hành. • Nếu n là số thực hành và tổng của các ước của n là ít nhất n + k trong đó k không phải là số nguyên âm, thì n(2n + k + 1) là số thực hành. 1.2.1 Thuật toán nhị phân Chúng ta chú ý rằng nếu N = 2n thì bất kì m < N có thể được viết bằng tổng của các ước phân biệt của N. Chúng ta chỉ đơn giản viết số theo kí hiệu của hệ nhị phân. Thực tế, m có thể được viết bằng tổng của n hoặc ít các ước hơn, khi 2n có đúng n ước là 20 , 21 , 22 , · · · , 2n−1 . Chẳng hạn 5 1+4 1 1 = = + 16 16 16 4 Nội dung thuật toán như sau: p Cho phân số tối giản q 10
Bước 1. Tìm Nk−1 < q ≤ Nk , trong đó Nk = 2k Bước 2. Nếu q = Nk thì đơn giản viết ra p bằng tổng của k hoặc ít các ước hơn của Nk : p = ji=1 di , và được khai triển P j j p X di X 1 = = q Nk Nk /di i=1 i=1 Ngược lại chuyển sang bước 3. Bước 3. Chú ý rằng đối với một vài số nguyên s và r,trong đó 0 < r < Nk chúng ta có: p pNk qs + r s r = = = + q qNk qNk Nk qNk P Bước 4. Viết s = di , trong đó di = các ước phân biệt của Nk P Viết r = di0 , trong đó di0 = các ước phân biệt của Nk P P Bước 5. Do đó được mở rộng 1/ (Nk /di ) + 1/ (qNk /di0 ) 5 Ví dụ 1.4. : 16 < 21 < 32 21 5 5 (32) = 21 21 (32) 7 (21) + 13 = 21 (32) 7 13 = + 32 21 (32) 1+2+4 1+4+8 = + 32 21 (32) 1 1 1 1 1 = + + + + 8 16 84 168 672 Định lý 1.5. Thuật toán nhị phân đảm bảo tạo ra một khai triển với D(n) < n2 và L(n) = O(log n). Chứng minh . Đầu tiên, ta đã chứng minh thuật toán làm việc ở phần đầu. Trong bước 2, chú ý rằng p < q < Nk nên pNk < qNk hay qs + r = pNk < qNk Suy ra s < Nk . 11
Do đó, chúng ta luôn luôn tìm được một mở rộng cho cả s và r. Kết quả các mẫu số của mở rộng là khác nhau bởi vì q chia tập thứ 2 của mẫu số (tương ứng với r). Nó không thể chia mẫu số tương ứng với s trừ khi q là một lũy thừa của 2. Nhưng nếu có thể,chúng ta không bao giờ nhận được qua bước 2. Vì vậy thuật này làm việc ít nhất. Trong trường hợp q = Nk , mở rộng chắc chắn có tối đa k số hạng. Trong trường hợp q < Nk , mở rộng có tối đa 2k số hạng. Vì k = log2 Nk , do đó nó có tối đa 2 log q số hạng trong khai triển. Vì vậy L(n) = O(log n). Trong trường hợp q = Nk , mẫu số lớn nhất chắc chắn là q. Trong trường hợp q < Nk , mẫu số lớn nhất có thể là q.Nk , do đó mẫu số lớn nhất phải là q(q − 1), vì vậy D(n) = O(n2 ). 1.2.2 os Thuật toán Bleicher/Erd¨ Chú ý rằng khi 2n là một số đơn giản, nó không có sự lựa chọn tốt cho số thực hành. Các số có dạng 2n là số thực hành với ít nhất số ước. Điều này dẫn đến giới hạn số các số hạng trong khai triển là log q. Rõ ràng, nếu số thực hành của chúng ta có nhiều ước số hơn, tử số có thể được viết bằng tổng của ít các ước hơn. Vì vậy số các số hạng cũng ít đi. Để tăng số ước, chúng ta có thể tránh được các yếu tố tương tự trong số thực hành của mình. Bleicher và Erd¨os Q có cách tiếp cận này trong thuật toán của họ. Ở đây họ định nghĩa Nk = k . Thuật toán như sau: p Cho phân số tối giản < 1. q Bước 1. Tìm k thỏa mãn Nk−1 < q ≤ Nk P Bước 2. Nếu q | Nk thì p/q = b/Nk và ta có thể viết b = di với mọi di | Nk Bước 3. Nếu không, thì p/q = pNk /qNk = (sq + r)/qNk = s/Nk + r/qNk , trong đó, chúng ta chỉ thực hiện với giới hạn Nk (1 − 1/k) ≤ r ≤ Nk (2 − 1/k). Số hạng s/Nk có thể được thực hiện như với b/Nk Chúng ta tìm được một mở rộng r và nhân các mẫu số của q. 12
5 Ví dụ 1.5. : Như vây k = 4 và Nk = 2.3.5.7 121 5 (2.3.5.7).5 = 121 (2.3.5.7).121 Chú ý Nk (1 − 1/k)315/2 = 157.5 và Nk (2 − 1/k) = 735/2 = 367.5. Lại có 5.(2.3.5.7)/121 = khoảng 8.7, ta được q = 7 và aNk = 7.121 + 203 Do đó 5 7 203 = + 121 2.3.5.7 (2.3.5.7).121 1 29 = + 30 (2.3.5).121 1 3 + 5 + 6 + 15 = + 30 (2.3.5).121 1 1 1 1 1 = + + + + 30 1210 726 605 242 1 1 1 1 1 = + + + + 30 242 605 726 1210 Định lý 1.6. Đối với thuật toán Bleicher Erdo¨s, D(n) = O(n(log N )3 ) Chứng minh . Ta có thể dễ dàng chứng minh bằng phương pháp quy nạp Q rằng k là thực hành, bằng cách sử dụng định lý đầu tiên trên số thực hành. Tuy nhiên Bleicher và Erdo¨s chứng minh một tuyên bố mạnh mẽ hơn: Q Bổ đề 1.1. Với mỗi số nguyên dương n ≤ σ( k ) có thể viết thành tổng của các Q ước phân biệt của k . Ở đây, σ(n) biểu thị tổng các ước của n, và rõ ràng rằng σ(n) > n. Chứng minh bổ đề này bằng phương pháp quy nạp trên k. i) Bổ đề dễ dàng được kiểm tra đúng với k = 0, 1, 2. Chẳng hạn, với k = 2, ta Q Q có k = 6 và σ( k ) = 1 + 2 + 3 + 6 = 12. Vì ta có 4 = 1 + 3, 5 = 2 + 3, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, và 11 = 6 + 2 + 3. Q ii) Giả sử bổ đề đúng với 0, 1, 2 · · · , k − 1. Tức là, nếu n ≤ σ( k−1 ) thì n có thể Q Q viết được thành tổng các ước phân biệt của k−1 . Vì vậy giả sử σ( k−1 ) < Q n ≤ σ( k ). Chú ý rằng : Y Y σ( ) = σ( ) × (Pk + 1). k k−1 13
Do đó Y Y Y σ( ) − σ( ) = Pk × σ( ) k k−1 k−1 Suy ra Y Y Y Y n − σ( ) ≤ σ( ) − σ( ) = Pk × σ( ) k k k−1 k−1 Y Y n − Pk × σ( ) ≤ σ( ) k−1 k−1 Và với k ≥ 3, ta có Y n > σ( ) ≥ 2Pk−1 > Pk . k−1 Vì vậy ta có thể tìm một số nguyên dương s thỏa mãn Y 0 < n − sPk ≤ σ(πk − 1) và 0 < s ≤ σ( ). k−1 Vì vậy, khi bổ đề đúng với k − 1, ta có thể viết X , X s= di và n − sPk di , trong đó di và d,i là các ước của k−1 và di phân biệt và d,i phân biệt. Mặt Q Q khác, vì Pk - k−1 nên chúng ta có X , n= Pk d i là thỏa mãn biểu thị cần đạt được của n.♦ Bổ đề 1.2. Cho P là một số nguyên tố và k là một số nguyên với 0 ≤ k < P. Cho k số nguyên {x1 , x2 , · · · , xk } bất kì, trong đó không có số nào chia hết cho P. Khi đó, tổng số 2k các tập con của tập {x1 , x2 , · · · , xk } nằm trong ít nhất k + 1 lớp đồng dư phân biệt mod P. Một lần nữa, chúng ta sử dụng quy nạp trên k để chứng minh bổ đề này. i) Nếu k = 0 thì chỉ có một tổng bằng 0. Vì vậy bổ đề đúng cho k = 0 ii) Giả sử bổ đề đúng cho k − 1. Sau đó gọi n bằng số các lớp đồng dư phân biệt mod P cho kết quả từ các tổng của các tập hợp con của {x1 , x2 , · · · , xk−1 } . Ta biết n ≥ (k − 1) + 1 = k. Nếu n > k ta đã làm. Vì vậy, giả sử n = k . Bây giờ ta tính kết quả của các tổng khi thêm xk vào các tổng. Nếu thu được 14
một lớp đồng dư mới, chúng ta đã chứng minh xong bổ đề. Nếu không, thì ta thấy rằng nếu chúng ta có thể đặt xk+P = · · · = xk+2 = xk+1 = xk , và nếu ta thêm vào chúng cùng một lúc thì chúng ta vẫn chỉ có k lớp đồng dư. Nhưng điều này là không thể, khi P là một số nguyên tố và P không chia hết xk .♦ Bổ đề 1.3. Nếu r là số nguyên bất kì thỏa mãn Nk (1 − 1/k) ≤ r ≤ Nk (2 − 1/k) thì có các ước phân biệt di của Nk thỏa mãn P 1. r = di 2. di ≥ cNk−3 cho hằng số c nào đó. Việc chứng minh bổ đề này thì dài và phức tạp sẽ không được trình bày, nhưng liên quan đến quy nạp theo biến k và sử dụng bổ đề 2.♦ Bổ đề 1.4. Nếu Nk−1 ≤ N ≤ Nk−1 thì ln N ln ln ln N k≤ 1+ ln ln N ln ln N Ta cũng không chứng minh bổ đề này.♦ Bây giờ chúng ta chứng minh định lý ban đầu. Nếu q|Nk , rõ ràng không có mẫu số lớn hơn Nk . Nếu không, trong bước 3 các mẫu số được ghép với số hạngs/Nk rõ ràng cũng không lớn hơn Nk , và rõ ràng chúng ta đã chứng minh xong. P Đối với số hạng r/Nk , chú ý rằng theo bổ đề 3 cho phép ta viết r = di với mọi di ≥ cNk−3 . Vì vậy mẫu số lớn nhất là qNk /cNk−3 = qPk Pk−1 Pk−2 /c. Áp dụng bổ đề 4, ta có mẫu số lớn nhất ≤ q(ln q)3 /c = O(q(q log q)3 ) Vào năm 1986, Yokota đã sửa đổi một chút thuật toán, để cho số r được thỏa mãn p Y Y 1 − 2/ Pk ≤r
trong đó λ → 1 khi n → ∞. Chứng minh này dài nên trong luận văn này cũng không trình bày. Để chỉ ra có bao nhiêu số hạng, chúng ta phải chỉ ra cần bao nhiêu số hạng Q Q để chúng ta viết N < k bằng tổng của các ước phân biệt của k . Cuối cùng, trước khi tiếp tục với thuật toán Yokota, chúng ta sẽ tìm hiểu giả thuyết của Goldbach được sử dụng như thế nào trong phân số Ai Cập. 1.2.3 Giả thuyết của Goldbach Ở đây ta chỉ ra có thể sử dụng giả thuyết của Goldbach trong phân số Ai Cập. Giả thuyết của Goldbach được xây dựng năm 1742 là Mọi số nguyên chẵn lớn hơn 2 đều là tổng của hai số nguyên tố. Điều này không được chứng minh, nhưng đã chỉ ra đúng với 2n lên tới 108 bởi Stein vào năm 1965. Cũng như vậy Chen đã chứng minh rằng: Định lý 1.7. Với mỗi số nguyên chẵn đủ lớn 2n có thể được viết dưới dạng 2n = p + m trong đó p là 1 số nguyên tố và m là tích của 2 số nguyên tố (không nhất thiết phân biệt). Cuối cùng, năm 1937 Vinograd đã chứng minh rằng: Định lý 1.8. Tồn tại số n0 thỏa mãn với mọi số n lẻ và n ≤ n0 là tổng của 3 15 số nguyên tố.n0 = 33 là thực hiện được. Vì vậy có một số bằng chứng thuyết phục là giả thuyết Goldbach là đúng, hoặc ít nhất chúng ta có thể viết một số bằng tổng của một số cố định của các số nguyên tố. Nếu chúng ta giả sử có giả thuyết Goldbach, thì chúng ta cho rằng có một số n < Pk . Nếu n là lẻ, chúng ta có thể viết n = Pa + Pb , trong đó a, b < k. Nếu các số nguyên tố không phân biệt và ta có n = Pa + Pa , thì ta có thể viết n = 2Pa = P1 Pa . Nếu n là số chẵn, thì ta có thể viết n = m + 1 với m là số lẻ và do đó n = Pa + Pb + 1 hoặc n = P1 Pa + 1. Vì vậy n có thể được viết thành tổng Q của 3 hoặc ít hơn các ước của k . Cũng chú ý rằng nếu chúng ta có n < Pk2 thì ta có thể viết n = sPk + r với s, r < Pk . Điều này có nghĩa là chúng ta có thể viết n bằng tổng của 6 hoặc ít Q hơn các ước của k . 16