M

U

Nhi u bƠi toán th c t d n đ n các ph
v i h s nguyên mƠ ta ph i tìm đ
ph

ng trình nƠy. Ph

ph ng tuy n tính.

ng trình, h ph

ng trình tuy n tính

c nghi m nguyên c a ph

ng trình nh th th

ng đ

c g i lƠ ph

ơy lƠ m t ch đ quan tr ng trong ch

ng trình vƠ h
ng trình

i-ô-


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
h ph
ph

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

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

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 a h ph

ng trình tuy n tính v i h s nguyên.

1

c xét. Tìm nghi m nguyên d

ng


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


chung l n nh t c a hai hay nhi u s nguyên, thu t toán
nh t vƠ đ c p t i bƠi toán tìm nghi m nguyên c a ph

-clit tìm

c chung l n

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
trình. N i dung c a ch

ng đ

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

c

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
lƠ đ n v (units), m i

c t m th

ng (trivial divisors) c a a; 1 vƠ -1 g 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
không có

c th c s . S nguyên d

c th c s . N u a lƠ s nguyên d

ng a > 1 g i m t lƠ s nguyên t (prime) n u a

c c a 20 lƠ ±1, ±2, ±4, ±5, ±10. T đó,

20 lƠ ±1, ±2, ±4. Vì th ,

c c a 8 lƠ

c chung c a 8 vƠ

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í d 1.6. Hưy tìm

và (a, b) = d thì (a/d, b/d) = 1.

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


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


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 

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


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

M c nƠy đ c p t i thu t toán
c a hai s nguyên d

฀

R NG

–clít quen thu c đ tìm

c chung l n nh t

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

ta đ t r- 1 = a, r0 = b, r i tính liên ti p th

cùng.

-clít nói r ng

c chung l n nh t c a hai s lƠ s d khác 0 cu i

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


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 đ
h p tuy n tính c a a vƠ b.
d

nh lý sau đ a ra ph

c (a, b) nh m t t

ng pháp quy n p đ tìm (a, b)

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


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

s nguyên vƠ nghi m c a ph



vƠ a1, a2, ... , an không cùng b ng 0. Ví d ph

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

.

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

tuy n tính ax + by = c có nghi m nguyên khi và ch khi d = (a, b) là

ng trình

c c a c.


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, a 2 ,..., a n , c  và a1, a 2 ,..., a n  0 . Ph

ng trình tuy n tính

a1 x1  a 2 x2  ...  a n xn  c có nghi m nguyên khi và ch khi c chia h t cho
d  a1 , a 2 ,...,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 đó
a 1 x1  a 2 x2  ...  a n xn  c .

Do d a 1 , d a 2 ,..., d a n nên theo



nh lý 1.7,



d a1 x1  a 2 x2  ...  a n xn ,

12


a1 x1  a 2 x2  ...  a k xk  a k1 xk1  c v i d  a1 , a 2 ,..., a k , a k 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  a 2 x2  ...  a k xk  a k1 xk1  c v i d  a1 , a 2 ,..., a k , a k 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 a k xk  a k1 xk1 trùng

v i t p t t c các b i nguyên c a a k , a k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
a k xk  a k1 xk1  a k , a k1  p
có vô s nghi m.
Do đó ph

ng trình đ

c rút g n ch còn k bi n

-clit,

i-ô-ph ng tuy n tính vƠ

ng trình i-ô-ph ng tuy n tính.

14

Thang Long University Libraty


Ch

GI I PH
Ch

ng 2

NG TRỊNH TUY N TÍNH H S

NGUYÊN

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
nguyên t ng quát c a ph


 , 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
trình (2.1) n u m i x i0 

ng

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) 
b) V i m i nghi m nguyên riêng x0 = (x 10 , ... , x 0n ) c a ph
t n t i k0 = (k 10 , ... , k 0h ) 

h

h

vƠ

ng trình (2.1) đ u

sao cho x i0 = fi(k 10 , ... , k 0h ), i = 1, ... , n.


c chung l n nh t. V i ph

nh lỦ 2.2. Cho a, b 
nguyên khi và ch khi d là

và d = (a, b). Ph

ng trình hai bi n ta có:

ng trình ax + by = c có nghi m

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
thì nghi m t ng quát c a ph
x = x0 +

ng trình có d ng

b
a
×k và y = y0 - ×k v i k  .
d
d

tìm nghi m nguyên riêng c a ph



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
Theo



ng trình.

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
Ta th y (4, 8) = 4. Ph


.

c s c a - 7 + 5n.

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

ng trình.

c nh sau:

B

c 1. Tính d = (a1, ... , an) -

B

c 2. N u d | b (d lƠ

c chung l n nh t c a a1, ... , an.

c c a b hay b chia h t cho d) thì "ph

nghi m nguyên": Chuy n t i B
"ph

ng

c 3. N u d

ng trình có

b (b không chia h t cho d) thì

ng trình không có nghi m nguyên": D ng thu t toán.
B


(C) L n l

B

c 8.

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 đ
B

c xác đ nh

c 7. Vi t m i aj, j  i d

c trên đơy vƠ d ng thu t toán.

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 


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Ơ
3.

c s c a 14) nên ph

