ĐẠ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
1.1 Giới thiệu về xây dựng thuật toán . . . .
1.1.1 Phương pháp tách . . . . . . . . .
1.1.2 Thuật toán Fibonaci-Sylvester . .
1.1.3 Thuật toán Golomb . . . . . . . . .
1.2 Số thực hành . . . . . . . . . . . . . . . . .
1.2.1 Thuật toán nhị phân . . . . . . . .
1.2.2 Thuật toán Bleicher/Erdös . . . .
1.2.3 Giả thuyết của Goldbach . . . . .
1.2.4 Thuật toán Yokota . . . . . . . . .
1.2.5 Thuật toán Tenenbaum/Yokota . .
1.2.6 Thuật toán số thực hành "tối ưu"
1.3 Các thuật toán khác . . . . . . . . . . . .
1.3.1 Thuật toán giai thừa . . . . . . . .
1.3.2 Thuật toán Chuỗi Farey . . . . .
1.3.3 Thuật toán phân số tiếp diễn . . .
1.3.4 So sánh Thuật toán . . . . . . . .
1.4 Độ dài và chặn mẫu số . . . . . . . . . . .
1.4.1 Chặn mẫu số . . . . . . . . . . . .
1.4.2 Chặn độ dài . . . . . . . . . . . . .
1.4.3 Độ dài và chặn mẫu số . . . . . . .
1.5 Bài toán liên quan đến số cố định . . . .
1.6 Paul Erdös và các phân số Ai Cập . . . .
1.6.1 Giới thiệu . . . . . . . . . . . . . .
1.6.2 Giả thuyết của Erdös-Straus . . .
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
4
5
7
9
10
12
16
17
19
20
22
22
23
24
24
25
25
28
29
31
37
38
39
1.6.3
1.6.4
1.6.5
Các phân số Ai Cập trù mật . . . . . . . . . . . . . . . . . 40
Thêm các bài toán từ bài toán cũ, mới và kết quả . . . . . 41
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
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 . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . .
2.1.3 Chứng minh Định lý 2.1 . . . . . . . . . . . . . . . . . . .
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ẻ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Chứng minh Định lý 2.2 . . . . . . . . . . . . . . . . . . .
2.2.3 Chứng minh Định lý 2.3 . . . . . . . . . . . . . . . . . . .
49
.
.
.
.
49
49
51
53
.
.
.
.
55
55
57
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
1
a
1
=
+ ··· +
b
x1
xn
thì sử dụng hệ thức
ta thu được
1
1
1
=
+
,
x
x + 1 x(x + 1)
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<100.
n
Gill đã thảo luận về một số tiêu chí khác nhau mà người Ai Cập có thể sử dụng
p
để tạo bảng. Trong bản luận văn này, ta chỉ quan tâm đến các phân số < 1.
q
Vì vậy ở bất cứ chỗ nào chưa được quy định rõ ràng thì ta coi như trong trường
hợp này.
Trước khi bắt đầu, ta sẽ tóm tắt một số các kí hiệu mà sẽ được sử dụng trong
bản Luận văn
3
Kí hiệu
Giả sử
p
1
1
=
+ ··· + ,
q
n1
nk
n1 < n2 < · · · < 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
• S
k
= P1 .P2 . . . Pk
= {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".
Cho phân số hữu tỷ
Bước1. Viết
p
< 1.
q
p
1
bằng tổng của phân số đơn vị
q
q
4
1
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
Bước 2. Nếu có hai phân số giống nhau
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.
Ví dụ 1.1.
3
7
3
7
=
=
=
=
=
1.1.2
1
7
1
7
1
7
1
7
1
7
1 1
+
7 7
1
1
1
1
+
+
+
+
8 56
8 56
1 1
1
1
+ + +
+
8
8 56 56
1
1
1
1
1
1
+ +
+
+
+
+
8
9 72
56
57 3192
1 1
1
1
1
+ + +
+
+
.
8 9 56 72 3192
+
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
Cho phân số tối giản
p
< 1.
q
Bước 1. Kí hiệu p0 = p và q 0 = q.
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
Bước 3. Chú ý rằng
p0
1
p0 − r
1
=
+
. Vì vậy
là một phần của khai
0
0
q
s + 1 q (s + 1)
s+1
triển.
Bước 4. Đặt p0 = p0 − r và q 0 = q 0 (s + 1) .
Bước 5. Rút gọn phân số
p0
về phân số tối giản và quay lại bước 2.
q0
5
Ví dụ 1.2.
3
7
1
2
+
3 21
1
1
1
= +
+
.
3 11 231
=
Giải thích. Ở đây p0 = p = 3, q 0 = q = 7. Ta có
7 = 2.3 + 1, s = 2, r = 1,
1
p0 − r
1
2
3
=
+ 0
= + .
7
s + 1 q (s + 1)
3 21
Tiếp theo, ta có p0 = 2, q 0 = 21. Ta có
21 = 10.2 + 1, s = 10, r = 1,
2
1
p0 − r
1
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
1
p0 − r
p0
=
+
.
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ể:
Khi
p0
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:
1
1
1
5
=
+
+
.
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ì
1
1
4
=
+
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:
1.1.3
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
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
Cho phân số tối giản
p
< 1.
q
Bước 1: Đặt p0 = p và q 0 = q
Bước 2: Nếu p0 = 1, đặt
p0
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 )
Bước 4: Lưu ý
p0
1
r
1
= 00 0 + 00 . Vì vậy 00 0 là một số hạng của khai triển.
0
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
7
2
1
+
5 35
1
1
1
= +
+
3 15 35
=
Giải thích. Ở đây p0 = p = 3, q 0 = q = 7. Ta có
3.5 = 7.2 + 1, p00 = 5, r = 2,
3
1
r
1
2
= 00 0 + 00 =
+ .
7
p q
p
35 5
Tiếp theo, ta có p0 = 2, q 0 = 5. Ta có
2.3 = 5.1 + 1, p00 = 3, r = 1,
2
1
r
1
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ó
1
1
1
3
= +
+ .
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
Dễ thấy rằng nếu p có thể viết bằng tổng các ước của q thì
p
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
= + +· · ·+
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à D1 + D2 + · · · + Dk = 0
và N và các ước D1 , · · · , Dk của N thỏa mãn
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
Định lý 1.3.
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 (12)
5
=
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
P
của Nk : p = ji=1 di , và được khai triển
j
j
i=1
i=1
X 1
p X di
=
=
q
Nk
Nk /di
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ó:
pNk
p
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 )
Ví dụ 1.4.
5
:
21
16 < 21 < 32
5
21
=
=
=
=
=
5 (32)
21 (32)
7 (21) + 13
21 (32)
13
7
+
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
Thuật toán Bleicher/Erdös
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ös
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
Bước 2. Nếu q | Nk thì p/q = b/Nk và ta có thể viết b =
P
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
Ví dụ 1.5.
5
: Như vây k = 4 và Nk = 2.3.5.7
121
(2.3.5.7).5
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 đó
7
203
5
=
+
121
2.3.5.7 (2.3.5.7).121
1
29
=
+
30 (2.3.5).121
3 + 5 + 6 + 15
1
+
=
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 Erdö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à Erdö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
σ(
) = σ(
k
k−1
13
) × (Pk + 1).
Do đó
σ(
Y
Y
k
k−1
) − σ(
) = Pk × σ(
Y
)
k−1
Suy ra
Y
Y
k
k
n − σ(
) ≤ σ(
) − σ(
Y
) = Pk × σ(
k−1
n − Pk × σ(
Y
) ≤ σ(
k−1
Y
)
k−1
Y
)
k−1
Và với k ≥ 3, ta có
n > σ(
Y
) ≥ 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
0 < n − sPk ≤ σ(πk − 1) và 0 < s ≤ σ(
Y
).
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 ,
Q
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
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
Y
p Y
1 − 2/
≤r<2
Pk
k
k
Sử dụng thuật toán được sửa đổi này, Yokota chứng minh rằng:
L(N ) ≤
4 log N
log log N
1+
log log log N
log log N
và
D(N ) ≤ λN (log N )2 ,
15
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
- Xem thêm -