Header Page 1 of 133.

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.

Footer Page 1 of 133.

1


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.

Footer Page 3 of 133.

3


Header Page 4 of 133.

4

Thang Long University Library


Header Page 5 of 133.

(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

= (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.

Footer Page 6 of 133.

6

Thang Long University Library


Header Page 7 of 133.

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);

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

Footer Page 8 of 133.

8

Thang Long University Library


Header Page 9 of 133.

39 = 12×3 + 3
12 = 3×4 + 0.


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.

Footer Page 10 of 133.

10

a1x1 + a2x2 + ... + anxn = b (n nguyên, n  1),

Footer Page 11 of 133.

11

(2.1)


Header Page 12 of 133.

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

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  .

Footer Page 13 of 133.


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).

Footer Page 15 of 133.

15


Header Page 16 of 133.

Đị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

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ố.

Footer Page 16 of 133.

16

Thang Long University Library


Header Page 17 of 133.

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 ∈ ℤ.

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à

Footer Page 18 of 133.

18

Thang Long University Library



19

(a)


Header Page 20 of 133.

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à:


a s 0

Tiếp tục như vậy, sau một số hữu hạn bước, ta nhận được (ở Bước 4) a = 1.
Thực ra, theo nhận xét vừa rồi, a của phương trình sau luôn nhỏ hơn a trước đó.


Trong trường hợp này (a = 1) thuật toán dừng ở Bước 6.
Bổ đề 2.2. Giả sử phương trình tuyến tính có dạng:
a1x1 + a2x2 + ... + anxn = b,

(2.2)

với min a s = a1 và phương trình
a s 0

- a1t1 + r2x2 + ... + rnxn = r,

(2.3)

với t1 = - x1 - q2x2 - ... - qnxn + q, trong đó ri = ai - a1qi, i = 2, ... , n, r = b - a1q và

a 
qi =  i  , q =
 a1 

b
 a  ([x] - số nguyên lớn nhất  x).
 1


t1 = - (c11 + q2c21 + ... + qncn1)k 10 - ... - (c1n-1 + q2c2n-1 + ... + qncnn-1) k 0n1 - (d1 + q2d2 + ... + qndn) + q = - x 10 - q2x 02 - … - qnx 0n + q = t 10 .



Bổ đề 2.4. Phương trình tuyến tính
a1x1 + a2x2 + ... + anxn = b

(2.4)

với |a1| = 1 có nghiệm tổng quát
x1 = - (a2k2 + ... + ankn - b) a1,
xi = ki  ℤ, i = 2, ... , n.
Chứng minh. Xét một nghiệm riêng của phương trình (2.4)
x1 = x 10 , x2 = x 02 , … , xn = x 0n .
Tồn tại k2 = x 02 , … , kn = x 0n sao cho
x1 = - (a2x 02 + … + anx 0n - b) a1 = x 10 , x2 = x 02 , … , xn = x 0n .



Bổ đề 2.5. Xét phương trình tuyến tính a1x1 + a2x2 + ... + anxn = b với

Footer Page 22 of 133.

22

Thang Long University Library


Header Page 23 of 133.


a1x1 + a2x2 + ... + anxn = b với mọi ai, b  ℤ và ai  0.

(2.5)

Trường hợp ai, b  ℚ (ℚ - tập các số hữu tỉ), i = 1, ... , n, được qui về trường
hợp trên bằng cách qui đồng mẫu số các số hữu tỉ và khử mẫu số chung. Ký hiệu d

Footer Page 23 of 133.

23


Header Page 24 of 133.

= (a1, ... , an) là ước chung lớn nhất của a1, ... , an. Theo định lý đã biết của lý thuyết
số, phương trình (2.5) có nghiệm nguyên khi và chỉ khi d | b (d là ước của b).
Nếu phương trình có nghiệm nguyên và d  1, ta chia phương trình cho d. Khi
đó d = 1.
Có hai trường hợp đặc biệt:
a) Nếu mọi ai = 0 thì phương trình có nghiệm nguyên tổng quát là xi = ki  ℤ,
i = 1, ... , n, khi b = 0 (đó là trường hợp duy nhất có nghiệm nguyên tổng
quát là n - lần bất định) và phương trình vô nghiệm khi b  0.
b) Nếu i, 1  i  n, sao cho ai =  1 thì nghiệm nguyên tổng quát là
n


xi = ai  b   a s k s  và xs = ks  ℤ, s  {1, ... , n} \ {i}.


s 1,s i


xi := r   a j t h   a s x s  b ,
s 1


si , j



Footer Page 24 of 133.

24

Thang Long University Library


Header Page 25 of 133.



ai  r n
r  ai
. asxs 
xj := r  a i t h 
a j s1
aj

si , j



= b.

s 1
si , j

Để minh họa thuật toán, ta xét ví dụ sau.
Ví dụ 2.4. Tìm nguyện nguyên của phương trình
17x1 - 7x2 + 10x3 = - 12 (a1 = 17, a2 = - 7, a3 = 10, b = - 12).
Giải. Áp dụng thuật toán vừa mô tả.
1. Đặt h = 1, p = 1.
2. Với cặp chỉ số (1, 2): min {|r| : r  17 (mod - 7), 0 < |r| < 7} = 3.
Với cặp chỉ số (2, 1): min {|r| : r  - 7 (mod 17), 0 < |r| < 17} = 7.
Với cặp chỉ số (1, 3): min {|r| : r  17 (mod 10), 0 < |r| < 10} = 3.

Footer Page 25 of 133.

25