ĐAI HOC QUOC GIA HÀ N®I TRƯèNG ĐAI HOC KHOA HOC TU NHIÊN NGUYEN TH± HONG NH¾T PHÂN SO AI C¾P VÀ BIEU DIEN ĐƠN V± LU¾N VĂN THAC SĨ KHOA HOC HÀ N®I - 2016 ĐAI HOC QUOC GIA HÀ N®I TRƯèNG ĐAI HOC KHOA HOC TU NHIÊN NGUYEN TH± HONG NH¾T PHÂN SO AI C¾P VÀ BIEU DIEN ĐƠN V± LU¼N VĂN THAC SĨ KHOA HOC Chuyên ngành : PHƯƠNG PHÁP TOÁN SƠ Mã so : 60 46 01 13 Giáo viên hưáng dan: TS NGUYEN VĂN NGOC HÀ N®I, 2016 CAP Mnc lnc Ma đau 1 Phân so Ai C¾p 1.1 Giói thi¾u ve xây dnng thu¾t tốn 1.1.1 Phương pháp tách .4 1.1.2 Thu¾t tốn Fibonaci-Sylvester 1.1.3 Thu¾t tốn Golomb .7 1.2 So thnc hành 1.2.1 Thu¾t tốn nh% phân .10 1.2.2 Thuắt toỏn Bleicher/Erdoăs 12 1.2.3 Gia thuyet cna Goldbach 16 1.2.4 Thu¾t tốn Yokota .17 1.2.5 Thu¾t tốn Tenenbaum/Yokota 19 1.2.6 Thu¾t tốn so thnc hành "toi ưu" .20 1.3 Các thu¾t tốn khác .22 1.3.1 Thu¾t tốn giai thùa 22 1.3.2 Thu¾t tốn Chuoi Farey 23 1.3.3 Thu¾t tốn phân so tiep dien 24 1.3.4 So sánh Thu¾t tốn 24 1.4 đ di v chắn mau so .25 1.4.1 Ch¾n mau so 25 1.4.2 Chắn đ di 28 1.4.3 đ di v chắn mau so 29 1.5 Bài toán liên quan đen so co đ%nh .31 1.6 Paul Erdăos v cỏc phõn so Ai Cắp 37 1.6.1 Giói thi¾u 38 1.6.2 Gia thuyet cna Erdăos-Straus 39 1.6.3 Các phân so Ai C¾p trù m¾t .40 1.6.4 Thêm toán tù tốn cũ, mói ket qua 41 1.6.5 Câu chun ve m®t gia thuyet khơng 46 Bieu dien đơn v% thành tong cua phân so Ai C¾p 49 2.1 Bieu dien đơn v% thành tőng cna phân so Ai C¾p vói mau so ngun dương đ¾c bi¾t .49 2.1.1 Giói thi¾u 49 2.1.2 Kien thúc chuan b% 51 2.1.3 Chúng minh Đ%nh lý 2.1 53 2.2 Bieu dien đơn v% thành tőng cna phân so đơn v% vói mau so le 55 2.2.1 Đ¾t van đe 55 2.2.2 Chúng minh Đ%nh lý 2.2 57 2.2.3 Chúng minh Đ%nh lý 2.3 59 Ket lu¾n 61 Tài li¾u tham khao 62 Ma đau Tốn HQc Ai Cắp rat ắc sac ve nhieu mắt Mđt nhung khía canh rat kỳ la cna Tốn HQc cő Ai C¾p liên quan đen "Phân so" Các nhà Tốn HQc cő Ai C¾p chi xét nhung phân so mà ta GQI "Phân so đơn v%", phân so có tu so bang mau so so nguyên dương Tai lai v¾y? e thịi Ai C¾p cő đai, ký hi¾u tốn HQc h¾ th¾p phân dna so ký hi¾u bang chu tưong hình cho moi lũy thùa cna mưịi cho đen m®t tri¾u Moi kí hi¾u so có the đưoc viet viet lai nhieu lan neu can thiet đe có the đat đưoc so mong muon Do đó, đe viet đưoc so tám mươi hay tám trăm, ký hiắu mũi hay mđt trm se oc viet tỏm lan tương úng Boi v¾y phương pháp tính tốn cna HQ khơng the xu lí hau het phân so có tu so lón 1, HQ phai viet phân so tőng cna nhieu phân so có tu so bang Các phân so đơn v% đưoc viet so nguyên vói dau cham hay kí hi¾u o bên Nhưng lu¾n văn van dùng qui ưóc thơng dung đe viet phân so Đe viet phân , nhà Tốn HQc cő Ai C¾p khơng the viet + theo 5 so quy ưóc viet so lúc đó, phân so đơn v% chi oc the hiắn mđt lan Thay vỡ 1 1 viet + phân so đưoc viet + Trong tốn HQc cő Ai C¾p ngồi cách 5 15 dùng phân so đơn v%, m®t so phân so thơng dung HQ quy ưóc viet bang mđt so kớ tn ắc biắt Trong luắn li¾t kê thu¾t tốn đe viet phân so bang tőng phân so đơn v%.Tuy nhiên moi m®t phân so khơng có nhat m®t bieu dien phân so đơn v%, có sn phân tích toi ưu giua thu¾t tốn Lu¾n văn nghiên cúu vi¾c bieu dien phân so thành tőng phân so đơn v% thêm đieu ki¾n co đ%nh, so so hang, hay mau so lón nhat Ngồi lu¾n văn cịn nghiên cúu lịi giai cna tốn ve phương trình Diophantine m®t so trưịng hop Đ¾c bi¾t bieu dien đơn v % thành tőng phân so đơn v% Đe thnc hi¾n lu¾n văn tác gia chn yeu thu th¾p nghiên cúu tù nguon tài li¾u khác nhau, roi phân tích thu¾t tốn đưa ví du minh HQA cu the Nhung tài li¾u ve phân so Ai C¾p bang Tieng Vi¾t rat Do neu lu¾n văn oc thnc hiắn thnh cụng thỡ nú cng l mđt tài li¾u tham khao bő ích cho giáo viên HQc sinh Cau trúc cna lu¾n văn đưoc chia thành ba phan: phan mo đau, phan n®i dung phan ket luắn Nđi dung luắn oc chia lm hai chương: Chương Phân so Ai C¾p Chương Bieu dien đơn v% thành tong phân so đơn v% Trong thịi gian thnc hi¾n lu¾n văn, tác gia nh¾n đưoc sn hưóng dan chi bao t¾n tình cna TS Nguyen Văn NGQc Qua đây, tác gia xin đưoc bày to lòng biet ơn sâu sac trân TRQNG nhung cơng lao, sn quan tâm, đ®ng viên sn t¾n tình chi bao cna Thay Tác gia chân thành cam ơn thay, khoa Tốn - Cơ - Tin HQc Trưòng Đai HQc Khoa HQc Tn nhiên, ĐHQG h Nđi ó day bao tắn tỡnh, cỏc thay cụ giáo Ban giám hi¾u, Phịng Đào tao, Văn phịng Khoa Tốn Cơ - Tin HQc trưịng Đai HQc Khoa HQc Tn nhiên - Đai HQc Quoc gia Hà N®i tao MQI đieu ki¾n tot nhat suot thịi gian tác gia HQc t¾p hồn thi¾n lu¾n văn H Nđi ngy 01/12/2016 HQc viờn Nguyen Th% Hong Nhắt Chương Phân so Ai C¾p 1.1 Giái thi¾u ve xõy dEng thuắt toỏn Mđt nhung van e c ban liên quan đen phân so Ai C¾p sn tìm kiem xây dnng thu¾t tốn-cách đe viet bat kỳ phân so thành tőng cna phân so đơn v%, túc nhung phân so có tu so bang mau so nhung so nguyên dương Qua nhieu năm, có nhieu thu¾t tốn khác xây dnng cho muc đích khác nhau, chúng bao gom tù thuan túy lý thuyet tói thnc hành Rõ ràng vói moi m®t phân so bat kỳ có nhieu mơt cách mo r®ng thành phân so Ai C¾p phân bi¾t Neu a su dung h¾ thúc b x ta thu đưoc a b = = = n x1 x+ +···+ + x , x(x + 1) 1 + + +···+ n− xn + xn (xn + 1) x1 x Ngưịi Ai C¾p có the cú hoắc khụng cú mđt thuắt toỏn e xõy dnng mo r®ng phân so HQ tao m®t ban mo r®ng cna so cho tat ca so le n