Luận văn Thạc sĩ Toán học: Một số lớp phương trình Diophantine

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

Thêm vào BST

Báo xấu

61
lượt xem 7
download

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

Mục tiêu của đề tài luận văn là: Tìm hiểu một số lớp phương trình Diophantine như phương trình Diophantine tuyến tính; một số phương trình Diophantine phi tuyến (phương trình Pell, phương trình Pell mở rộng, phương trình Pythagoras Fermat). Liên phân số và ứng dụng trong phương trình Diophantine.

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ĩ Toán học: Một số lớp phương trình Diophantine

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI HỮU MÊN MỘT SỐ LỚP PHƯƠNG TRÌNH DIOPHANTINE LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI HỮU MÊN MỘT SỐ LỚP PHƯƠNG TRÌNH DIOPHANTINE 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 GS.TSKH. ĐẶNG HÙNG THẮNG Thái Nguyên - 2017
3 Mục lục Danh sách kí hiệu 4 Mở đầu 5 Chương 1. Phương trình Diophantine tuyến tính 7 1.1 Phương trình bậc nhất hai ẩn . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Phương trình bậc nhất nhiều ẩn . . . . . . . . . . . . . . . . . . . . . . 15 Chương 2. Một số phương trình Diophantine phi tuyến 23 2.1 Phương trình Pell loại 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Phương trình Pell loại 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3 Phương trình Pythagoras . . . . . . . . . . . . . . . . . . . . . . . . . 38 Chương 3. Liên phân số và ứng dụng trong phương trình Diophantine 45 3.1 Liên phân số hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Liên phân số vô hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3 Liên phân số vô hạn tuần hoàn . . . . . . . . . . . . . . . . . . . . . . 50 3.4 Áp dụng vào phương trình Diophante . . . . . . . . . . . . . . . . . . 56 3.4.1 Phương trình bậc nhất hai ẩn Ax + By = C . . . . . . . . . . . . 56 3.4.2 Phương trình x2 − dy2 = ±1 . . . . . . . . . . . . . . . . . . . 57 Kết luận 62 Tài liệu tham khảo 63
4 Danh sách kí hiệu N tập hợp các số tự nhiên Z vành các số nguyên Q trường các số hữu tỷ R trường các số thực C trường các số phức Fp trường có p phần tử K[X] vành đa thức với hệ số trên trường K dxe trần của số x deg P(X) bậc của đa thức P(X) mod p modulo p gcd(P(X), Q(X)) ước chung lớn nhất của hai đa thức P(X) và Q(X)
5 Mở đầu Phương trình Diophantine là một chủ đề lớn của Lý thuyết số, chứa đựng nhiều lý thuyết toán học sâu sắc, gắn liền với nhiều tên tuổi của nhiều nhà toán học xuất sắc. Mục tiêu của đề tài luận văn là: Tìm hiểu một số lớp phương trình Diophantine như: phương trình Diophantine tuyến tính; một số phương trình Diophantine phi tuyến (phương trình Pell, phương trình Pell mở rộng, phương trình Pythagoras Fermat). Liên phân số và ứng dụng trong phương trình Diophantine. Về mặt ứng dụng, luận văn sẽ áp dụng lý thuyết để soi sáng những bài toán số học ở phổ thông, hệ thống hóa, tổng quát hóa và sáng tác ra những bài toán số học mới. Luận văn sẽ cố gắng trở thành một tài liệu tham khảo tốt, thiết thực phục vụ cho việc giảng dạy, nhất là việc giảng dạy và bồi dưỡng học sinh giỏi. Ngoài ra thông qua việc viết luận văn, tác giả luận văn có cơ hội mở rộng nâng cao hiểu biết về toán sơ cấp nói chung và số học nói riêng, hình thành các kỹ năng chứng minh các định lí số học và giải các bài toán số học, phục vụ tốt cho việc giảng dạy môn Toán ở trường phổ thông. Nội dung của luận văn được trình bày trong ba chương như sau: • Chương 1. Phương trình Diophantine tuyến tính. Trong chương này chúng tôi trình bày về phương trình bậc nhất hai ẩn, nhiều ẩn, và một số bài toán chọn lọc. • Chương 2. Một số phương trình Diophantine phi tuyến. Trong chương này chúng tôi trình bày nội dung chính về các phương trình Pell loại 1, phương trình Pell loại , và phương trình Pythagoras. • Chương 3. Liên phân số và ứng dụng trong phương trình Diophantine. Trong
6 chương này chúng tôi trình bày một cách ngắn gọn các sự kiện về liên phân số, đặc biệt là các ứng dụng của chúng để giải phương trình Pell. Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành với sự hướng dẫn của GS.TSKH. Đặng Hùng Thắng (Trường ĐHKHTN - ĐHQG Hà Nội). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán–Tin, cùng các giảng viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu. Tác giả muốn gửi những lời cảm ơn tốt đẹp nhất tới tập thể lớp Cao học Toán khóa 9 (2015-2017) đã động viên và giúp đỡ tác giả rất nhiều trong suốt quá trình học tập. Nhân dịp này, tác giả cũng xin chân thành cảm ơn Sở Giáo dục và Đào tạo Hải Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Thái Phiên đã tạo điều kiện cho tác giả hoàn thành tốt nhiệm vụ học tập và công tác của mình. Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến đại gia đình vì những động viên và chia sẻ những khó khăn để tác giả hoàn thành luận văn này. Thái Nguyên, ngày 10 tháng 11 năm 2017 Tác giả Bùi Hữu Mên
7 Chương 1 Phương trình Diophantine tuyến tính Phương trình Diophantine là một trong những chủ đề sâu sắc và rất rộng của Lý thuyết số. Mục đích của chương này là nghiên cứu về phương trình Diophantine bậc nhất hai và nhiều ẩn. Như một minh họa cho lý thuyết, các ví dụ là các bài toán trích từ các đề thi sẽ được trình bày. Đặc tính của các phương trình Diophantine là chúng có một hay nhiều ẩn số mà mọi hệ số đều là số nguyên và chỉ yêu cầu tìm các nghiệm nguyên (hoặc nguyên dương). Nhà toán học nổi tiếng thời cổ đại Diophantine đã có công lớn vì những nghiên cứu tiên phong về chúng. Với một phương trình Diophantine cho trước ta có thể đặt ra các câu hỏi sau đây (xếp theo thứ tự từ dễ đến khó): Câu hỏi 1. Nó có nghiệm nguyên hay không ? Câu hỏi 2. Nó có một số hữu hạn nghiệm hay có vô số nghiệm? Câu hỏi 3. Hãy tìm tất cả các nghiệm của nó. Chẳng hạn, ta hãy xét phương trình Diophantine xn + yn = zn trong đó n là số nguyên dương lớn hơn hay bằng 2. Với n = 2 phương trình trên có vô số nghiệm và ta có thể tìm được tường minh tất cả các nghiệm của nó. Với n > 2, nhà toán học thiên tài của thế kỷ 17 Pierre de Fermat khẳng định rằng
8 phương trình trên không có nghiệm nguyên dương. Kết luận này ngày nay được mang tên là Định lí lớn Fermat hay Định lí cuối cùng của Fermat. Người ta đã không tìm thấy dấu vết của chứng minh khẳng định trên của Fermat mà chỉ thấy một ghi chú của Fermat bên lề cuốn sách “Số học” của Diophantine: “Tôi đã tìm được một chứng minh thật là tuyệt vời nhưng vì lề sách ở đây quá hẹp nên không thể viết ra”. Năm 1983, nhà toán học 29 tuổi người Đức là Faltings đã chứng minh thành công một giả thuyết của Mordell trong lĩnh vực Hình học đại số rồi từ đó suy ra rằng phương trình xn + yn = zn với n > 2 chỉ có một số hữu hạn nghiệm nguyên. Với thành tựu này Faltings đã nhận được Giải thưởng Fields (giải thưởng quốc tế cao nhất dành cho các nhà toán học không quá 40 tuổi). Năm 1993 nhà toán học người Anh là Andrew Wiles đã công bố phép chứng minh của Định lí lớn Fermat. Đây là một câu chuyện lớn của Toán học, có thể tham khảo trong Amir D. Aczel [1]. Với sự ra đời của máy tính, người ta cũng đặt câu hỏi: Có tồn tại chăng một thuật toán để với mọi phương trình Diophantine cho trước nhờ đó có thể khẳng định được rằng phương trình này có nghiệm nguyên hay không. Tiếc thay câu trả lời lại là: không có một thuật toán như vậy (Định lí Machiakevich). 1.1 Phương trình bậc nhất hai ẩn Phương trình Diophantine đơn giản nhất là phương trình bậc nhất hai ẩn ax + by = c (1.1) trong đó a, b, c là những số nguyên cho trước khác 0. Vấn đề đặt ra là với điều kiện nào của a, b, c thì phương trình (1.1) có nghiệm và nếu có thì cách tìm nghiệm thế nào. Định lí 1.1.1. Điều kiện cần và đủ để phương trình (1.1) có nghiệm nguyên là
9 (a, b) là ước của c. Chứng minh. Điều kiện cần. Giả sử (x0 , y0 ) là một nghiệm nguyên của (1.1). Khi đó ax0 + by0 = c. Nếu d = (a, b) thì rõ ràng d | c. Điều kiện đủ. Giả sử d = (a, b) và d | c. Ta có a = da1 , b = db1 , c = dc1 trong đó (a1 , b1 ) = 1. Phương trình (1.1) tương đương với a1 x + b1 y = c1 . Xét a1 số {b1 k} với k = 0, 1, 2, . . . , a1 − 1. Vì (a1 , b1 ) = 1 nên các số này khi chia cho a1 sẽ cho ta các số dư khác nhau. Vậy tại k0 , 0 ≤ k0 ≤ a1 − 1 sao cho b1 k0 = c1 (mod a1 ). Điều này có nghĩa là: c1 − b1 k0 = a1 l0 với l0 ∈ Z hay c1 = a1 l0 + b1 k0 . Vậy (l0 , k0 ) là một nghiệm của phương trình (1.1). Phép chứng minh định lí được hoàn thành. Tiếp theo ta hãy đi tìm tất cả các nghiệm của phương trình (1.1) Định lí 1.1.2. Nếu (x0 , y0 ) là một nghiệm nguyên của (1.1) thì nó có vô số nghiệm nguyên và nghiệm nguyên (x, y) của nó được cho bởi công thức b  x = x0 + t,  d (1.2) y = y0 − a t,  d trong đó t ∈ Z và d = (a, b). Chứng minh. Trước hết ta kiểm tra mọi cặp số (x, y) cho bởi công thức (1.2) là nghiệm. Thật vậy ax + by = ax0 + by0 = c. Đảo lại, giả sử (x1 , y1 ) là một nghiệm của (1.1) tức là ax1 + by1 = c. Trừ đẳng thức này vào đẳng thức ax0 + by0 = c ta thu được a(x1 − x0 ) = b(y0 − y1 ). (1.3)
10 Vì d = (a, b) nên a = a1 d, b = b1 d với (a1 , b1 ) = 1. Thay vào (1.3) ta được a1 (x1 − x0 ) = b1 (y0 − y1 ). Vì (a1 , b1 ) = 1 nên y0 − y1 = ta1 và x1 − x0 = tb1 . Vậy at bt y1 = y0 − ta1 = y0 − và x1 = x0 + tb1 = x0 + . d d Phép chứng minh được kết thúc. Thuật toán tìm nghiệm của phương trình Diophantine bậc nhất. Từ Định lí 1.1.2 ta thấy rằng để tìm tất cả các nghiệm của (1.1) ta chỉ cần tìm một nghiệm (x0 , y0 ) nào đó của nó. Ta gọi một nghiệm cụ thể như thế là một nghiệm riêng còn công thức (1.2) được gọi là nghiệm tổng quát. Sau đây ta sẽ trình bày một thuật toán cho phép xác định khá nhanh một nghiệm riêng của (1.1). Giả sử q0 , q1 , . . . là một dãy các số nguyên dương. Với mỗi i ≥ 0 ta kí hiệu [q0 , q1 , . . . , qi ] là phân số sau đây 1 [q0 , q1 , . . . , qi ] = q0 + . 1 q1 + 1 q2 + · · · + 1 qi−1 + qi Bằng phương pháp quy nạp có thể dễ dàng chứng minh được bổ đề sau: Bổ đề 1.1.3. Giả sử {hn }, {kn } là hai dãy số nguyên được xác định như sau: h−2 = 0, h−1 = 1, h1 = qi hi−1 + hi−2 , i ≥ 0, k0 = 1, k1 = q1 , ki = qi hki−1 + ki−2 , i ≥ 2. Khi đó với mọi i ≥ 1 ta có: (a) hi ki−1 − hi−1 ki = (−1)i−1 ; (b) [q0 , q1 , . . . , qi ] = hkii .
11 Bây giờ cho hai số dương a, b với a > b. Ta hãy viết thuật toán Euclid tìm ước chung lớn nhất của a và b. a = bq0 + r1 b = r1 q1 + r2 ... (1.4) rn−1 = rn qn−1 + rn+1 rn = rn+1 qn . Từ hệ (1.4) ta suy ra a = [q0 , q1 , . . . , qn ] b Từ khẳng định (b) của Bổ đề 1.1.3 ta có a hn = . b kn Từ (a) ta suy ra (hn , kn ) = 1. Do đó nếu (a, b) = 1 thì a = hn và b = kn . Vậy thì akn−1 − bhn−1 = (−1)n−1 . Thành thử tồn tại x0 ∈ {kn−1 } và y0 ∈ {hn−1 } sao cho ax0 + by0 = 1. Ta thử từng trường hợp (nhiều nhất là bốn phép thử) để xác định x0 , y0 . Như vậy để giải phương trình (1.1) ta sẽ tiến hành lần lượt các bước sau đây. Bước 1. Tìm d = (a, b) sau đó chia hai vế cho d để được một phương trình tương đương a1 x + b1 y = c1 , ở đó a = da1 , b = db1 , c = dc1 , (a1 , b1 ) = 1. Bước 2. Viết thuật toán Euclid cho hai số |a1 | và |b1 |. Giả sử |a1 | > |b1 |. |a1 | = |b1 |q0 + r1
12 |b1 | = r1 q1 + r2 ... rn−1 = rn qn−1 + rn+1 rn = rn+1 qn . Bước 3. Tính [q0 , q1 , . . . , qn−1 ] = hk . Bước 4. Lấy nghiệm riêng (x00 , y00 ) của phương trình a1 x + b1 y = 1 thoả mãn điều kiện |x00 | = k, |y00 | = h. Ta xác định dấu của x00 và y00 bằng cách thử. Bước 5. Ta có x0 = c1 x00 , y0 = c1 y00 là nghiệm riêng của phương trình (1.1). Khi đó nghiệm tổng quát là x = x0 + b1t, y = y0 + a1t, với t ∈ Z. Ví dụ 1.1.4. Giải phương trình Diophantine 342x − 123y = 15. Lời giải. Ta sẽ làm lần lượt theo các bước như trên. Bước 1. Ứớc chung lớn nhất của 342 và 123 là 3. phương trình đã cho tương đương với 114x − 41y = 5. Bước 2. Ta viết thuật toán Euclid cho 114 và 41. 114 = 41 · 2 + 32 41 = 32 · 1 + 9 32 = 9 · 3 + 5 9 = 5·1+4 5 = 4·1+1 4 = 1 · 4.
13 Bước 3. Ta biểu diễn theo liên phân số h 1 25 = 2+ = . k 1 9 1+ 1 3+ 1 1+ 1 Như vậy h = 25, k = 9. Bước 4. Lấy nghiệm riêng x00 , y00 của phương trình 114x − 41y = 1 thoả mãn điều kiện |x00 | = 9 và |y00 | = 25. Bằng cách thử ta tìm được x00 = 9, y00 = 25. Bước 5. Nghiệm riêng x0 , y0 của phương trình đã cho là x0 = 9 · 5 = 45, y0 = 25 · 5 = 125 và nghiệm tổng quát là x = 45 + 41t, y = 125 + 114t, với t ∈ Z. Nhận xét 1.1.5. 1. Nếu a | c ta có thể lấy nghiệm riêng c x0 = , y0 = 0. a 2. Xét trường hợp (a, b) = 1. Theo Định lí Euler ta có aϕ(b) − 1 = kb với k ∈ Z. Vậy caϕ(b) − bkc = c. Do đó x0 = caϕ(b) − 1, y0 = −kc là một nghiệm riêng của phương trình đang xét.
14 Một số bài toán chọn lọc Bài toán 1.1.6. Cho hai số nguyên dương a, b. Chứng minh rằng (a, b) = 1 khi và chỉ khi tồn tại các số nguyên dương u, v sao cho au − bv = 1. Lời giải. Điều kiện đủ là hiển nhiên. Đảo lại, giả sử (a, b) = 1. Theo Định lí 1.1.1, tồn tại các số nguyên x0 , y0 để cho ax0 + by0 = 1. Đặt  u = x0 + bt,  v = at − y0 ,  trong đó t ∈ Z được chọn sao cho x0 y0 t >− , t> . b b Khi đó u và v là các số nguyên dương và au − bv = ax0 + by0 = 1. Bài toán 1.1.7. Giả sử (l, m) = 1 và al = bm , trong đó a, b, l, m ∈ N∗ . Khi đó tồn tại n để a = nm , b = nl . Lời giải. Theo Bài toán 1.1.6 tồn tại các số r, s ∈ N∗ để lr − ms = 1. Ta có r m lr−ms alr bmr b a=a = ms = ms = . a a as √ r √ r Suy ra m a = bas . Vì m a là một số hữu tỉ nên nó phải là số nguyên. Vậy n = bas ∈ N∗ . Suy ra a = nm . Từ đó bm = nl = nml , nên b = nl . Bài toán được chứng minh xong. Bài toán 1.1.8. Cho a ∈ N∗ . Hãy tìm g = (am − 1, an − 1). Lời giải. Trước hết xét trường hợp (m, n) = 1. Vì (a − 1) | am − 1, (a − 1)an − 1 nên a − 1 là ước của g. Đảo lại, ta sẽ chứng minh g cũng là ước của a − 1. Theo Bài toán 1.1.6 tồn tại các số u, v ∈ N∗ sao cho mu − nv = 1.
15 Vì g | am − 1, g | an − 1 nên cũng có g | amu − 1, g | anv − 1. Suy ra g | amu − anv = anv (amu−nv − 1) = anv (a − 1). Mặt khác, dễ thấy (g, a) = 1. Vậy g | (a − 1). Như vậy nếu (m, n) = 1 thì (am − 1, an − 1) = a − 1. Với m, n bất kì, giả sử d = (m, n). Khi ấy m = dm1 , n = dn1 và (m1 , n1 ) = 1. Ta có (am − 1, an − 1) = ((ad )m1 − 1, (ad )n1 − 1) = ad − 1. Tóm lại ta có công thức (am − 1, an − 1) = a(m, n) − 1. Bài toán 1.1.9. Cho (a, b) = 1 trong đó a, b ∈ N∗ . Tìm giá trị c ∈ N∗ lớn nhất để phương trình ax + by = c không có nghiệm nguyên dương. Lời giải. Ta chứng minh rằng c = ab là giá trị cần tìm. Giả sử c > ab. Xét b số a, 2a, . . . , ba. Vì (a, b) = 1 nên các số này khi chia cho b sẽ cho các số dư khác nhau. Vậy tồn tại số k, 1 ≤ k ≤ b, sao cho ka ≡ c (mod b). Suy ra c − ka = lb trong đó l ∈ Z. Nếu c > ab thì c > ka, do đó lb > 0 hay l ∈ N∗ . Như vậy (k, l) là nghiệm nguyên dương của phương trình ax + by = c. Mặt khác, giả sử (x0 , y0 ) là nghiệm nguyên dương của phương trình ax + by = ab. Khi đó ax0 = ab − by0 = b(a − y0 ). . . Vì (a, b) = 1 nên từ đó suy ra x0 .. b. Tương tự, y0 .. a. Như vậy x0 ≥ b, y0 ≥ a, do đó ab = ax0 + by0 ≥ 2ab. Vô lý. Phép chứng minh được kết thúc. 1.2 Phương trình bậc nhất nhiều ẩn Trong mục này ta mở rộng kết quả của mục trước bằng cách xét phương trình Diophantine bậc nhất n ẩn a1 x1 + a2 x2 + . . . + an xn = c. (1.5)
16 trong đó a1 , a2 , . . . , an và c là các số nguyên cho trước, n ≥ 2. Đối với bất kỳ một phương trình nào, câu hỏi đầu tiên là, trong những tình huống nào của hệ số, ta có thể khẳng định về tính tồn tại nghiệm của nó. Về sự tồn tại nghiệm của phương trình Diophantine bậc nhất n ẩn này ta có định lí sau đây. Định lí 1.2.1. Điều kiện cần và đủ để phương trình (1.5) có nghiệm là (a1 , a2 , . . . , an ) | c. Chứng minh. Điều kiện cần là hiển nhiên. Ta sẽ chứng minh điều kiện đủ bằng phương pháp quy nạp, với n = 1 điều khẳng định là đúng do Định lí 1.1.1. Giả sử định lí đúng với n = 1, ta chứng minh nó đúng với n. Kí hiệu ai c bi = , c1 = , ở đó d = (a1 , a2 , . . . , an ). d d Phương trình (1.5) tương đương với b1 x1 + b2 x2 + . . . + bn xn = c1 . (1.6) trong đó (b1 , b2 , . . . , bn ) = 1. Đặt b = (b1 , b2 , . . . , bn−1 ). Ta có (b, bn ) = 1. Theo Định lí 1.1.1 tồn tại số nguyên ln và k sao cho: bn ln + bk = c1 . (1.7) bi Kí hiệu b0i = b với i = 1, 2, . . . , n − 1. Ta có (b01 , b02 , . . . s, b0n−1 ) = 1. Theo giả thiết quy nạp tồn tại các số nguyên l1 , l2 , . . . , ln−1 sao cho b01 l1 + b02 l2 + . . . + b0n−1 ln−1 = k hay b1 l1 + b2 l2 + . . . + bn−1 ln−1 = bk. (1.8) Từ (1.7) và (1.8) ta suy ra b1 l1 + b2 l2 + . . . + bn−1 ln−1 + bn ln = c1 tức là (l1 , l2 , . . . , ln ) là nghiệm của phương trình (1.6). Định lí được chứng minh.
17 Chúng ta không đi sâu vào việc tìm biểu thức cho nghiệm tổng quát của nó như đã làm đối với trường hợp n = 2. Tuy nhiên có thể thấy rằng nếu phương trình (1.5) có nghiệm nguyên α1 , α2 , . . . , αn thì nó sẽ có vô số nghiệm nguyên phụ thuộc vào n − 1 tham số. Thật vậy, dễ dàng kiểm tra được tất cả các bộ n số nguyên x1 , x2 , . . . , xn xác định như sau là nghiệm của (1.5),      x1 = α1 + ant1        x2 + α2 + ant2  ...    xn−1 = αn−1 + antn−1        xn = αn − a1t1 − a2t2 . . . − an−1tn−1  trong đó ti ∈ Z, i = 1, 2, . . . n − 1 được chọn tuỳ ý. Bây giờ, ta sẽ thảo luận về cách giải phương trình (1.5). Về mặt thực hành ta có thể tiến hành theo hai cách sau đây. Cách 1. Đưa (1.5) về trường hợp có một hệ số bằng 1. Cách 2. Nếu phương trình (1.5) có hai hệ số nguyên tố cùng nhau, chẳng hạn (a1 , a2 ) = 1 thì ta viết dưới dạng a1 x1 + a2 x2 = c − a3x3 − . . . − an xn rồi giải phương trình theo hai ẩn x1 , x2 . Ta xét hai ví dụ sau đây, nó sẽ lần lượt minh họa cho hai cách trên. Ví dụ 1.2.2. Tìm tất cả các nghiệm nguyên của phương trình 6x + 45y + 6z − 10t = 13. Lời giải. Phương trình đã cho được viết dưới dạng 6(x + z) + 10(4y − t) + 5y = 13.
18 Đặt x + z = x1 , 4y − t = x2 ta được 6x1 + 10x2 + 5y = 13. Suy ra x1 + 10x2 + 5(y + x1 ) = 13. Đặt x1 + y = x3 ta được x1 + 10x2 + 5x3 = 13. Vậy x1 = 13 − 10x2 − 5x3 . Từ đây, bằng tính toán trực tiếp ta có y = x3 − x1 = x3 − (13 − 10x2 − 5x3 ) = 10x2 + 6x3 − 13; t = 4y − x2 = 39x2 + 24x3 − 52; x = x1 − z = 13 − 10x2 − 5x3 − z. Vậy nghiệm tổng quát của phương trình đã cho là x = 13 − 10x2 − 5x3 − x4 , y = 10x2 + 6x3 − 13, z = x4 , t = 39x2 + 24x3 − 52. trong đó x2 , x3 , x4 là các số nguyên tuỳ ý. Ví dụ 1.2.3. Giải phương trình 6x + 15y + 10z = 3. (1.9) Lời giải. Ta có thể viết (1.9) dưới dạng 6(x + z) + 15y = 3 − 4z. Đặt u = x + z ta có 15y + 4z = 3 − 6u. Ta thấy (−1, 4) là nghiệm riêng của 15y + 4z = 1. Do đó (−3 + 6u, 12 − 24u) là nghiệm riêng của 15y + 4z = 3 − 6u. Suy ra nghiệm tổng quát của nó là y = −3 + 6u + 4t, z = 12 − 24u − 15t.
19 Từ u = x + z suy ra x = u − z = u − (12 − 24u − 15t) = −12 + 25u + 15t. Vậy nghiệm tổng quát của (1.9) là      x = −12 + 25u + 15t,  y = −3 + 6u + 4t,    z = 12 − 24u − 15,  với u, t ∈ Z. Một số bài toán chọn lọc Bài toán 1.2.4 (Đề thi Vô định Toán Quốc tế 1983). Cho a, b, c là các số nguyên đôi một nguyên tố cùng nhau. Chứng minh rằng 2abc − ab − bc − ca là số nguyên lớn nhất không viết được dưới dạng xbc + yca + zab với x, y, z là những số không âm. Lời giải. Bài toán tương đương với việc chứng minh rằng Khẳng định 1. phương trình xbc + yca + zab = 2abc − ab − bc − ca không có nghiệm nguyên không âm; Khẳng định 2. Nếu n > 2b − ab − bc − ca thì phương trình có nghiệm nguyên không âm. Chứng minh Khẳng định 1. Giả sử tồn tại x0 , y0 , z0 ∈ N∗ sao cho x0 bc + y0 ca + z0 ab = 2abc − ab − bc − ca. Điều này tương đương với bc(x0 + 1) + ca(y0 + 1) + ab(z0 + 1) = 2abc.
20 . . Suy ra ab(z0 + 1) .. c. Vì (ab, c) = 1 nên z0 + 1 .. c. Mặt khác z0 + 1 ∈ N∗ nên z0 + 1 ≥ c. Tương tự y0 + 1 ≥ b, x0 + 1 ≥ a. Vậy bc(x0 + 1) + ca(y0 + 1) + ab(z0 + 1) ≥ 3abc. Điều này vô lí. Chứng minh Khẳng định 2. Xét ab có dạng kbc + lac, với 0 ≤ k ≤ a − 1, 0 ≤ l ≤ b − 1.. Các số này khi chia cho ab sẽ cho ta các số dư khác nhau. Thật vậy, giả sử k1 bc + l1 ac ≡ k2 bc + l2 ac (mod ab). . . Vì (ab, c) = 1 nên suy ra b(k1 − k2 ) − a(l1 − l2 ) .. ab. Từ đó b(k1 − k2 ) .. a và a(l1 − . . . l2 ) .. b. Vì (a, b) = 1 nên k1 − k2 .. a và l1 − l2 .. b. Mặt khác |k1 − k2 | < a, |l1 − l2 | < b nên l1 −l2 = 0, k1 −k2 = 0. Do đó tồn tại x0 , y0 ∈ Z+ , 0 ≤ x0 ≤ a−1, 0 ≤ y0 ≤ b−1 để cho bcx0 + acy0 ≡ n (mod ab). Vậy tồn tại z0 ∈ Z để bcx0 + acy0 + abz0 = n. Ta có ab(z0 + 1) = n − bcx0 − acy0 + ab > 2abc − bcx0 − acy0 − bc − ca = bc(a − 1 − x0 ) + ac(b − 1 − y0 ) ≥ 0. Do đó z0 + 1 > 0. Suy ra z0 ≥ 0. Bài toán 1.2.5. Cho các số nguyên không âm a, b thoả mãn điều kiện 5a ≥ 7b. Chứng minh rằng hệ  x + 2y + 3z + 7u = a, y + 2z + 5u = b luôn có nghiệm nguyên không âm.