ng trình có nghi m nguyên.

t h := 1. Do |d| = |2|  1 nên chia hai v c a ph

ng trình cho 2 ta đ

c:

c xác đ nh).

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
7. Vi t l i các h s aj, j  i = 3

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

Thay giá tr c a x3 vƠo bi u th c c a bi n x1 đư xác đ nh theo (a), ta đ

(b)
c


(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


Ch ng minh. Gi s a1x1 + a2x2 + ... + anxn = b lƠ ph

ng trình tuy n tính ban

đ u, v i ít nh t m t ai  0. B ng cách đánh s l i các bi n vƠ đ i d u hai v c a
ph



ng trình sau luôn nh h n a tr

ng h p nƠy (a = 1) thu t toán d ng

B đ 2.2. Gi s ph

c, ta nh n đ
B

c 6.

฀

ng trình tuy n tính có d ng:
a1x1 + a2x2 + ... + anxn = b,

v i min a s = a1 và ph
a s 0

c đó.

(2.2)

ng trình
- a1t1 + r2x2 + ... + rnxn = r,

(2.3)

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

- a1t 10 + r2x 02 + … + rnx 0n = r


t1 = t 10 , x2 = x 02 , … , xn = x 0n là m t nghi m riêng c a ph

ng trình (2.3).

฀

B đ 2.3. xi = ci1k1 + ci2k2 + ... + cin-1kn-1 + di, i = 1, ... , n là nghi m t ng quát
c a ph

ng trình (2.2) khi và ch khi

t1 = - (c11 + q2c21 + ... + qncn1)k1 - ... - (c1n-1 + q2c2n-1 + ... + qncnn-1)kn-1 - (d1 + q2d2 + ... + qndn) + q,
xj = cj1k1 + ... + cjn-1kn-1 + dj, j = 2, . . . , n.
là nghi m t ng quát c a ph

ng trình (2.3).

Ch ng minh. t1 = t 10 = - x 10 - q2x 02 - … - qnx 0n + q, x2 = x 02 , … , xn = x 0n lƠ m t
nghi m riêng c a ph
nghi m riêng c a ph

ng trình (2.2)
ng trình (2.3)

x1 = x 10 , x2 = x 02 , … , xn = x 0n lƠ m t
k1 = k 10  , … , kn = k 0n 


฀

ng trình tuy n tính a1x1 + a2x2 + ... + anxn = b v i

22

Thang Long University Libraty


min a s = a1 và ai = a1qi, i = 2, ... , n.
a s 0

Khi đó, nghi m t ng quát c a ph

ng trình là

x1 = - (q2k2 + ... + qnkn - q),
xi = ki  , i = 2, ... , n.
Ch ng minh. Chia hai v c a ph

ng trình cho a1 vƠ áp d ng B đ 2.4.

฀

nh lỦ 2.3 (Tính đúng đ n c a thu t toán). Thu t toán cho nghi m t ng quát
c a ph

ng trình tuy n tính a1x1 + a2x2 + ... + anxn = b v i ai, b 

và ai  0.


sau khi thu t toán đư th c hi n m t s vòng l p (theo các B đ 2.2 vƠ 2.3), t B
đ 2.3 suy ra r ng vi c nh n đ
ban đ u t

ng đ

ng v i tính nghi m t ng quát c a ph

nghi m t ng quát c a ph
nh lý đư đ

2.5).

c nghi m t ng quát c a ph

ng trình đó đ

ng trình tuy n tính

ng trình

B

c 6 A) mƠ

c cho b i thu t toán (theo B đ 2.4 vƠ

c ch ng minh xong.


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

23


= (a1, ... , an) lƠ
s , ph

c chung l n nh t c a a1, ... , an. Theo đ nh lý đư bi t c a lý thuy t

ng trình (2.5) có nghi m nguyên khi vƠ ch khi d | b (d lƠ

N u ph

ng trình có nghi m nguyên vƠ d  1, ta chia ph

c c a b).

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

c mô t nh sau:
ng trình tuy n tính

a1x1 + ... + anxn = b, ai, b  , ai   1, i = 1, ... , n
v i ít nh t m t ai  0 vƠ (a1, ... , an) = 1, t c

c chung l n nh t c a a1, ... , an b ng 1.

u ra: Nghi m nguyên t ng quát c a ph
Thu t toán d ng l p g m 5 b

(2.6)

ng trình.

c nh sau:

B

c 1.

B

c 2. Tìm r vƠ c p ch s (i, j) sao cho

t h := 1 (s bi n nguyên m i), p := 1 (s bi u th c c a bi n m i).



min r : r  a i mod a j , 0  r  a j

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



b .



(A) Th các giá tr v a tính c a xi vƠ xj vƠo m i bi u th c (p), p = 1, 2, ...
(n u có th ).
(B) T bi u th c cu i cùng ( p ) nh n đ
bi u th c tr

c trong thu t toán, th vƠo các

c đó ( p - 1), ( p - 2), ... , (1) n u p > 1.

(C) M i bi u th c k t ( p - 1) c n áp d ng cùng m t thao tác nh
sau đó l n l



c 2 v i ph

ng trình m i:
n

asxs

rxi + ajth +

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

(B),

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.