Tài liệu Về bài toán diophantine tuyến tính của frobenius

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐỖ THỊ THU HIỀN VỀ BÀI TOÁN DIOPHANTINE TUYẾN TÍNH CỦA FROBENIUS Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. LÊ THỊ THANH NHÀN Thái Nguyên - NĂM 2013 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐỖ THỊ THU HIỀN VỀ BÀI TOÁN DIOPHANTINE TUYẾN TÍNH CỦA FROBENIUS Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. LÊ THỊ THANH NHÀN Thái Nguyên - Năm 2013 1 LỜI CAM ĐOAN Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên. Dưới sự hướng dẫn của PGS.TS. Lê Thị Thanh Nhàn. Tôi xin cam đoan các kết quả được trình bày trong luận văn là do tôi làm và không sao chép các luận văn đã được công bố trước đó. Tác giả Đỗ Thị Thu Hiền 2 Mục lục LỜI CẢM ƠN 3 LỜI NÓI ĐẦU 4 1 GIỚI THIỆU BÀI TOÁN FROBENIUS 1.1 Bài toán đổi tiền của Frobenius . . . . . . . . . . . . . . . . 1.2 Số Frobenius và sự tồn tại của nó . . . . . . . . . . . . . . 6 6 8 2 BÀI TOÁN FROBENIUS - TRƯỜNG HỢP HAI SỐ 13 2.1 Định lí hai đồng xu . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Định lí Sylvester về công thức tính n (a, b) . . . . . . . . . . 19 3 BÀI TOÁN FROBENIUS VỚI 3 SỐ 22 3.1 Trường hợp 3 số nguyên tố cùng nhau đôi một . . . . . . . 23 3.2 Vài kết quả trong lịch sử giải bài toán Frobenius . . . . . . 32 Kết luận 36 Tài liệu tham khảo 37 3 LỜI CẢM ƠN Sau quá trình nhận đề tài và nghiên cứu dưới sự hướng dẫn khoa học của PGS. TS Lê Thị Thanh Nhàn, luận văn "Về bài toán Diophantine tuyến tính của Frobenius" của tôi đã được hoàn thành. Có được kết quả này, đó là nhờ sự dạy bảo hết sức tận tình và nghiêm khắc của Cô. Tôi xin bày tỏ lòng biết ơn sâu sắc tới Cô và gia đình! Tôi cũng xin gửi lời cảm ơn chân thành đến Ban Giám hiệu, Phòng Đào Tạo - Khoa học - Quan hệ quốc tế và Khoa Toán - Tin của Trường Đại học Khoa học - Đại học Thái Nguyên đã tạo điều kiện thuận lợi nhất trong suốt quá trình học tập tại trường cũng như thời gian tôi hoàn thành đề tài này. Sự giúp đỡ nhiệt tình và thái độ thân thiện của các cán bộ thuộc Phòng Đào tạo và Khoa Toán - Tin đã để lại trong lòng mỗi chúng tôi những ấn tượng hết sức tốt đẹp. Tôi xin cảm ơn Trường PT Vùng cao Việt Bắc - nơi tôi đang công tác đã tạo điều kiện cho tôi hoàn thành khóa học này. Tôi xin cảm ơn gia đình, bạn bè đồng nghiệp và các thành viên trong lớp cao học Toán K5A (Khóa 2011 - 2013) đã quan tâm, tạo điều kiện, động viên cổ vũ để tôi có thể hoàn thành nhiệm vụ của mình. 4 LỜI NÓI ĐẦU Mục đích của luận văn là trình bày lại một cách tương đối hệ thống một vài kết quả quan trọng về bài toán Diophantine tuyến tính của Frobenius (còn gọi là bài toán Frobenius). Bài toán: Cho trước k số nguyên dương a1 , ..., ak nguyên tố cùng nhau. Xác định số nguyên lớn nhất g (a1 , ..., ak ) không là tổ hợp tuyến tính không âm của a1 , ..., ak , tức là không thể viết dưới dạng m1 a1 + ... + mk ak với m1 , ..., mk là các số nguyên không âm. Số g (a1 , ..., ak ) trong bài toán trên được gọi là số Frobenius. Bài toán Frobenius có những ứng dụng quan trọng trong nhiều lĩnh vực khác nhau của Toán học như Lí thuyết số, Lí thuyết tự động và Tổ hợp. Đặc biệt, bài toán Frobenius đã được sử dụng để phân tích các mạng Petri, để nghiên cứu bài toán phân loại các không gian véc tơ, các nhóm Aben, để nghiên cứu các mật mã hình học đại số thông qua tính chất của các nửa nhóm đặc biệt, để nghiên cứu các bài toán xếp hình... Một ví dụ nổi tiếng về bài toán Frobenius là "bài toán đổi tiền của Frobenius": Cho trước k loại tiền với các mệnh giá là các số tự nhiên nguyên tố cùng nhau, xác định khoản tiền lớn nhất không thể đổi thành các loại tiền trên. Trong các cuốn sách về số học sơ cấp, chúng ta tìm thấy nhiều ví dụ dạng như: tìm khoản tiền lớn nhất không thể đổi được thành các loại tiền mệnh giá 3 xu, 5 xu, 7 xu. Bài toán Frobenius đã được giải quyết trọn vẹn cho trường hợp hai số. Từ những năm 1890, người ta đã biết công thức tính số Frobenius của hai số tự nhiên a, b nguyên tố cùng nhau là ab − b − a. Bên cạnh đó, người ta cũng xác định được công thức tính số các số nguyên dương không biểu 1 diễn được qua a, b là (a − 1) (b − 1) . Vì thế, rất tự nhiên, nhiều nhà 2 toán học quan tâm đến việc mở rộng bài toán Frobenius cho trường hợp từ 3 số trở lên. Tuy nhiên việc giải quyết cho trường hợp nhiều hơn hoặc 5 bằng 3 số là vô cùng khó, nó đã và đang thách thức các nhà toán học trong suốt thời gian dài và cho đến nay vẫn là bài toán mở. Luận văn gồm 3 chương. Trong chương 1, chúng tôi giới thiệu sơ lược về bài toán Frobenius và chứng minh sự tồn tại số Frobenius g (a1 , ..., ak ). Chương 2, trình bày lời giải trọn vẹn cho bài toán Frobenius trong trường hợp hai số, trong đó có công thức tính số Frobenius g (a, b) (Định lí 2.1.1) và công thức tính n (a, b) - số các số nguyên dương không biểu diễn được qua a, b (Định lí 2.2.2). Phần đầu Chương 3 dành để chứng minh một kết quả nổi bật cho bài toán Frobenius trong trường hợp 3 số (Định lí 3.1.3). Phần cuối Chương 3 trình bày sơ lược những thành tựu và các hướng nghiên cứu tiếp theo đối với bài toán Frobenius cho trường hợp từ 3 số. Các kết quả và thông tin trong luận văn được viết chủ yếu dựa vào cuốn sách của J. L. Alfonsin "The diophantine Frobenius problem" xuất bản bởi Oxford University Press năm 2005, cuốn sách của Jefrey Shallit "The Frobenius Problem and Its Generalizartion" xuất bản bởi Springer năm 2008, và bài báo của F. Curtis "On formulas for the Frobenius number of a numerical semigroup" đăng trên Math. Scand. năm 1990. 6 Chương 1 GIỚI THIỆU BÀI TOÁN FROBENIUS Ferdinand Georg Frobenius (26/10/1849 - 03/08/1917) là một nhà toán học người Đức nổi tiếng với những đóng góp trong lí thuyết các hàm Eliptic, phương trình vi phân và lí thuyết nhóm. Ông được giới khoa học biết đến vì phát minh ra những đồng nhất định thức gọi là các công thức FrobeniusStickelberger. Ông đã có nhiều đóng góp quan trọng trong việc phát triển lí thuyết dạng song toàn phương và là người đầu tiên giới thiệu khái niệm xấp xỉ hữu tỷ cho các hàm (ngày nay gọi là xấp xỉ Pade). Ông là người đưa ra chứng minh đầy đủ đầu tiên cho Định lí Cayley-Hamilton. Tên của Ông đã được đặt cho một số đối tượng hình học trong Vật lí Toán hiện đại, chẳng hạn như "Đa tạp Frobenius", vì Ông đã có những đóng góp quan trọng trong lĩnh vực này. 1.1 Bài toán đổi tiền của Frobenius Alfred Brauer (1894-1985) đã viết trong bài báo [Bra] đăng năm 1942 rằng Ferdinand Georg Frobenius (1849 - 1917), một nhà toán học người Đức, là người đã vài lần giới thiệu bài toán sau đây trong các bài giảng của mình vào những năm 1880, nhưng Frobenius không công bố trong bất cứ tài liệu nào. Bài toán Frobenius: Cho trước k số nguyên dương a1 , ..., ak nguyên tố cùng nhau. Xác định số nguyên lớn nhất g (a1 , ..., ak ) không là tổ hợp tuyến tính không âm của a1 , ..., ak , tức là không thể viết dưới dạng tổ hợp 7 tuyến tính m1 a1 + ... + mk ak với m1 , ..., mk là các số nguyên không âm. Alfred Brauer (là học trò của Isaac Shur và cũng là học trò của Georg Frobenius) đã đầu tư công sức để giải quyết bài toán Frobenius trong suốt hơn 10 năm sau đó (từ 1942 đến 1954 - xem bài báo của Alfred Brauer và B. M. Seelbinder: On a problem of partitions, American Journal of Mathematics, 76 (1954), 343-346). Một ví dụ nổi tiếng về bài toán Frobenius là "bài toán đổi tiền của Frobenius": Cho trước k loại tiền với các mệnh giá là các số tự nhiên nguyên tố cùng nhau, xác định khoản tiền lớn nhất không thể đổi thành các loại tiền trên. Hình 1.1. Nguồn internet Chẳng hạn, trong các cuốn sách về số học sơ cấp, chúng ta tìm thấy nhiều ví dụ dạng như: a) Tìm khoản tiền lớn nhất không thể đổi được thành các loại tiền mệnh giá 2 xu và 5 xu (Đáp án: 3 xu). b) Tìm khoản tiền lớn nhất không thể đổi được thành các loại tiền mệnh giá 3 xu, 5 xu và 7 xu (Đáp án: 4 xu). Vào năm 1972, nhiều kết quả quan trọng về bài toán Frobenius được công bố. Một số kết quả tiêu biểu được viết trong bài báo của P. Erdos và E. L. Graham, On a linear diophantine problem of Frobenius, Acta Arithmetica, 45 (1972), 399-408. Và từ đó bài toán Frobenius còn được gọi là "bài toán Diophantine tuyến tính của Frobenius". Một ví dụ nổi tiếng khác là bài toán mua một miếng gà chiên (Hình 1.2): tại một quán ăn nhanh, gà chiên được bán thành các loại gói đóng sẵn, bao gồm gói 6 miếng, gói 9 miếng và gói 20 miếng. Tìm số miếng gà chiên nhiều nhất không thể mua được tại quán ăn này (Đáp án: 43 miếng). 8 Hình 1.2. Nguồn internet 1.2 Số Frobenius và sự tồn tại của nó Trong tiết này, cho trước k số nguyên dương a1 , ..., ak nguyên tố cùng nhau (tức là gcd (a1 , ..., ak ) = 1). Một tổ hợp tuyến tính không âm của a1 , ..., ak là một số nguyên n dạng n = m1 a1 + ... + mk ak với m1 , ..., mk là các số nguyên không âm. 1.2.1. Định nghĩa. Số nguyên lớn nhất không là tổ hợp tuyến tính không âm của các số nguyên a1 , ..., ak được gọi là số Frobenius ứng với bộ số a1 , ..., ak . Theo Matthias Beck and Sinai Robins [BR], số Frobenius ứng với bộ số a1 , ..., ak được kí hiệu là g (a1 , ..., ak ). Chú ý rằng mọi số nguyên x lớn hơn số Frobenius g (a1 , ..., ak ) đều biểu diễn được dạng: x = a1 x1 + a2 x2 + ... + ak xk với x1 , ..., xk là các số nguyên không âm. Ta gọi những số nguyên viết được thành tổ hợp tuyến tính không âm của a1 , ..., ak là những số biểu diễn được qua bộ số a1 , ..., ak . 1.2.2. Ví dụ. Số Frobenius ứng với 2 và 5 là 3. Thật vậy, rõ ràng 3 không biểu diễn được qua 2 và 5. Cho x > 3. Nếu x chẵn thì x là bội của 2 và do đó nó biểu diễn được qua 2 và 5. Nếu x lẻ thì x = 5 + y , trong đó y là một số chẵn. Vì thế x cũng biểu diễn được qua 2 và 5. Vậy g (2, 5) = 3. 1.2.3. Ví dụ. Số Frobenius ứng với 3, 5, 7 là 4. Thật vậy, ta cần chứng 9 minh 4 không biểu diễn được qua 3, 5, 7 và mọi số tự nhiên lớn hơn 4 đều biểu diễn được qua 3, 5, 7. Giả sử 4 biểu diễn được qua 3, 5 và 7. Khi đó tồn tại các số nguyên không âm m, n, p sao cho 4 = 3m + 5n + 7p Suy ra n = p = 0. Do đó 4 = 3m, tức là 4 là bội của 3, vô lí. Vậy 4 không biểu diễn được qua 3, 5, 7. Cho x > 4 là một số tự nhiên. Trường hợp 1: Nếu x chia hết cho 3 thì x = 3m và do đó x = 3m + 5 × 0 + 7 × 0 là tổ hợp tuyến tính không âm của 3, 5, 7. Trường hợp 2: Nếu x chia cho 3 dư 1 thì x ≥ 7 và x = 3t + 1, do đó t ≥ 2, vì thế x = 3 (t − 2) + 7 = 3 (t − 2) + 5 × 0 + 7 × 1 là tổ hợp tuyến tính không âm của 3, 5, 7. Trường hợp 3: Nếu x chia cho 3 dư 2 thì x ≥ 5 và x = 3s + 2, do đó s ≥ 1 và vì thế x = 3 (s − 1) + 5 = 3 (s − 1) + 5 × 1 + 7 × 0 là tổ hợp tuyến tính không âm của 3, 5, 7. Như vậy, số 4 là số nguyên dương lớn nhất không biểu diễn được qua 3, 5, 7, tức là g (3, 5, 7) = 4. 1.2.4. Ví dụ. Tại một quán ăn nhanh có bán các loại gà chiên đóng thành các gói loại 6 miếng, 9 miếng và 20 miếng. Khi đó số miếng gà chiên nhiều nhất mà chúng ta không thể mua được tại quán ăn này là 43 chiếc. Chứng minh. Ta cần chỉ ra rằng số Frobenius ứng với 6, 9, 20 là 43, tức là cần chứng minh 43 là số nguyên lớn nhất không biểu diễn được qua 6, 9, 20. Thật vậy, giả sử 43 biểu diễn được qua 6, 9, 20. Khi đó tồn tại các số nguyên không âm m, n, p sao cho thì 43 = 6m + 9n + 20p. Khi đó p ≤ 2. Nếu p = 2 thì 3 = 6m + 9n thì là điều vô lí. Do đó p ≤ 1. Nếu p = 1 thì 23 = 6m + 9n, điều này là vô lí vì 6m + 9n chia hết cho 3 nhưng 23 không chia hết cho 3. Do đó p = 0, suy ra 43 = 6m + 9n, điều này cũng vô lí vì 43 không chia hết cho 3, trong khi đó 6m + 9n chia hết cho 3. Như 10 vậy, 43 không thể biểu diễn thành tổ hợp tuyến tính không âm của 6, 9, 20. Bây giờ ta chứng minh rằng nếu a là số nguyên lớn hơn 43 thì a biểu diễn được qua 6, 9, 20. Ta viết a = 44 + b, trong đó b ≥ 0 là một số tự nhiên. Chia b cho 6 ta được b = 6t + r, trong đó t ≥ 0 là một số tự nhiên và r = 0, 1, 2, 3, 4, 5. Vì thế a = 44 + b = 6t + 44 + r. Nếu r = 0 thì a = 6t + 44 = 6 (t + 4) + 0 × 9 + 1 × 20, do đó a biểu diễn được qua 6, 9, 20. Nếu r = 1 thì a = 6t + 45 = 6 (t + 3) + 3 × 9 + 0 × 20, do đó a biểu diễn được qua 6, 9, 20. Nếu r = 2 thì a = 6t + 46 = 6 (t + 1) + 0 × 9 + 2 × 20, do đó a biểu diễn được qua 6, 9, 20. Nếu r = 3 thì a = 6t + 47 = 6t + 3 × 9 + 1 × 20, do đó a biểu diễn được qua 6, 9, 20. Nếu r = 4 thì a = 6t + 48 = 6 (t + 8) + 0 × 9 + 0 × 20, do đó a biểu diễn được qua 6, 9, 20. Nếu r = 5 thì a = 6t + 49 = 6t + 1 × 9 + 2 × 20, do đó a biểu diễn được qua 6, 9, 20. Như vậy, trong mọi trường hợp, a đều biểu diễn được qua 6, 9, 20. Vì thế g (6, 9, 20) = 43. Mặc dù ta thấy rằng có những số nguyên biểu diễn được và có những số không biểu diễn được, nhưng các câu hỏi sau rất cần được được giải quyết: a) Có hay không số nguyên lớn nhất không biểu diễn được qua a1 , ..., ak ? b) Có bao nhiêu số tự nhiên không biểu diễn được qua các số a1 , ..., ak ? Rõ ràng câu trả lời cho câu hỏi a) là "có" khi và chỉ khi số Frobenius tồn tại, khi và chỉ khi câu trả lời cho câu hỏi b) là "chỉ có hữu hạn số". Mục đích của tiết này là chứng minh rằng số Frobenius luôn tồn tại trong trường hợp các số tự nhiên a1 , ..., ak là nguyên tố cùng nhau. 11 1.2.5. Mệnh đề. Nếu gcd (a1 , ..., ak ) = 1 và ai > 1 với mọi i thì số Frobenius g (a1 , ..., ak ) luôn tồn tại. Chứng minh. Vì gcd (a1 , ..., ak ) = 1 nên tồn tại các số nguyên m1 , ..., mk sao cho 1 = m1 a1 + ... + mk ak . Không mất tính tổng quát ta có thể đánh số các chỉ số của các số nguyên a1 , ..., ak sao cho m1 , ..., mk < 0 và mt+1 , ..., mk ≥ 0, trong đó 0 ≤ t ≤ k . Đặt x = (1 − a1 ) m1 a1 + ... + (1 − a1 ) mt at . Vì ai > 1 và mi < 0 nên (1 − a1 ) mi > 0 với mọi i = 1, ..., t. Do đó đẳng thức trên chứng tỏ x biểu diễn được thành tổ hợp tuyến tính không âm của a1 , ..., at và do đó nó biểu diễn được qua a1 , ..., ak . Cho y là một số tự nhiên lớn hơn x. Viết y = x + z , trong đó z ≥ 1. Viết z = a1 p + r, trong đó p ≥ 0 là một số tự nhiên và 0 ≤ r < a1 . Vì r = r ×1 = rm1 a1 +...+rmk ak nên ta có y = x + a1 p + r = (1 − a1 ) m1 a1 + ... + (1 − a1 ) mt at + a1 p + r = [(1 + r − a1 ) m1 + p] a1 + (1 + r − a1 ) m2 a2 + ... + (1 + r − a1 ) mt at +rmt+1 at+1 + ... + rmk ak . Vì r < a1 và mi < 0 nên (1 + r − a1 ) mi ≥ 0 với mọi i = 1, ..., t. Hơn nữa, do p ≥ 0 và mt+1 , ..., mk ≥ 0 nên đẳng thức trên chứng tỏ y biểu diễn được thành tổ hợp tuyến tính không âm của a1 , ..., ak . Vì mỗi ai > 1 nên 1 không thể là tổ hợp tuyến tính không âm của a1 , ..., ak . Do đó trong các số từ 1 đến x − 1, ắt phải có số nguyên dương lớn nhất không biểu diễn được qua a1 , ..., ak . Từ mệnh đề trên ta thấy rằng chỉ có hữu hạn số nguyên không biểu diễn được qua các số a1 , ..., ak . Vì thế người ta quan tâm đến bài toán Frobenius ở hai khía cạnh. Thứ nhất là tìm số Frobenius, tức là tìm số nguyên lớn nhất không biểu diễn được qua a1 , ..., ak . Thứ hai là xác định xem có bao nhiêu số nguyên dương không biểu diễn được qua a1 , ..., ak . Theo Matthias Beck and Sinai Robins [BR], kí hiệu n (a1 , ..., ak ) là các số nguyên dương không biểu diễn được qua a1 , ..., ak . Ta có n (2, 5) = 2 vì có đúng 2 số tự nhiên không biểu diễn được qua 2 và 5, đó là 1 và 3; ta có 12 n (3, 5, 7) = 3 vì có đúng 3 số tự nhiên không biểu diễn được qua 3, 5, 7, đó là 1 , 2, 4; ta có n (6, 9, 20) = 22 vì có đúng 22 số tự nhiên không biểu diễn được qua 6, 9, 20, đó là các số 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43. Khi k = 1, từ điều kiện về ước chung lớn nhất ta có a1 = 1. Do đó không có số nguyên dương nào không là tổ hợp tuyến tính không âm của a1 . Vì thế từ nay về sau chúng ta chỉ cần quan tâm cho trường hợp k ≥ 2. 13 Chương 2 BÀI TOÁN FROBENIUS TRƯỜNG HỢP HAI SỐ Định lí hai đồng xu (the two-coin Theorem) phát biểu rằng nếu a, b là hai số nguyên dương nguyên tố cùng nhau thì số Frobenius g (a, b) được cho bởi công thức sau: g (a, b) = ab − a − b. Nguồn gốc của hai Định lí hai đồng xu không còn tìm thấy trong lịch sử toán học. Trong [BR], Matthias Beck và Sinai Robins đã viết: " Định lí hai đồng xu là một trong những kết quả nổi tiếng của lịch sử Toán học và cũng là một trong những kết quả nổi tiếng của lịch sử Toán học và cũng là một trong những định lí có lỗi trích dẫn nhiều nhất trong Toán học (ngay cả trong luận văn này, hầu hết các cuốn sách và bài báo ở phần tài liệu tham khảo đều trích dẫn Định lí hai đồng xu là James J. Sylvester, điều này không đúng). Khi nhắc đến Định lí hai đồng xu, mọi người thường trích dẫn bài toán James J. Sylvester trong [Sy]. Tuy nhiên kết quả trong bài báo của Sylvester [Sy] là Định lí Sylvester phát biểu rằng "Số các số 1 nguyên dương không biểu diễn được qua a và b là (a − 1) (b − 1)", chứ 2 không phải là Định lí hai đồng xu. Thực tế, bài toán của Sylvester đã xuất hiện trước Định lí hai đồng xu. Đến nay không có tài liệu nào khẳng định ai là người đã phát minh hoặc đã đưa ra chứng minh đầu tiên cho Định lí hai đồng xu. Tuy nhiên chúng ta có thể đoán rằng Sylvester đã biết điều này khi Ông làm việc với Sylvester [Sy]". Mục đích của chương này là chứng minh Định lí hai đồng xu về công thức tính số Frobenius g (a, b) và Định lí Sylvester về số n (a, b) (số các số 14 nguyên dương không biểu diễn được qua a, b). 2.1 Định lí hai đồng xu Có nhiều chứng minh cho Định lí hai đồng xu. Chẳng hạn, J. L. R. Alfonsin đã đưa ra 4 chứng minh cho định lí này trong cuốn sách [A] xuất bản năm 2005; Matthias Beck và Siani Robins còn chỉ ra một chứng minh khác trong cuốn sách [BR] xuất bản năm 2007. Rất có thể có nhiều cách chứng minh khác chưa được khám phá. Trong tiết này, chúng ta đưa ra hai chứng minh gần đây. Chứng minh thứ nhất được Curtis Kifer viết trong bài báo [K] năm 2010. Chứng minh thứ hai được Jeffrey Shallit viết trong cuốn sách [Sh] năm 2008. Các chứng minh này khác với 5 chứng minh của Alfonsin, Beck và Robins đã nói ở trên. Đặc biệt, chứng minh thứ hai còn cho ta một thuật toán hữu hiệu để biểu diễn các số lớn hơn số Frobenius g (a, b) thành tổ hợp tuyến tính không âm của a và b. 2.1.1. Định lý.(Định lí hai đồng xu.) Nếu a, b là hai số nguyên dương nguyên tố cùng nhau thì g (a, b) = ab − a − b. Để đưa ra chứng minh thứ nhất cho Định lí hai đồng xu (xem Curtis Kier [K]), ta nhắc lại một số khái niệm và tính chất về đồng dư thức. với một số nguyên dương a, một hệ gồm a số nguyên được gọi là một hệ thặng dư đầy đủ theo môđun a nếu hai số nguyên bất kì trong hệ đó không đồng dư với nhau theo môđun a. Chẳng hạn, hệ gồm 5 số nguyên {0, 1, 2, 3, 4}; hệ gồm 3 số nguyên {−3, 10, −7} là một hệ thặng dư đầy đủ môđunlô 3. 2.1.2. Bổ đề. Cho a, b là hai số nguyên dương nguyên tố cùng nhau. Khi đó {0b, 1b, 2b, ..., (a − 1) b} là một hệ thặng dư đầy đủ theo môđun a. Chứng minh.. Rõ ràng hệ {0b, 1b, 2b, ..., (a − 1) b} gồm a số. Do đó ta chỉ cần chứng minh hai số bất kì trong hệ này không đồng dư với nhau theo môđun a. Lấy 0 ≤ i < j ≤ a − 1. Nếu ib đồng dư với jb theo môđun a thì ta có (j − i) b là bội của a. Do a và b nguyên tố cùng nhau nên j − i chia hết cho a, điều này là vô lí vì ta có 0 < j − i < a. Vì thế ib và jb không đồng dư với nhau theo môđun a. Do đó hệ trên là một hệ thặng dư 15 đầy đủ theo môđun a. Chứng minh thứ nhất cho Định lí hai đồng xu. Không mất tính tổng quát ta có thể giả thiết a < b. Trước hết ta chứng minh các số tự nhiên từ ab−b trở đi luôn biểu diễn được qua a, b. Rõ ràng ab−b = 0×a+(a − 1) b biểu diễn được qua a, b. Cho n > ab − b là số tự nhiên. Theo Bổ đề 2.1.2, tồn tại duy nhất một số trong hệ {0b, 1b, 2b, ..., (a − 1) b} đồng dư với n theo môđun a, giả sử tb ≡ n (moda) với 0 ≤ t ≤ a − 1. Do đó tồn tại số nguyên p sao cho n − tb = pa. Do t ≤ a − 1 nên tb ≤ (a − 1) b < n. Vì thế n − tb > 0. Suy ra p > 0. Do đó n = pa + tb là một biểu diễn của n thành tổ hợp tuyến tính không âm của a và b. Như vậy, n biểu diễn được qua a, b với mọi số tự nhiên n ≥ ab − b. Tiếp theo ta chứng minh các số ab − b − 1, ..., ab − b − (a − 1) là biểu diễn được qua a, b. Thật vậy, xét hệ S = {ab − b, ab − b − 1, ..., ab − b − (a − 1)} . Rõ ràng hệ này gồm a phần tử đôi một không đồng dư với nhau theo môđun a, vì thế nó là một hệ thặng dư đầy đủ theo môđun a. Theo Bổ đề 2.1.2, hệ T = {0b, 1b, 2b, ..., (a − 1) b} cũng là một hệ thặng dư đầy đủ theo môđun a. Vì thế mỗi số trong hệ S đồng dư theo môđun a với một và chỉ một số trong hệ T . Chú ý rằng hệ T và S đều chứa phần tử ab − b. Vì thế mỗi số trong hệ S đồng dư theo môđun a với một và chỉ một số trong hệ T . Chú ý rằng hệ T và S đều chứa phần tử ab − b. Vì thế mỗi số trong hệ S1 = {ab − b − 1, ..., ab − b − (a − 1)} đồng dư theo môđun a với một và chỉ một số trong hệ T1 = {0b, 1b, 2b, ..., (a − 2) b}. Phần tử lớn nhất của hệ T1 là (a − 2) b, phần tử nhỏ nhất của hệ S1 là ab − b − (a − 1). Vì a < b nên ta có ab − b − (a − 1) > ab − 2b. Do đó bất cứ số nào trong hệ S1 đều lớn hơn thực sự tất cả các phần tử trong hệ T1 . Lấy ab − b − r ∈ S1 với r ∈ {1, ..., a − 1}. Khi đó tồn tại tb ∈ T1 với r ∈ {0, 1, ..., a − 2} sao cho ab − b − r ≡ tb (moda). Do đó ab − b − r = tb + aq với q ∈ Z. Theo chứng minh trên, ab − b − r > tb. Vì thế q > 0. Theo trên, t ≥ 0. Do đó ab − b − r là một tổ hợp tuyến tính không âm của a, b. Như vậy, mọi phần tử trong S đều biểu diễn được qua a, b. Tóm lại, đến đây ta đã chứng minh được mọi số tự nhiên n > ab − a − b đều biểu diễn được qua a, b. Bây giờ ta chứng minh ab − a − b không biểu diễn được qua a, b. Giả sử 16 ab − a − b biểu diễn được qua a, b. Khi đó tồn tại các số nguyên p, q ≥ 0 sao cho ab − b − a = pa + qb. Nếu p = 0 thì ab − b − a là bội của b, do đó a là bội của b, điều này là vô lí. Do đó p > 0. Tương tự ta suy ra q > 0. Vì ab − b − a = pa + qb nên ta có qb ≡ ab − b − a (moda). Do p > 0 nên qb < ab − b − a. Vì q > 0, a < b và qb < ab − b − a nên ta có q ∈ {1, 2, ..., a − 2}. Vì thế, từ qb ≡ ab − b − a (moda) ta suy ra (q + 1) b ≡ 0 (moda). Do b và a nguyên tố cùng nhau nên q + 1 chia hết cho a, điều này là vô lí vì q ∈ {1, 2, ..., a − 2}. Chứng minh thứ hai cho Định lí hai đồng xu. Trường hợp một trong hai số a hoặc b bằng 1 thì không có số nguyên dương lớn nhất không biểu diễn qua a và b. Do đó ta chỉ xét Định lí hai đồng xu cho trường hợp a, b > 1. Trước hết ta khẳng định ab − a − b không biểu diễn được qua a và b. Thật vậy, giả sử ngược lại, tức là có các số nguyên không âm x, y sao cho ab − a − b = ax + by . Lấy kết quả ở hai vế theo môđun a ta suy ra được −b ≡ by (moda) . Suy ra (y + 1) b là bội của a. Do a và b nguyên tố cùng nhau nên y ≡ −1 (moda). Tương tự, bằng cách lấy kết quả ở hai vế của đẳng thức ab−a−b = ax+by theo môđun b ta được x ≡ −1 (modb). Do đó y = ma − 1 và x = nb − 1 với m, n là các số nguyên. Chú ý rằng a, b là các số dương. Vì thế nếu m ≤ 0 thì y ≤ −1 là số âm, vô lí. Do đó m ≥ 1 và vì thế by ≥ b (a − 1). Tương tự ta suy ra n ≥ 1 và do đó ax ≥ a (b − 1). Vì thế ta có ab − a − b = ax + by ≥ a (b − 1) + b (a − 1) = 2ab − a − b. Điều này là mâu thuẫn với giả thiết a, b là các số nguyên dương. Vậy, ab − a − b không biểu diễn được qua a và b. Đặt g (a, b) = ab − a − b. Tiếp theo, ta khẳng định g (a, b) + 1 biểu diễn được qua a và b. Vì gcd (a, b) = 1 nên từ thuật toán Euclid mở rộng, ta có thể tìm thấy các số x, y ∈ Z sao cho 1 = ax + by . Chia x cho b ta được x = bp + c trong đó 0 ≤ c < b. Do đó ta có 1 = ac + bap + by . Rút gọn cả hai vế theo môđun b ta được ac ≡ 1 (modb) và vì thế ta phải có b > c ≥ 1. Bằng cách lập luận tương tự, ta suy ra rằng tồn tại số nguyên d sao cho bd ≡ 1 (moda) với a > d ≥ 1. Từ đây ta có thể chỉ ra rằng (d − 1) b + (c − 1) a = ab − a − b + 1 = g (a, b) + 1. 17 Vì c, d > 1 nên c − 1 > 0 vàd − 1 > 0. Do đó (d − 1) b + (c − 1) a là một tổ hợp tuyến tính không âm của g (a, b) + 1, tức là g (a, b) + 1 biểu diễn được qua a, b. Cho n > g (a, b) + 1. Đặt r = g (a, b) − 1 > 0. Trước hết ta giả thiết r < min {a, b}. Vì gcd (a, b) = 1 nên từ thuật toán Euclid mở rộng, ta có thể tìm thấy các số e, f ∈ Z sao cho 1 = ae + bf . Suy ra r = are + brf . Ta có n = g (a, b) + 1 + r = (d − 1) b + (c − 1) a + are + brf = (c − 1 + re) a + (d − 1 + rf ) b. Vì 1 = ae + bf và a, b > 0 nên trong hai số e và f ắt phải có một số dương và một số âm. Không mất tính tổng quát ta có thể giả thiết e > 0 và f < 0. Rõ ràng hệ số (c − 1 + re) của a là dương. Vì thế nếu hệ số (d − 1 + rf ) của b không âm thì n = (c − 1 + re) a + (d − 1 + rf ) b là biểu diễn của n. Nếu (d − 1 + rf ) < 0 thì giả thiết r < min {a, b} ta có thể suy ra c − 1 + re − b ≥ 0. Nếu d − 1 + rf + a ≥ 0 thì n = (c − 1 + re) a + (d − 1 + rf ) b + ab + a (−b) = (c − 1 + re − b) a + (d − 1 + rf + a) b là biểu diễn của n. Trong trường hợp d − 1 + rf + a < 0 thì lại sử dụng giả thiết r < min {a, b} ta có thể suy ra c − 1 + re − 2b ≥ 0. Do đó nếu d − 1 + rf + 2a ≥ 0 thì n = (c − 1 + re) a + (d − 1 + rf ) b + 2ab + a (−2b) = (c − 1 + re − 2b) a + (d − 1 + rf + 2a) b là biểu diễn của n. Nếu d − 1 + rf + 2a < 0 thì ta cứ tiếp tục quá trình trên, sau một số hữu hạn bước ta thu được một biểu diễn của n qua a và b. Bây giờ ta giả thiết r > 0 bất kì. Khi đó tồn tại các số nguyên p, q ≥ 0 sao cho r = pa + pb + s, trong đó 0 ≤ s ≤ min {a, b}. Theo trường hợp trên, g (a, b) + 1 + s biểu diễn được qua a, b. Do đó g (a, b) + 1 + r cũng biểu diễn được qua a và b. 18 Như đã nhắc ở phần trên, chứng minh thứ nhất cho Định lí hai đồng xu đưa ra một thuật toán hữu hiệu để tìm biểu diễn của các số lớn hơn số Frobenius. Dưới đây là một ví dụ minh họa. 2.1.3. Ví dụ. Biểu diễn các số g (13, 19) + 1, g (13, 19) + 2, g (13, 19) + 7, g (13, 19) + 13, g (13, 19) + 39 qua 13 và 19. Lời giải. Ta có g (13, 19) = 13 × 19 − 13 − 19 = 215. Do đó ta phải biểu diễn các số 216, 217, 222, 228, 254 qua 13 và 19. Như trong chứng minh Định lí hai đồng xu của Jeffrey Shallit, ta cần tìm các số nguyên c, d sao cho 13c ≡ 1 (mod19) , 19d ≡ 1 (mod13) với 1 ≤ c < 19 và 1 ≤ d < 13. Để làm điều đó, ta cần thực hiện thuật toán Euclid mở rộng để biểu diễn ước chung lớn nhất gcd (13, 19) thành tổ hợp tuyến tính của chúng. 19 = 13 × 1 + 6 19 = 6 × 2 + 1 6 = 1 × 6. Suy ra: gcd (13, 19) = 1 = 13 − 6 × 2 = 13 − (19 − 13) × 2 = 13 × 3 + 19 × (−2) . Rút gọn theo môđun 19 ta được 13 × 3 ≡ 1 (mod19). Do đó ta có c = 3. Rút gọn theo môđun 13 ta được 19 × (−2) ≡ 1 (mod13). Ta lại có −2 = 13 × (−1) + 11. Vì thế 19 × 11 ≡ 1 (mod13). Do đó ta có d = 11. Vậy biểu diễn của g (13, 19) + 1 là g (13, 19) + 1 = (d − 1) 19 + (c − 1) 13, hay 216 = 10×19+2×13 là biểu diễn của 216. Để biểu diễn 217 = 216+1, ta có 1 = 10 × 3 + 19 × (−2) . Vì thế 217 = 8 × 19 + 5 × 13 là biểu diễn của 217 qua 13 và 19. Đối với biểu diễn của 222 = 216 + 6, ta có 6 = 13 × 18 + 19 × (−12) . Vì thế 222 = (−2) × 19 + 20 × 13. Vì hệ số −2 là âm nên ta thực hiện một lần thêm và bớt 13 × 19, ta được 222 = (−2 + 13) × 19 + (20 − 19) × 13, hay 222 = 11 × 19 + 1 × 13 là biểu diễn của 222 qua 13 và 19. Đối với biểu diễn của 228 = 216 + 12,