Đăng ký Đăng nhập
Trang chủ Phương pháp tìm nghiệm nguyên của hệ phương trình tuyến tính...

Tài liệu Phương pháp tìm nghiệm nguyên của hệ phương trình tuyến tính

.PDF
49
4875
107

Mô tả:

MỞ ĐẦU Nhiều bài toán thực tế dẫn đến các phương trình, hệ phương trình tuyến tính với hệ số nguyên mà ta phải tìm được nghiệm nguyên của phương trình và hệ phương trình này. Phương trình như thế thường được gọi là phương trình Đi-ôphăng tuyến tính. Đây là một chủ đề quan trọng trong chương trình phổ thông. Trong lịch sử toán học đã có rất nhiều các nhà toán học nghiên cứu về chủ đề này. Tuy nhiên, số lượng các vấn đề cần được giải quyết còn rất nhiều. Luận văn này có mục đích tìm hiểu và trình bày các thuật toán tìm nghiệm nguyên của phương trình và hệ phương trình tuyến tính với các hệ số nguyên. Nội dung luận văn được chia thành 3 chương: Chương 1 "Kiến thức chuẩn bị” nhắc lại các khái niệm ước số và phần dư của phép chia hai số nguyên, số nguyên tố và hợp số, ước chung lớn nhất của hai hay nhiều số nguyên, thuật toán Ơ-clít tìm ước chung lớn nhất, đề cập tới khái niệm đồng dư và bài toán tìm nghiệm nguyên của phương trình Đi-ô-phăng tuyến tính của hai hay nhiều biến số, điều kiện tồn tại nghiệm nguyên của phương trình. Chương 2 "Phương trình tuyến tính" đề cập tới khái niệm nghiệm nguyên riêng và nghiệm nguyên tổng quát của phương trình tuyến tính với hệ số nguyên của hai hay nhiều biến số. Trình bày hai thuật toán tìm nghiệm nguyên riêng và nghiệm nguyên tổng quát của phương trình tuyến tính và chứng minh tính đúng đắn của các thuật toán giải, cùng với các ví dụ số minh họa cho thuật toán. Chương 3 "Hệ phương trình tuyến tính" đề cập tới các bài toán thực tế dẫn tới hệ phương trình tuyến tính với các hệ số nguyên và trình bày các thuật toán giải hệ phương trình tuyến tính, chứng minh tính đúng đắn của thuật toán giải, cùng với các ứng dụng có liên quan của các bài toán được xét. Tìm nghiệm nguyên dương của hệ phương trình tuyến tính với hệ số nguyên. 1 Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau này. Nhân dịp này, tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS.TS. Trần Vũ Thiệu, đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả cũng xin chân thành cảm ơn các thầy, cô giáo ở Bộ môn toán đã nhiệt tình giảng dạy, các cán bộ Phòng sau đại học và quản lý khoa học, Ban giám hiệu Trường đại học Thăng Long đã quan tâm, động viên và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu tại Trường. Hà Nội, tháng 05 năm 2016 Tác giả Lê Minh Quỳnh Hoa 2 Thang Long University Libraty Chương 1 KIẾN THỨC CHUẨN BỊ Chương này nhắc lại khái niệm phần dư của phép chia hai số nguyên, ước chung lớn nhất của hai hay nhiều số nguyên, thuật toán Ơ-clit tìm ước chung lớn nhất và đề cập tới bài toán tìm nghiệm nguyên của phương trình tuyến tính với hệ số nguyên của hai hay nhiều biến số, điều kiện tồn tại nghiệm nguyên của phương trình. Nội dung của chương được tham khảo từ các tài liệu [1], [2] và [4]. 1.1. ƯỚC CHUNG LỚN NHẤT 1.1.1. Ước số và phần dư Xét tập số nguyên ℤ = {0,  1,  2, ... }. Từ lý thuyết số, ta có kết quả sau Định lý 1.1.(Thuật toán chia) Với mọi a, b  ℤ, b  0, tồn tại duy nhất q, r ℤ, 0  r < |b|, sao cho a = bq + r. (Chia a cho b được q là thương số, r là phần dư). Ví dụ 1.1. a) Với a = 23, b = 5 ta có q = 4, r = 3, vì 23 = 54 + 3. b) Với a = 17, b = - 3 ta có q = - 5, r = 2, vì 17 = (- 3)(- 5) + 2. c) Với a = - 11, b = 2 ta có q = - 6, r = 1, vì - 11 = 2(- 6) + 1. d) Với a = - 9, b = - 4 ta có q = 3, r = 3, vì - 9 = (- 4)3 + 3. Định nghĩa 1.1. Với a, b  ℤ, ta nói a là ước (divisor) của b nếu tồn tại số nguyên x sao cho a.x = b. Trong trường hợp này ta nói rằng b chia hết (divisible) cho a hay b là bội (multiple) của a và viết a | b (đọc là a là ước của b). Trái lại, ta nói a không là ước của b và viết a ∤ b. Ví dụ 1.2. Do 2 và - 3 là ước của 6 nên ta viết 2 | 6 và - 3 | 6. Nhưng 4 không là ước của 6 nên ta viết 4 ∤ 6. Bài tập 1.1. Giả sử a, b, c, m, n  ℤ. Nếu a | b và a | c thì a | (mb + nc). Định nghĩa 1.2. Với bất kỳ a  ℤ, các điều sau đây luôn đúng: 1 | a, - 1 | a, a | a, - a | a. 3 Ta nói 1, - 1, a và - a là các ước tầm thường (trivial divisors) của a; 1 và -1 gọi là đơn vị (units), mọi ước bất kỳ khác của a gọi là ước thực sự (proper divisors). 1.1.2. Số nguyên tố và hợp số Định nghĩa 1.3. Số nguyên dương a > 1 gọi một là số nguyên tố (prime) nếu a không có ước thực sự. Số nguyên dương a gọi là một hợp số (composite) nếu a có ước thực sự. Nếu a là số nguyên dương và các số nguyên tố p1, p2, ... , pk thỏa mãn p1p2 ... pk = a thì tích p1p2 ... pk gọi là phân tích thừa số nguyên tố (prime factorization) của a. Ví dụ 1.3. Các số nguyên tố < 40: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Định lý 1.2. (Định lý cơ bản của số học) Mọi số a  ℤ, a > 1, có phân tích thừa số nguyên tố duy nhất (không kể sự sai khác về thứ tự các thừa số). Ví dụ 1.4. 12 = 223; 18 = 232; 231 = 3711. Định nghĩa 1.4. Cho a, b  ℤ. Ta định nghĩa ước chung lớn nhất (greatest common divisor) của a và b là số nguyên lớn nhất d mà cả a và b đều chia hết cho d: d | a và d | b. Ước chung lớn nhất được ký hiệu là (a, b) = d hoặc gcd (a, b) = d. Ta sẽ sử dụng (a, b) để chỉ ước chung lớn nhất của a và b. Ví dụ 1.5. Hãy tìm ước chung lớn nhất của 8 và 20. Ta thấy các ước của 8 là ±1, ±2, ±4, ±8; và các ước của 20 là ±1, ±2, ±4, ±5, ±10. Từ đó, ước chung của 8 và 20 là ±1, ±2, ±4. Vì thế, ước chung lớn nhất của 8 và 20 là 4. Ta viết gcd (8, 20) = 4 hoặc (8, 20) = 4. Có thể kiểm tra lại rằng (12, - 9) = 3; (- 15, 20) = 5; (- 3, - 7) = 1. Định nghĩa 1.5. Nếu ước chung lớn nhất (a, b) = 1 thì ta nói hai số nguyên a và b là nguyên tố cùng nhau (relatively prime). Định lý 1.3. Nếu a, b  ℤ và (a, b) = d thì (a/d, b/d) = 1. Ví dụ 1.6. Hãy tìm ước chung lớn nhất của 20 và 45. Bằng cách phân tích ra thừa số nguyên tố ta có 20 = 22×5 và 45 = 32×5. Từ đó, ta tìm được ước chung lớn nhất của 20 và 45 bằng 5, tức là (20, 45) = 5. Ta thấy 4 Thang Long University Libraty (20/5, 45/5) = (4, 9) = 1. Định lý 1.4. Nếu a, b, c  ℤ sao cho a | bc và a, b nguyên tố cùng nhau thì a | c. Định lý 1.5. Cho a, b, c  ℤ. Khi đó (a + cb, b) = (a, b). Ví dụ 1.7. Xét ba số: a = 110, b = 44, c = 22. Theo Định lý 1.4, ta sẽ có (110 + 22×44, 44) = (110, 44) hay (1078, 44) = (110, 44). Để kiểm tra đẳng thức này, ta cần tính (1078, 44) và (110, 44). Ta thấy 44 = 22×11, 110 = 2×5×11 và 1078 = 2×72×11. Từ đó suy ra (1078, 44) = (110, 44) = 22. Kết quả kiểm tra đúng. Định nghĩa 1.6. Cho a, b  ℤ. Tổ hợp tuyến tính (linear combination) của a và b là tổng có dạng ax + by, trong đó x, y  ℤ. Định lý 1.6. Cho hai số a, b  ℤ. Khi đó d = (a, b) là số nguyên dương nhỏ nhất biểu diễn được dưới dạng d = ax + by với x, y  ℤ. Ví dụ 1.8. Giả sử a = 51 và b = 187. Ta thấy 51 = 3×17 và 187 = 11×17. Từ đó (51, 187) = 17. Nếu chọn x = 4, y = - 1, ta có 51×4 - 187×1 = 204 - 187 = 17 = (51, 187). Định lý 1.7. Nếu a, b, m, n  ℤ và c là ước số chung của a và b thì c cũng là ước số của ma + nb, nghĩa là (c | a và c | b) ⇒ c | (ma + nb). Ví dụ 1.9. Giả sử a = 21, b = 39, và c = 3. Ta có 21 = 3×7 và 39 = 3×13. Vì thế, 21 và 39 chia hết cho 3. Giả sử m = 7, n = - 3. Khi đó 7×21 - 3×39 = 147 - 117 = 30. Rõ ràng 3 là ước của 30, vì 30 = 3×10. Định lý 1.8. Nếu a, b là các số nguyên dương thì tập hợp các tổ hợp tuyến tính của a và b là tập các bội nguyên của (a, b). Ví dụ 1.10. Giả sử a = 52, b = 117. Ta thấy 52 = 22×13 và 117 = 32×13. 5 Do đó (52, 117) = 13. Với bất kỳ x, y ∈ ℤ tìm được số nguyên k nghiệm đúng phương trình 52x + 117y = 13k. Tìm x và y cho ta k = 2, tức là x, y thỏa mãn 52x + 117y = 13×2 = 26. Chia cả hai vế cho 13, phương trình rút gọn còn 4x + 9y = 2. Ta tìm được x = 5 và y = - 2, vì 4×5 - 9×2 = 20 - 18 = 2. 1.1.3. Ước chung lớn nhất của nhiều số nguyên Định nghĩa 1.7. Ta mở rộng định nghĩa ước chung lớn nhất cho n số nguyên với n ≥ 2. Xét n số nguyên, không cùng bằng 0. Ta định nghĩa ước chung lớn nhất của chúng là số lớn nhất trong các ước chung của n số đó và viết (a1, a2, ... , an). Ví dụ 1.11. Có thể thấy (2, 6, 14) = 2 và (7, 21, 49) = 7. Tuy nhiên, đôi khi ta gặp nhiều hơn ba số nguyên hoặc nhiều số phức tạp mà ta không thể dễ dàng tìm được ước chung của chúng. Trong những trường hợp như thế, ta có thể dùng định lý sau đây. Định lý 1.9. Nếu a1, a2, ... , an là các số nguyên, không cùng bằng 0, thì (a1, a2, ... , an-1, an) = (a1, a2, ... , (an-1, an)). Ví dụ 1.12. Tìm ước chung lớn nhất của 96, 405, 693 và 1989. Phân tích các số nguyên ra thừa số nguyên tố và dùng Định lý 1.9, ta thấy 96 = 25×3, 405 = 34×5, 693 = 32×7×11, 1989 = 32×13×17. (96, 405, 693, 1989) = (96, 405. (693, 1989)) = (96, 405, 9) = (96, (405, 9)) = (96, 9) = 3. Định lý 1.10. Nếu c, d  ℤ và c = dq + r, với q, r  ℤ thì (c, d) = (r, d). Ví dụ 1.13. Xét đẳng thức 48 = 9×5 + 3. Nếu phân tích đẳng thức này theo Định lý 1.10, ta thấy c = 48, d = 9, q = 5 và r = 3. 6 Thang Long University Libraty Ta có 48 = 24×3 và 9 = 32. Áp dụng định lý ta được (48, 9) = (3, 9) = 3. 1.2. ĐỒNG DƯ Định nghĩa 1.8. Cho a, b  ℤ. Ta nói rằng a đồng dư với b (congruent to) modulo m (viết tắt là mod m) nếu m | (a - b). Ta ký hiệu là a  b (mod m). Nhận xét 1.1. Lưu ý rằng ta có thể biểu diễn m | a bằng a  0 (mod m). Bài tập 1.2. Với bất kỳ a  ℤ ta có: 1. a  a (mod m); 2. Nếu a  b (mod m) thì b  a (mod m); 3. Nếu a  b (mod m) và b  c (mod m) thì a  c (mod m). Nếu a  b (mod m) thì ta có: 1. a + c  b + c (mod m); 2. ac  bc (mod m). Nếu có thêm c  d (mod m) thì ta có: 1. a + c  b + d (mod m); 2. ac  bd (mod m). Ngoài ra, nếu ac  bd (mod m) và c, m nguyên tố cùng nhau thì a  b (mod m). Bây giờ ta có thể phân loại số nguyên thành các lớp dựa trên quan hệ đồng dư modulo m của chúng, với số nguyên m nào đó, m > 1, bằng cách đặt các số nguyên đồng dư với nhau vào cùng một lớp. Mỗi số nguyên chỉ được đặt một và chỉ một lớp như thế và bất kỳ cặp số nguyên x, y lấy ra từ cùng một lớp sẽ thỏa mãn x  y (mod m). Các lớp này gọi là lớp thặng dư modulo m (residue classes), ký hiệu là a m , trong đó a là một phần tử trong lớp đó. Một tập chứa đúng một phần tử của mỗi lớp thặng dư có thể được viết thành ℤ/mℤ. Ví dụ khi m = 4, ta có thể viết ℤ/4ℤ = {0, 1, 2, 3}. Với một số phép toán, cụ thể là cộng, trừ, nhân và lũy thừa, thì một phần tử bất kỳ của lớp là đại diện cho cả lớp, nghĩa là thực hiện các phép toán này 7 trên các phần tử đại diện của hai lớp sẽ cho kết quả lớp thặng dư giống như áp dụng cho phần tử bất kỳ của mỗi lớp đó. Với các phép toán khác, ví dụ ước chung lớn nhất, thì không được. Nhận xét 1.2. Ta có thể tùy ý thay đổi giữa biểu thức đồng dư và biểu thức đại số của một số. Chẳng hạn, phát biểu "n có dạng 4k + 1" tương đương với cách nói rằng n  1 (mod 4). Định lý 1.11. Nếu m, n nguyên tố cùng nhau thì m có nghịch đảo trong phép nhân modulo n. Chứng minh. Vì m, n nguyên tố cùng nhau nên ước chung lớn nhất (m, n) = 1 = am + bn với a, b  ℤ theo Định lý 1.6. Xét phương trình đồng dư (modulo n): 1  am + bn (mod n) ⇒ 1  am + 0  am (mod n). Do đó m có nghịch đảo trong phép nhân modulo n.  1.3. THUẬT TOÁN Ơ-CLIT VÀ MỞ RỘNG Mục này đề cập tới thuật toán Ơ–clít quen thuộc để tìm ước chung lớn nhất của hai số nguyên dương. Đó là thuật toán cực kỳ nhanh để tìm ước chung lớn nhất. Định lý 1.12. (Thuật toán Ơ–clít) Để tìm ước chung lớn nhất của hai số a và b ta đặt r- 1 = a, r0 = b, rồi tính liên tiếp thương qi+1 và số dư ri+1 theo ri-1 = riqi+1 + ri+1 với i = 0, 1, 2, ... cho tới khi gặp số dư rn+1 = 0. Khi đó, số dư khác không cuối cùng rn sẽ là ước chung lớn nhất của a và b. Ví dụ 1.14. Ta minh họa thuật toán Ơ-clít qua việc tìm (246, 699). Lần lượt thực hiện các phép chia sau: 699 = 246×2 + 207 246 = 207×1 + 39 207 = 39×5 + 12 8 Thang Long University Libraty 39 = 12×3 + 3 12 = 3×4 + 0. Thuật toán Ơ-clít nói rằng ước chung lớn nhất của hai số là số dư khác 0 cuối cùng. Ở ví dụ trên, số dư khác 0 cuối cùng là 3 nên (246, 699) = 3. Nếu muốn tìm ước chung lớn nhất của nhiều hơn hai số thì ta có thể sử dụng thuật toán Ơ-clít, kết hợp với Định lý 1.9. Ví dụ 1.15. Sử dụng thuật toán Ơ-clít tìm (33, 176, 275, 352, 539, 1331). • Trước hết tìm (539, 1331) bằng cách sử dụng thuật toán Ơ-clít. Ta có 1331 = 539×2 + 253 539 = 253×2 + 33 253 = 33×7 + 22 33 = 22×1 + 11 22 = 11×2 + 0. Số dư khác 0 cuối cùng là 11. Vì thế, (539, 1331) = 11. • Tiếp theo là tìm (33, 176, 275, 352, 11) = (33, 176, 275, (352, 11)). Ta có 352 = 11×32 + 0. Số dư bằng 0, vì thế (352, 11) = 11. • Tiếp theo ta tìm (33, 176, 275, 11) = (33, 176, (275, 11)). Ta có 275 = 11×25 + 0, tức 275 là bội của 11 và (275, 11) = 11. • Tiếp theo tìm (33, 176, 11) = (33, (176, 11)). Do 176 = 11×16 + 0 nên (176, 11) = 11. • Cuối cùng, tìm (33, 11) = (11×3, 11) = 11. Kết quả là (33, 176, 275, 352, 539, 1331) = 11.  Biểu diễn d = (a, b) dưới dạng tổ hợp tuyến tính của a và b Ta đã biết cách tìm ước chung lớn nhất của hai số nguyên bằng thuật toán Ơ-clít. Giả sử rn = (a, b), a > b, rn-2 = rn-1×qn + rn và rn-1 = rn×qn+1 + 0. 9 Khi ta muốn viết ước chung lớn nhất của hai số nguyên dưới dạng một tổ hợp tuyến tính của những số nguyên này, ta sử dụng quy trình sau. Đẳng thức (a, b) = rn = rn-2 - rn-1×qn cho thấy (a, b) là một tổ hợp tuyến tính của rn-2 và rn-1. Từ đẳng thức trước đó rn-3 = rn-2×qn-1 + rn-1 suy ra rn-1 = rn-3 - rn-2×qn-1. Vì vậy, ta nhận được rn = rn-2 - (rn-3 - rn-2×qn-1)×qn = rn-2(1 + qn-1×qn) - qn×rn-3. Biểu thức cuối cho thấy rn là một tổ hợp tuyến tính của rn-2 và rn-3. Ta tiếp tục quá trình "biểu diễn (a, b) như tổ hợp tuyến tính của mỗi cặp số dư" cho tới khi tìm được (a, b) như tổ hợp tuyến tính của a và b. Với cặp số dư ri và ri-1 ta có biểu diễn (a, b) = k×ri + m×ri-1. Do ri = ri-2 - ri-1×qi nên ta có (a, b) = k×(ri-2 - ri-1×qi) + m×ri-1. = k×ri-2 + (m - k×qi)ri-1 Tiếp tục cho tới đẳng thức đầu a = b×q1 + r1, ta sẽ tìm được (a, b) như một tổ hợp tuyến tính của a và b. Định lý sau đưa ra phương pháp quy nạp để tìm (a, b) dưới dạng một tổ hợp tuyến tính của a và b. Định lý 1.13. Cho a, b là hai số nguyên dương. Khi đó, ta có biểu diễn d = (a, b) = kn×a + mn×b với kn và mn là số hạng thứ n của dãy số được xác định theo đệ quy bởi k -1 = 1, m -1 = 0, k0 = 0, m0 = 1 và ki = ki -2 - ki -1×qi, mi = mi -2 - mi -1×qi với i = 1, 2, ... , n, trong đó qi là thương số của phép chia thứ i trong thuật toán Ơ-clít tìm ước chung lớn nhất của a và b. 10 Thang Long University Libraty Ví dụ 1.16. Tìm số nguyên x và y sao cho 161x + 1274y = (161, 1274). Trước hết ta sử dụng thuật toán Ơ-clit để tìm (161, 1274). Ta có 1274 = 161×7 + 147, 161 = 147×1 + 14, 147 = 14×10 + 7, 14 = 7×2 + 0. Số dư khác 0 cuối cùng là 7, vì thế (161, 1274) = 7. Bây giờ sử dụng phép thay thế theo hướng ngược lại để tìm cách biểu diễn 7 như một tổ hợp tuyến tính của 161 và 1274. Ta có 7 = 147 - 14×10, = 147 - (161 - 147)×10, = 11×147 - 161×10, = 11×(1274 - 161×7) - 161×10, = - 87×161 + 11×1274. Kết quả: một nghiệm nguyên của phương trình 161x + 1274y = (161, 1274) = 7 là x = - 87, y = 11 (Kiểm tra lại: 1274×11 - 161×87 = 14014 - 14007 = 7). 1.4. PHƯƠNG TRÌNH ĐI-Ô-PHĂNG TUYẾN TÍNH Định nghĩa 1.9. Phương trình Đi-ô-phăng là phương trình đa thức với các hệ số nguyên và nghiệm của phương trình cũng là các số nguyên. Ví dụ 1.17. Sau đây là một số phương trình Đi-ô-phăng bậc 1, 2 và 3: 3x + 2y = 13; 5x2 - 3y2 - 4x + 2y + 7 = 0; x3 + y3 = z3. Phương trình Đi-ô-phăng đơn giản nhất là phương trình Đi-ô-phăng tuyến tính: a1x1 + a2x2 + ... + anxn = b (n nguyên, n  1), 11 (2.1) trong đó a1, a2, ... , an, b  ℤ và a1, a2, ... , an không cùng bằng 0. Ví dụ phương trình tuyến tính hai biến: ax + by = c với a, b, c ∈ ℤ. Vấn đề đặt ra là xác định xem một phương trình tuyến tính đã cho có nghiệm nguyên hay không? Nếu có thì tìm tất cả các nghiệm nguyên của phương trình? Định lý sau đây cho một điều kiện cần và đủ cho sự tồn tại nghiệm nguyên của phương trình tuyến tính (2.1). Định lý 1.14. Cho a, b và c  ℤ với a, b không cùng bằng 0. Phương trình tuyến tính ax + by = c có nghiệm nguyên khi và chỉ khi d = (a, b) là ước của c. Chứng minh. (⇒) Giả sử x0 và y0 là một nghiệm nguyên. Khi đó ax0 + by0 = c. Do d | a và d | b nên theo Định lý 1.7, d | (ax0 + by0), tức d là ước của c. (⇐) Giả sử d | c. Khi đó c = d×k với k  ℤ. Theo Định lý 1.6, có thể viết (a, b) như một tổ hợp tuyến tính của a và b. Do đó, tồn tại u, v ∈ ℤ thỏa mãn d = a×u + b×v. Nhân hai vế với k ta được c = d×k = a(u×k) + b(v×k). Chứng tỏ phương trình ∎ ax + by = c có nghiệm nguyên x = u×k, y = v×k). Ví dụ 1.18. Tìm nghiệm của phương trình 126x + 54y = 11. Sử dụng thuật toán Ơ-clit ta tìm được (126, 54) = 18. Do 11 không chia hết cho 18 nên theo Định lý 1.14, phương trình đã cho không có nghiệm nguyên. Định lý 1.14 được mở rộng cho phương trình có nhiều hơn hai biến. Định lý 1.15. Cho a1, a2 ,..., an , c  ℤ và a1, a2 ,..., an  0 . Phương trình tuyến tính a1 x1  a2 x2  ...  an xn  c có nghiệm nguyên khi và chỉ khi c chia hết cho d  a1 , a2 ,...,a n . Hơn nữa, nếu phương trình có nghiệm nguyên thì phương trình sẽ có vô số nghiệm nguyên. Chứng minh. (⇒) Giả sử x1 , x2 ,..., xn là một nghiệm. Khi đó a1 x1  a 2 x 2  ...  a n x n  c . Do d a1 , d a 2 ,..., d a n nên theo Định lý 1.7,   d a1 x1  a2 x2  ...  an xn , 12 Thang Long University Libraty tức d là ước của c hay c chia hết cho d  a1 , a2 ,...,a n . (⇐) Giả sử d  a1 , a2 ,..., a n và d c . Ta chứng minh phương trình a1 x1  a2 x2  ...  an xn  c . có vô số nghiệm nguyên. Muốn thế, ta dùng phương pháp quy nạp. Định lý 2.2 cho thấy điều khẳng định này đúng với n = 2. Giả sử điều này đúng với n = k, tức là phương trình a1 x1  a2 x2  ...  ak xk  c với d  a1 , a2 ,..., a k  c có vô số nghiệm. Ta sẽ chỉ ra phương trình với n = k+1 biến a1 x1  a2 x2  ...  ak xk  ak 1 xk 1  c với d  a1 , a2 ,..., a k , ak 1  c cũng có vô số nghiệm. Thật vậy, ta tìm cách đưa phương trình với n = k+1 biến a1 x1  a2 x2  ...  ak xk  ak 1 xk 1  c với d  a1 , a2 ,..., a k , ak 1  c về phương trình Đi-ô-phăng tuyến tính với k biến. Giả sử c  d  p với p là số nguyên. Theo Định lý 1.8, tập tất cả các tổ hợp tuyến tính của ak xk  ak 1 xk 1 trùng với tập tất cả các bội nguyên của ak , ak 1  . Vì thế với các nghiệm nguyên xk , xk 1 và p, phương trình Đi-ô-phăng tuyến tính ak xk  ak 1 xk 1  ak , ak 1  p có vô số nghiệm. Do đó phương trình được rút gọn chỉ còn k biến a1 x1  a2 x2  ...  ak 1 xk 1  ak , ak 1   p  c (*) Theo Định lý 1.9, d  a1 , a2 ,...,a k , ak 1   a1 , a2 ,..., ak 1 , ak , ak 1  . Do đó nếu c chia hết cho d thì c cũng chia hết cho a1 , a2 ,..., ak 1 , ak , ak 1  . 13 Vì thế, theo giả thiết quy nạp, phương trình (*) có vô số nghiệm ( do (*) cũng là phương trình Đi-ô-phăng tuyến tính k biến) và ta hoàn thành chứng minh định lý theo quy nạp. Tóm lại, chương này đã trình bày lại một số khái niệm cơ bản của lý thuyết số: ước số và phần dư, số nguyên tố và hợp số, ước chung lớn nhất, thuật toán Ơ-clit, đồng dư và bài toán tìm nghiệm nguyên của phương trình Đi-ô-phăng tuyến tính và điều kiện tồn tại nghiệm nguyên của phương trình Đi-ô-phăng tuyến tính. 14 Thang Long University Libraty Chương 2 GIẢI PHƯƠNG TRÌNH TUYẾN TÍNH HỆ SỐ NGUYÊN Chương này đề cập tới khái niệm nghiệm nguyên riêng và nghiệm nguyên tổng quát của phương trình tuyến tính với các hệ số nguyên của hai hay nhiều biến số. Tiếp đó trình bày hai thuật toán, khác với thuật toán Ơ-clit đã biết, tìm nghiệm nguyên tổng quát của phương trình và chứng minh tính đúng đắn của các thuật toán, cùng với các ví dụ số minh họa thuật toán. Nội dung của chương được tham khảo chủ yếu từ tài liệu [2] và [4]. 2.1. NGHIỆM NGUYÊN RIÊNG VÀ NGHIỆM NGUYÊN TỔNG QUÁT Xét phương trình tuyến tính n biến a1x1 + a2x2 + . . . + anxn = b, (2.1) trong đó mọi ai  0 và mọi ai, b  ℤ (ℤ - tập các số nguyên). Giả sử h  ℕ (ℕ - tập các số tự nhiên) và fi : ℤh  ℤ, i = 1, ... , n (hàm của n đối số nguyên và nhận giá trị nguyên). Sau đây ta nêu một số khái niệm cần thiết. Định nghĩa 2.1. x0 = (x 10 , ... , x 0n ) là một nghiệm nguyên riêng của phương trình (2.1) nếu mọi x i0  ℤ và a1x 10 + ... + anx 0n = b. Định nghĩa 2.2. x = (f1(k1, ... , kh), ... , fn(k1, ... ,kh)) là một nghiệm nguyên tổng quát của phương trình (2.1) nếu: a) a1f1(k1, ... , kh) + ... + anfn(k1, ... ,kh) = b, k = (k1, ... , kh)  ℤh và b) Với mỗi nghiệm nguyên riêng x0 = (x 10 , ... , x 0n ) của phương trình (2.1) đều tồn tại k0 = (k 10 , ... , k 0h )  ℤh sao cho x i0 = fi(k 10 , ... , k 0h ), i = 1, ... , n. Nghiệm nguyên tổng quát có thể được biểu diễn bởi các hàm tuyến tính. Với 1  i  n ta xét các hàm fi = ci1k1 + ... + cihkh + di với ci1, ... , cih, di  ℤ. Định nghĩa 2.3. A = (cij)nh gọi là ma trận tương ứng với nghiệm nguyên tổng quát của phương trình (2.1). 15 Định nghĩa 2.4. Các số nguyên k1, ... , ks, 1  s  h, gọi là độc lập nếu các cột tương ứng của ma trận A là độc lập tuyến tính. Định nghĩa 2.5. Một nghiệm nguyên là s - lần bất định nếu số tối đa các tham số độc lập bằng s. Định lý 2.1. Nghiệm nguyên tổng quát của (2.1) là (n - 1) - lần bất định. Có thể xem chứng minh định lý trong [2], tr. 4 - 6. Trước khi trình bày thuật toán mới, ta nhắc lại công thức tính nghiệm nguyên tổng quát đã biết, dựa trên ước chung lớn nhất. Với phương trình hai biến ta có: Định lý 2.2. Cho a, b  ℤ và d = (a, b). Phương trình ax + by = c có nghiệm nguyên khi và chỉ khi d là ước của c. Nếu d | c thì phương trình có vô số nghiệm nguyên. Hơn nữa, nếu x = x0, y = y0 là một nghiệm nguyên riêng của phương trình thì nghiệm tổng quát của phương trình có dạng x = x0 + b a ×k và y = y0 - ×k với k  ℤ. d d  Để tìm nghiệm nguyên riêng của phương trình ax + by = c ta sử dụng Định lý 1.13 và Thuật toán Ơ-clit mở rộng (xemVí dụ 1.16). Ví dụ 2.1. Tìm nghiệm riêng và nghiệm tổng quát của phương trình: 10x + 4y = 16 (a = 10, b = 4 và c = 16). Thuật toán Ơ-clit cho ta d = (10, 4) = 2. Do d = 2 là ước của c = 16 nên theo Định lý 1.14, phương trình đã cho có nghiệm. Để tìm nghiệm riêng x 0, y0 của phương trình, áp dụng thuật toán Ơ-clit mở rộng, ta tìm được 2 = 10×1 - 4×2. Nhân hai vế với 8 ta có 16 = 108 + 4(- 16). Từ đó cho thấy: x0 = 8, y0 = - 16 là một nghiệm riêng của phương trình. Theo Định lý 2.2, nghiệm tổng quát của phương trình đã cho có dạng: 10k 4k x=8+ = 8 + 2k, y = - 16 = - 16 - 5k, k ∈ ℤ. 2 2  Định lý 2.2 được mở rộng cho phương trình với nhiều hơn hai biến số. 16 Thang Long University Libraty Ví dụ 2.2. Tìm các nghiệm nguyên của phương trình 4x + 8y + 5z = 7. Ta thấy (4, 8) = 4. Phương trình đã cho trở thành (4, 8)(x + 2y) + 5z = 7. Nếu đặt w = x + 2y thì có thể viết 4w + 5z = 7. Dễ dàng thấy rằng (4, 5) = 1. Do 7 chia hết cho 1 vì 7 = 1×7 (k = 7). Theo Định lý 2.2, phương trình này có vô số nghiệm. Để tìm một nghiệm riêng w0, z0, áp dụng thuật toán Ơ-clit mở rộng, ta tìm được 1 = 4×(- 1) + 5×1 ⇒ 4(- 7) + 57) = 7. Suy ra nghiệm riêng w0 = - 7, z0 = 7. Theo Đl 2.2, nghiệm tổng quát của phương trình 4w + 5z = 7 là w = - 7 + 5n, z = 7 - 4n, n ∈ ℤ. Tiếp theo, ta tìm x và y từ phương trình x + 2y = w hay x + 2y = - 7 + 5n với (1, 2) = 1 là ước số của - 7 + 5n. Có thể thấy phương trình này có một nghiệm riêng là x0 = - 7 + 5n và y0 = 0. Từ đó nghiệm tổng quát của phương trình là x = x0 + 2p, y = y0 - p và z = 7 - 4n, n, p ∈ ℤ ⇔ x = - 7 + 5n + 2p, y = - p và z = 7 - 4n, n, p ∈ ℤ. • Ta có thể giải phương trình theo một cách khác (ghép y với z). Kết quả ta nhận được nghiệm tổng quát với các tham số khác là s và m. x = 1 + s, y = 6 - 8s + 5m và z = - 9 + 12s - 8m, s, m ∈ ℤ. • Có thể chỉ ra rằng các tham số s, m liên hệ với các tham số n, p theo hệ thức s = 5n + 2p - 8 và m = 8n + 3p - 14. Tóm lại, nghiệm tổng quát của phương trình đã cho phụ thuộc hai tham số nguyên n và p (hoặc s và m) như đã nêu trên. 2.2. THUẬT TOÁN GIẢM DẦN HỆ SỐ Thuật toán nhằm xác định xem phương trình tuyến tính với hệ số nguyên có nghiệm nguyên hay không, nếu có thì đưa ra nghiệm tổng quát của phương trình. 17  Đầu vào: Phương trình tuyến tính a1x1 + ... + anxn = b với ai, b  ℤ, xi là ẩn số nguyên cần tìm, i = 1, ... , n, và ít nhất một ai  0.  Đầu ra: Cho biết phương trình có nghiệm nguyên hay không. Nếu phương trình có nghiệm nguyên thì cho ra nghiệm tổng quát của phương trình. Thuật toán gồm 9 bước như sau: Bước 1. Tính d = (a1, ... , an) - ước chung lớn nhất của a1, ... , an. Bước 2. Nếu d | b (d là ước của b hay b chia hết cho d) thì "phương trình có nghiệm nguyên": Chuyển tới Bước 3. Nếu d ∤ b (b không chia hết cho d) thì "phương trình không có nghiệm nguyên": Dừng thuật toán. Bước 3. Đặt h ;= 1. Nếu |d|  1 thì chia phương trình cho d. Đặt lại ai := ai / d, i = 1, ... , n, b := b / d. Bước 4. Tính số a = min |ai| và xác định chỉ số i sao cho |ai| = a. a i 0 Bước 5. Nếu a  1 thì chuyển tới Bước 7. Bước 6. Nếu a = 1 thì: (A) Đặt xi = - (a1x1 + ... + ai-1xi-1 + ai+1xi+1 + ... + anxn - b)ai. (B) Thay giá trị của xi vào biểu thức của các biến đã được xác định ở Bước 8. (C) Lần lượt gán các tham số nguyên k1, k2, ... , kn-1 cho các biến ở vế phải các biểu thức của những biến đã được xác định. (D) Ghi lại nghiệm tổng quát vừa nhận được trên đây và dừng thuật toán. Bước 7. Viết mỗi aj, j  i dưới dạng: aj = aiqj+ rj, j  i, b = aiq + r với 0  rj < ai, 0  r < ai và a j  b qj =   , q =   ([x] là số nguyên lớn nhất nhỏ hơn hay bằng x). ai  ai  Bước 8. Đặt xi = - q1x1 - ... - qi-1xi-1 - qi+1xi+1 - ... - qnxn + q - th. Thay giá trị của xi vào biểu thức của các biến đã được xác định trước đó ở Bước 8. Bước 9. Đặt lại a1 := r1, ... , ai-1 := ri-1, ai+1 = ri+1, ... , an := rn và 18 Thang Long University Libraty ai := - ai, b := r, xi = th, h := h + 1. và trở lại Bước 4 với phương trình mới: a1x1 + ... + ai-1xi-1 + aith + ai+1xi+1 + ... + anxn = b.  Để minh họa cho thuật toán nêu trên, ta xét ví dụ sau. Ví dụ 2.3. Tìm nghiệm nguyên của phương trình với các hệ số nguyên 4 ẩn: 6x1 - 12x2 - 8x3 + 22x4 = 14. Giải. Áp dụng thuật toán vừa trình bày: 1. Ước chung lớn nhất d = (6, - 12, - 8, 22) = 2. 2. Do 2 | 14 (2 là ước số của 14) nên phương trình có nghiệm nguyên. 3. Đặt h := 1. Do |d| = |2|  1 nên chia hai vế của phương trình cho 2 ta được: 3x1 - 6x2 - 4x3 + 11x4 = 7. Ghi lại các hệ số của phương trình: a1 = 3, a2 = - 6, a3 = - 4, a4 = 11 và b = 7. 4. Tính số a := min {|3|, |- 6|, |- 4|, |11|} = 3 chỉ số đạt min i = 1. 5. Do a  1 nên chuyển tới Bước 7. 7. Viết lại các hệ số aj, j  i = 1 ở dạng: a2 = - 6 = 3(- 2) + 0 (q2 = - 2, r2 = 0), a3 = - 4 = 3(- 2) + 2 (q3 = - 2, r3 = 2), a4 = 11 = 33 + 2 (q4 = 3, r4 = 2), b = 7 = 32 + 1 (q = 2, r = 1). 8. Đặt x1 = 2x2 + 2x3 − 3x4 + 2 − t1 (biến x1 đã được xác định). 9. Đặt lại a2 := 0, a3 := 2, a4 := 2 và a1 := - 3, b := 1, x1 := t1, h := 2. Trở lại Bước 4 với phương trình mới - 3t1 + 0.x2 + 2x3 + 2x4 = 1. 4. Tính số a := min {|- 3|, |2|, |2|} = 2 và chỉ số đạt min i = 3. 5. Do a  1 nên chuyển sang Bước 7. 7. Viết lại các hệ số aj, j  i = 3 ở dạng: 19 (a) a1 = - 3 = 2(- 2) + 1 (q1 = - 2, r1 = 1), a2 = 0 = 20 + 0 (q2 = 0, r2 = 0), a4 = 2 = 21 + 0 (q4 = 1, r4 = 0), b = 1 = 20 + 1 (q = 0, r = 1). 8. Đặt x3 = 2t1 + 0.x2 - x4 + 0 - t2. (biến x3 đã được xác định). (b) Thay giá trị của x3 vào biểu thức của biến x1 đã xác định theo (a), ta được x1 = 2x2 - 5x4 + 3t1 - 2t2 + 2. (c) 9. Đặt lại a1 := 1, a2 := 0, a4 := 0 và a3 := - 2, b := 1, x3 := t2, h := 3. Trở lại Bước 4 với phương trình mới: 1.t1 + 0.x2 - 2t2 + 0.x4 = 1. 4. Tính số a := min {|1|} = 1 và chỉ số đạt min i = 1. 5. Do a = 1 nên thực hiện Bước 6. 6. (A) t1 = - (0.x2 - 2t2 + 0.x4 - 1)1 = 2t2 + 1. (B) Thay giá trị của t1 vào các biểu thức của x1 và x3 đã xác định trước đây theo (c) và (b), ta nhận được: x1 = 2x2 - 5x4 + 4t2 + 5 và x3 = - x4 + 3t2 + 2. (C) Lần lượt gán tham số x2 ;= k1, x4 := k2, t2 := k3 với k1, k2, k3  ℤ. (D) Nghiệm tổng quát của phương trình ban đầu là: x1 = 2k1 - 5k2 + 4k3 + 5, x2 = k1, x3 = - k2 + 3k3 + 2, x4 = k2 với k1, k2, k3  ℤ. Kiểm tra lại cho thấy nghiệm này thỏa mãn phương trình tuyến tính đã cho.   Để chứng minh tính đúng đắn của thuật toán, ta cần tới các bổ đề sau đây. Bổ đề 2.1. Thuật toán trên đây là hữu hạn. 20 Thang Long University Libraty
- Xem thêm -

Tài liệu liên quan