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 = 54 + 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
p1p2 ... pk = a thì tích p1p2 ... 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 = 223; 18 = 232; 231 = 3711.
Đị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)nh 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 = 108 + 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) + 57) = 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 = 33 + 2 (q4 = 3, r4 = 2),
b = 7 = 32 + 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 = 20 + 0 (q2 = 0, r2 = 0),
a4 = 2 = 21 + 0 (q4 = 1, r4 = 0),
b = 1 = 20 + 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 -