Quan hệ chia hết
1.1.1 Định nghĩa Cho a, b ∈ Z, b 6= 0 Ta nói a chia hết cho b (b chia hết a), kí hiệu: a b (hay b|a) nếu ∃c ∈ Z sao cho a = bc Khi a b ta nói a là một bội của b hay b là một ước của a.
1.1.2 Tính chất 1 0 b,∀b ∈ Z, b 6= 0, chỉ có duy nhất số 0 có tính chất này.
2 ±1 là ước của mọi số nguyên, chỉ có ±1 có tính chất này.
3 Nếu mỗi số hạng của một tổng chia hết cho một số thì tổng củng chia hết cho số đó.
1.1.3 Ví dụ 1 6 2 hay 2|6 Ta nói 6 là bội của 2 hay 2 là ước của 6.
2 12 6 5 Ta nói 12 không phải là bội của 5 hay 5 không phải là ước của 12.
Phép chia có dư
1.2.1 Định lý (Định lý cơ bản về phép chia có dư)
(i) Cho a, b ∈ N, b 6= 0 Khi đó tồn tại duy nhất một cặp só tự nhiên q và r sao cho a=bq + r, trong đó 06 r < b
(ii) Cho a, b ∈ Z, b 6= 0 Khi đó tồn tại duy nhất một cặp số nguyên q, r sao cho a=bq + r, trong đó 0 6 r < |b|
Chứng minh Ta chứng minh từng trường hợp.
(i) Xét tập hợp M = {bx|x ∈ N, bx 6 a}
Vì vậy M là tập con khác rỗng bị chặn trên bởi a của N, nên M có số lớn nhất Gọi số đó là bq
(Vì bq + b > bq và bq là số lớn nhất của M)
⇒b(q + 1) > a ⇔bq +b > a ⇔b > a−bq Đặt r = a - bq ⇒ 06 r < b (vì bq 6 a, a−bq < b)
Giả sử a = bq+r = bq’ + r’, với 0 6 r, r 0 < r
Ta có bq 6 bq +r = bq 0 + r 0 < bq 0 +b = b(q 0 + 1)
Tương tự ta có: q > q 0 ⇒ q = q 0 ⇒ bq = bq 0 ⇒ a−bq = a−bq 0 ⇒r = r 0
(ii) Ta xét 4 trường hợp:
Trường hợp 1: a > 0, b > 0 đã chứng minh ở (i)
Trường hợp 2: a > 0, b < 0 Áp dụng (i) đối với 2 số tự nhiên a và (-b), tồn tại duy nhất cặp số tự nhiên q’, r’ sao cho: a = −bq 0 +r 0 ,0 6 r 0 < −b
=> q, r là cặp số nguyên duy nhất và a = bq +r, 0 6 r < |b|
Trương hợp 3: a 6 0, b > 0 Áp dụng (i) đối với 2 số tự nhiên –a và b, tồn tại duy nhất cặp số tự nhiên q’, r’ sao cho:
Nếu r 0 6= 0, ta có b(−q 0 −1) + (b−r 0 ) Đặt q = -q’ – 1, r = b – r’ suy ra q, r củng là cặp số nguyên duy nhất và a = bq +r,0 6 r < b
Trường hợp 4: a 6 0, b < 0 Áp dụng (i) đối với 2 số tự nhiên –a và -b, tồn tại duy nhất cặp số tự nhiên q’, r’ sao cho
Nếu r 0 6= 0, thì a = b(q’-1)+(b-r) Đặt q = q’ – 1, r = b – r’ suy ra q, r củng là cặp số nguyên duy nhất sao cho a = bq +r,06 r < b
1.2.2 Định nghĩa Cặp số q và r xác định trong Định lý 1.2.1 thì q được gọi là thương và r được gọi là số dư trong phép chia a cho b.
Ước chung lớn nhất
Số nguyên d khác 0 được xem là ước chung của hai số a và b khi d chia hết cho cả a và b Nếu d là ước chung dương lớn nhất của a và b, thì d phải chia hết cho tất cả các ước chung của a và b.
1.3.3 Định lý Cho a, b ∈ Z Khi đó d = (a, b) tồn tại duy nhất.
Chứng minh Sự tồn tại: Trước hết ta có nhận xét (a,b) = (-a,-b) = (-a,b)
= (a,-b) Vì vậy không mất tính tổng quát ta có thể giả sử a > 0, b > 0
∀d ∈ Z, d 6= 0 ta luôn có d|0, nên ta có thể giả sử a>0, b>0. Đặt M = {ax+by;x, y ∈ Z}
Giả sử α ∈ M, tồn tại các số nguyên u, v ∈ Z sao cho α = au + bv, từ đó suy ra −α = a(−u) + b(−v) cũng thuộc M Điều này chứng tỏ trong M có số nguyên dương Vì tập hợp các số tự nhiên N có tính chất sắp thứ tự tốt, nên mọi tập con của N đều có số bé nhất, dẫn đến việc trong M tồn tại số nguyên dương bé nhất Gọi d là số nguyên dương bé nhất trong M, với d = (a, b) Theo định lý cơ bản của phép chia có dư, với các cặp (a, d) và (b, d), ta có a = dq + r, với 0 ≤ r < d, và b = dq₀ + r₀, với 0 ≤ r₀ < d, từ đó r = a - dq và r₀ = b - dq₀.
Vì d ∈ M nên ∃x, y ∈ Z : d= ax+by Thay vào (*) ta có: r = a−(ax+by)q = a(1−xq) +b(−yq) ∈ M r 0 = b−(ax+ by)q 0 = a(−xq 0 ) +b(1−yq 0 ) ∈ M
⇒ r, r 0 ∈ M,0 6 r, r 0 < d mà d là số nguyên dương bé nhất thuộc M nên r = r 0 = 0 ⇒a = dq, b = dq 0 ⇒d|a, d|b
Tiếp theo chúng ta chứng minh d chia hết cho mọi ước chung của a và b Giả sử d 0 là ước chung nào đó của a và b Ta có:
(d 0 |a ⇒d 0 |ax d 0 |b ⇒d 0 |by ⇒ d0|(ax+by) hay d 0 |d
Vậy ∀a, b ∈ Z tồn tại ước chung lớn nhất của a và b.
Chứng minh tính duy nhất:
Giả sử d và d’ đều là ƯCLN(a,b) Ta có: d|d 0 vì d’ là ƯCLN(a,b) và d 0 |d vì d là ƯCLN(a,b).
Ta lại có d, d’ >0 Suy ra d = d’.
1 Cho a, b ∈ Z Nếu d = (a, b) thì ∃u, v ∈ Z : d = au+bv
2 Nếu d là một ước chung của a và b và ∃u, v ∈ Z sao cho d = au + bv thì d = (a,b)
1.3.5 Định nghĩa Choa1, a2, , an ∈ Z Khi đó(a1, a2, , an) = ((a1, a2), a3, , an)
1.3.6 Ví dụ ( minh họa Đinh nghia 1.3.5 )
1.3.7 Bổ đề Nếu a = bq + r thì (a,b) = (b,r).
Chứng minh Ta chứng minh tập các ước chung của a và b trùng với tập các ước chung của b và r.
Giả sử d là ước chung của a và b => d|a, d|b => d|(a−bq) => b|r.
Vậy d là ước của b và r Giả sử d là ước chung của b và r, suy ra d|b, d|r do đó d|(bq +r) hay d|a.
Vậy d là ước chung của a và b.
1.3.8 Thuật toán Eucide Bài toán: Cho a, b ∈ Z Tìm (a,b)
Không mất tính tổng quát giả sử |a| > |b|
Theo định lý cơ bản về phép chia có dư ta có: a = bq +r,0 6 r < |b|
Nếu r 6= 0 thì (a,b) = (b,r) Chuyển sang bước 2.
Nếu r 1 6= 0 thì (b, r) = (r, r 1 ) Chuyển sang bước 3.
Quá trình tiếp tục nhưng không vô hạn vì ta có dãy giảm ngặt các số tự nhiên
Trong đó r n là số dư cuối cùng khác 0 Ta viết lại như sau: a = bq+ r,06 r < |b| b = rq 1 +r 1 ,0 6 r 1 < r r = r 1 q 2 +r 2 ,06 r 2 < r 1
Giải: Áp dụng các bước của bài toán trên ta có:
Đồng dư thức
1.4.1 Định nghĩa Cho m ∈ N Hai số nguyên a và b được gọi là đồng dư theo mô đun m nếu chúng có cùng số dư khi chia cho m.
1.4.2 Nhận xét Cho m ∈ N, m > 1, a, b ∈ Z Khi đó các phát biểu sau là tương đương:
1.4.3 Các tính chất của quan hệ đồng dư
- Nếu a ≡b(mod m) thì a ≡ b+ km(mod m), k ∈ Z
2 Nếu a ≡ b(mod m), c ≡d(mod m) thì ac ≡ bd(mod m)
- Nếu a ≡b(mod m) thì ac ≡ bc(mod m),∀c ∈ Z
3 Nếu a ≡ b(mod m) và d|a, d|b,(d, m) = 1 thì a d ≡ b d(mod m)
THUẬT TOÁN TÌM NGHIỆM NGUYÊN CỦA PHƯƠNG TRÌNH DIOPHANTINE TUYẾN TÍNH
Chúng tôi trình bày hai thuật toán tìm nghiệm nguyên của phương trình Diophantine tuyến tính và đưa ra các ví dụ minh họa.
2.1 Nghiệm nguyên của phương trình Diophantine tuyến tính
2.1.1 Định nghĩa Phương trình Diophantine tuyến tính là phương trình bậc nhất có dạng: a1x1 +a2x2 + +anxn = b (1) trong đó a i , b ∈ Z,∀i = 1,2,3 , n; a 1 , a 2 , , a n không đồng thời bằng 0.
2.1.2 Ví dụ 1 Phương trình: 5x + 6y = 7 là phương trình Diophantine tuyến tính hai biến.
2 Phương trình 3x + 2y – 4z = 3 là phương trình Diophantine tuyến tính ba biến.
2.1.3 Định lý Phương trình dạng: ax + by =c (1’) trong đó a, b, c ∈ Z;ab 6= 0 có nghiệm nguyên khi và chỉ khi d|c với d = (a,b).
Chứng minh “ Nếu phương trình (1’) có nghiệm nguyên thì d = (a,b) ” Giả sử phương trình (1’) có nghiệm nguyên (x 0 , y 0 ) Khi đó ax 0 + by 0 = c.
Do d =(a,b) nên a d, b d ⇒ ax 0 d, by 0 d ⇒ ax 0 +by 0 d hay c d
“Nếu d = (a,b) thì phương trình (1’) có nghiệm nguyên”: c d = (a, b) nên c 1 ∈ Z : c = dc 1 Do d=(a,b) nên ∃u, v ∈ Z : d = au+bv ⇒ c = (au + bv)c 1 = a(uc 1 ) + b(vc 1 ) ⇒ (x 0 = uc 1 , y 0 = vc 1 ) là nghiệm của phương trình (1’).
2.1.4 Ví dụ 1 Phương trình 3x + 4y = 5 có nghiệm nguyên vì (3,4)\5
2 Phương trình 108x + 96y = 25 không có nghiệm nguyên vì
(108,96) mà 12 không phải là ước của 25.
2.1.5 Định lý Nếu phương trình (1’) có nghiệm nguyên (x 0 , y 0 ) thì phương trình sẽ có vô số nghiệm và tập nghiệm được xác định như sau:
x = x 0 + b dt y = y 0 − a dt t ∈ Z Định lý 2.1.3 được mở rộng cho phương trình Diophantine nhiều biến như sau
2.1.6 Định lý Phương trình Diophantine a 1 x 1 +a 2 x 2 + +a n x n = b (2) trong đó a i , b ∈ Z, các a i không đồng thời bằng 0, ∀i = 1,2,3 , n; có nghiệm nguyên khi và chỉ khi d|b với d = (a 1 , a 2 , , a n ).
Nếu (2) có 1 nghiệm thì (2) có vô số nghiệm.
Sau đây là khái niệm nghiệm nguyên riêng, nghiệm nguyên tổng quát của phương trình Diophantine tuyến tính.
2.1.7 Định nghĩa x 0 = (x 0 1 , x 0 2 , , x 0 n ) được gọi là một nghiệm nguyên riêng của phương trình (1) nếu: x 0 i ∈ Z,∀i = 1,2,3 , n và a 1 x 0 1 + a 2 x 0 2 + + a n x 0 n = b
2.1.8 Định nghĩa x i = f i (k 1 , , k h ), i = 1,2, , n là một nghiệm nguyên tổng quát của phương trình (1) nếu: a) n
Phương trình P i=1 a i f i (k 1 , , k h ) = b có nghiệm nguyên riêng x i = x 0 i cho mọi i từ 1 đến n, tồn tại cho mọi (k 0 1 , , k h 0 ) ∈ Z h Điều này có nghĩa là bất kỳ nghiệm nguyên nào cũng có thể được trích xuất từ nghiệm tổng quát thông qua tham số hóa, với x 0 i = f i (k 1 0 , , k h 0) cho mọi i từ 1 đến n.
Chúng ta sẽ thấy rằng nghiệm tổng quát có thể được thể hiện bởi một hàm tuyến tính.
2.1.9 Định nghĩa Một nghiệm nguyên là s-lần bất định nếu số tham số độc lập lớn nhất là s.
2.1.10 Định lý Nghiệm nguyên tổng quát của (1) là (n-1) lần bất định. Chứng minh Xem [3] trang 4-6
Định lý 2.1.11 khẳng định rằng nghiệm nguyên tổng quát của phương trình tuyến tính thuần nhất a₁x₁ + a₂x₂ + + aₙxₙ = 0, với mọi aᵢ ∈ Z\{0}, có thể biểu diễn dưới dạng xᵢ = cᵢ₁k₁ + cᵢ₂k₂ + + cᵢₙkₙ cho i = 1, 2, , n, với d₁ = d₂ = = dₙ = 0 Chứng minh cho điều này bắt đầu bằng giả thiết rằng nghiệm nguyên tổng quát được viết dưới dạng xᵢ = n - 1.
Phương trình P j=1 cijPj + di, với i = 1, 2, , n và các d i không đồng thời bằng 0, có thể được biểu diễn dưới dạng (3) Phương trình thuần nhất này có nghiệm tầm thường x 1 = x 2 = = x n = 0 Do đó, tồn tại một tập hợp (p 0 1 , , p 0 n−1 ) thuộc Z n−1 sao cho n−1.
Thay thế: P j = p 0 j + k j , j = 1,2, , n −1 trong dạng được thể hiện ở phần đầu, ta sẽ thu được dạng (3).
Thật vậy: Ta có xi n−1
2.1.12 Định nghĩa (3) được gọi là dạng chuẩn của nghiệm nguyên tổng quát của phương trình tuyến tính thuần nhất (2’).
2.1.13 Ví dụ 1 Địnhlý2.1.5 là một ví dụ cho nghiệm nguyên riêng và nghiệm tổng quát Nếu(x 0 , y 0 )là nghiệm nguyên riêng của phương trình Diophantine
x = x 0 + b dt y = y 0 − a dt t∈ Z là nghiệm nguyên tổng quát của phương trình Diophantine 2 biến (1’).
Cụ thể: Phương trình 3x - 2y = -1 có một nghiệm nguyên riêng là
(x0 = 1, y0 = 2) nên nghiệm tổng quát của phương trình này là:
2 Tìm các nghiệm nguyên của phương trình
Theo Định lý 2.1.6, phương trình (4) có nghiệm vì ước chung lớn nhất của (2, 6, 9) là 1, và điều này cho thấy phương trình không chỉ có một nghiệm duy nhất mà còn có vô số nghiệm Hiện tại, chúng ta sẽ tìm tập nghiệm cho phương trình (4).
Ta có: (2,6) = 2 nên phương trình (4) tương đương với phương trình
2(x+3y) + 9z = 10. Đặt u = x + 3y, ta được phương trình:
Ta có (2,9) = 1 nên theo Định lý 2.1.5 phương trình (5) có vô số nghiệm.
Dễ thấy u 0 = −4, z 0 = 2 là một nghiệm nguyên riêng của phương trình (5).
Ta có nghiệm tổng quát của phương trính (5) là:
Do (1;3)=1 nên 1\(−4 + 9t) nên phương trình (6) có nghiệm (theo tham số t) Phương trình (6) có một nghiệm nguyên riêng là: x 0 = −4, y 0 = 3t Ta có nghiệm tổng quát của phương trình (6) là:
Vậy phương trình (4) có nghiệm tổng quát là:
Nhận xét: Nghiệm tổng quát của phương trình 3 ẩn (4) phụ thuộc vào 2 tham số t và s.
Nghiệm nguyên tổng quát của phương trình tuyến tính không thuần nhất được xác định bằng cách cộng nghiệm nguyên tổng quát của phương trình tuyến tính thuần nhất tương ứng với nghiệm nguyên riêng của phương trình tuyến tính không thuần nhất.
Chứng minh Giả sử rằng x i n−1
Phương trình tuyến tính thuần nhất có nghiệm nguyên tổng quát được biểu diễn dưới dạng P j=1 c ij k j, với i = 1, 2, , n Giả sử rằng xi = vi, với i = 1, 2, , n là nghiệm nguyên riêng của phương trình tuyến tính không thuần nhất Do đó, x i n−1 sẽ được xem xét trong bối cảnh này.
P j=1 c ij k j +v i , i = 1,2, , nlà nghiệm nguyên tổng quát của phương trình tuyến tính không thuần nhất.
(đúng theo định nghĩa nghiệm của phương trình)
Nếu x i = x 0 i (i = 1, 2, , n) là nghiệm nguyên tổng quát của phương trình tuyến tính không thuần nhất, thì x i = x 0 i − v i (i = 1, 2, , n) sẽ là nghiệm nguyên riêng của phương trình tuyến tính thuần nhất Do đó, tồn tại (k 1 0, , k 0 n−1) thuộc về tập hợp các nghiệm này.
P j=1 cijk j 0 +vi = x 0 i , i= 1,2, , n.Vậy định lý đã được chứng minh.
Các thuật toán tìm nghiệm nguyên của Dophantine tuyến tính
Thuật toán 1 giúp xác định xem một phương trình tuyến tính có nghiệm nguyên hay không, và nếu có, thuật toán cũng sẽ xác định nghiệm tổng quát của phương trình đó.
Phương trình tuyến tính a 1 x 1 + +a n x n = b, a i ,b ∈ Z x i là ẩn nhận giá trị nguyên, các a i không dồng thời bằng 0, i = 1,2, , n Đầu ra:
Khẳng định phương trình có nghiệm nguyên hay không, và nếu phương trình có nghiệm nguyên thì đưa ra nghiệm tổng quát.
Tìm ước chung lớn nhất của các hệ số Gọi d = (a 1 , a 2 , , a n )
Nếu b d thì kết luận: “phương trình có nghiệm nguyên” và chuyển sang bước
3 Nếu b 6 d thì kết luận: “ 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| 6= 1, chia phương trình cho d. Đặt a i := a i /d, i := 1,2, , n, b := b/d
Tìm a = min a s 6=0|a s | và xác định i sao cho |a i | = a
Nếu a 6= 1 thì chuyển sang Bước 7.
(B) Thay các giá trị của x i vào giá trị của các ẩn số đã xác định.
(C) Thay các tham số nguyênk 1 , k 2 , , k n−1 cho tất cả các biến ở vế phải tương ứng.
(D) Viết thông báo nghiệm tổng quát được xác định Dừng.
Viết ra tất cả các a j , j 6= i dưới dạng: a j = a i q j +r j , q j a j a i b = aiq +r;q b a i
Viết x i = −(q 1 x 1 + q i−1 x i−1 +q i+1 x i+1 + +q n x n ) +q−t h Thay giá trị của x i trong các giá trị của các ẩn số xác định khác.
2.2.2 Bổ đề Thuật toán trên là hữu hạn
Giả sử phương trình tuyến tính ban đầu được biểu diễn dưới dạng a1x1 + + anxn = b, với ai và b thuộc Z, trong đó tất cả ai không đồng thời bằng không Để kiểm tra điều kiện min |as| = a1 ≠ 1 (nếu không thì tiến hành đánh số lại) Theo thuật toán, khi chúng ta chuyển từ phương trình ban đầu sang một phương trình mới, ta có a0.
Khi thực hiện các bước, nếu min a s ≠ 0 và 0 < min a s ≠ 1|a s|, chúng ta tiếp tục quy trình tương tự Sau một số bước hữu hạn, đến bước 4, giá trị a sẽ trở thành 1 (trên thực tế, a luôn nhỏ hơn giá trị trước đó, như đã lưu ý) Trong trường hợp này, thuật toán sẽ kết thúc.
2.2.3 Bổ đề Giả sử phương trình tuyến tính là: a 1 x 1 + +a n x n = b (7) với min a s 6=0|a s | = a 1 và phương trình
Khi đó x 1 = x 0 1 , x 2 = x 0 2 , , x n = x 0 n là nghiệm riêng của phương trình (7) khi và chỉ khi t 1 = t 0 1 = −x 0 1 −q 2 x 0 2 − −q n x 0 n +q; x 2 = x 0 2 , , x n = x 0 n là nghiệm riêng của phương trình (8)
Chứng minh x 1 = x 0 1 , x 2 = x 0 2 , , x n = x 0 n nghiệm riêng của phương trình
⇔t 1 = t 0 1 , x 2 = x 0 2 , , x n = x 0 n là nghiệm riêng của phương trình (8).
2.2.4 Bổ đề x i = c i1 k 1 + +c in−1 k n−1 +d i , i = 1,2, , n (9) là nghiệm tổng quát của phương trình (7) khi và chỉ khi t 1 = −(c 11 + q 2 c 21 + +q n c n1 )k 1 − −(c 1n−1 +q 2 c 2n−1 + +q n c nn−1 )k n
−(d 1 +q 2 d 2 + +q n d n ) +q, x j = c 1j k 1 + +c jn−1 k n−1 +d j , j = 2,3, , n là nghiệm tổng quát của phương trình (8).
Chứng minh t 1 = t 0 1 = −x 0 1 −q 2 x 0 2 − −q n x 0 n +q, x 2 = x 0 2 , , x n = x 0 n là một nghiệm riêng của phương trình (8)
⇔x 1 = x 0 1 , x 2 = x 0 2 , , x n = x 0 n là một n nghiệm riêng của phương trình (7)
⇔ ∃k 1 = k 1 0 ∈ Z, , k n = k 0 n ∈ Z sao cho x i = c i1 k 0 1 + +c in−1 k 0 n−1 + d i x 0 i , i = 2,3, , n và t 1 = −(c 11 + q 2 c 21 + +q n c n1 )k 1 0 − −(c 1n−1 +q 2 c 2n−1 + +q n c nn−1 )k n−1 0
2.2.5 Bổ đề Phương trình tuyến tính a 1 x 1 + +a n x n = b với |a 1 |= 1 (10) có nghiệm tổng quát:
Chứng minh Giả sử x 1 = x 0 1 , x 2 = x 0 2 , , x n = x 0 n là một nghiệm riêng của phương trình (10).
2.2.6 Bổ đề Xét phương trình tuyến tính a 1 x 1 + +a n x n = b với min a s 6=0|a s | = a 1 và a i = a 1 q i , i= 2,3, , n
Thế thì nghiệm tổng quát của phương trình là
Chứng minh Chia phương trình cho a 1 và áp dụng Bổ đề??.
Thuật toán đã được xác minh tính đúng đắn, cho phép tính toán chính xác nghiệm tổng quát của phương trình tuyến tính dạng a1x1 + + anxn = b, với điều kiện tất cả các hệ số ai không đồng thời bằng không.
Thuật toán được chứng minh là hữu hạn theo Bổ đề 2.2.2 Tính đúng đắn của các bước 1, 2 và 3 là rõ ràng Ở bước 4, ta luôn có giá trị min a s khác 0, vì các a i không đồng thời bằng 0.
Tính đúng đắn ở bước 6(A) được xác nhận qua Bổ đề 2.2.5 và Bổ đề 2.2.6 Thuật toán này cho phép tìm nghiệm tổng quát của phương trình ban đầu thông qua các nghiệm tổng quát của phương trình tuyến tính sau một số vòng lặp, như đã trình bày trong Bổ đề 2.2.3 và Bổ đề 2.2.4 Bổ đề 2.2.4 chỉ ra rằng nghiệm tổng quát của phương trình tuyến tính ban đầu tương đương với việc tìm nghiệm tổng quát của phương trình ở bước 6(A), mà nghiệm tổng quát đã được đưa ra trong thuật toán (theo Bổ đề 2.2.5 và Bổ đề 2.2.6) Định lý đã được chứng minh một cách đầy đủ.
Chú ý: Ở Bước 4 của thuật toán này ta xéta := min a s 6=0{|a s |}sao cho số lần lặp lại càng nhỏ càng tốt Thuật toán vẫn thực hiện nếu ta đặt a := |a i | 6= max s=1,n
{|a s |} nhưng phải mất thời gian lâu hơn Thuật toán này có thể đưa vào một chương trình máy tính. Ứng dụng:
Tìm nghiệm nguyên của phương trình: 22x 1 −12x 2 + 8x 3 −6x 4 = 18
Giải: Áp dụng tuần tự các bước của thuật toán.
Bước 1.Tìm ước chung lớn nhất của các hệ số của ẩn: d = (22,-12,8,-6) = 2Bước 2 Ta có: d =2; b nên d là ước của b Vì vậy phương trình đã cho có nghiệm nguyên.
Bước 3 h:=1; |2| 6= 1 , chia hai vế của phương trình cho 2, ta được phương trình:
Bước 4 a := min a s 6=0{|a s |}= min a s 6=0{|11|,|−6|,|4|,|−3|} = 3, i = 4 Bước 5 a 6= 1, chuyển sang bước 7
4 a := min a s 6=0{|a s |} = min a s 6=0{|2|,|1|,|3|} = 1, i= 3 ( Do a = 1 nên thức hiện bước 6)
(B) Thay thế giá trị của x 3 vào x 4 ta thu được x 4 = x 1 −x 2 −4t 1 −3 (C) Thay x 1 = k 1 , x 2 = k 2 , t 1 = k 3 ta có nghiệm nguyên tổng quát của phương trình ban đầu là:
Với k 1 , k 2 , k 3 là các tham số nhận giá trị nguyên.
Trong phần 2.2.7, chúng tôi giới thiệu một thuật toán mới nhằm tìm nghiệm nguyên cho phương trình tuyến tính thông qua việc sử dụng phép đồng dư Cụ thể, xét phương trình tuyến tính có dạng: a1x1 + a2x2 + + anxn = b, với điều kiện rằng tất cả các hệ số ai và b đều thuộc tập số nguyên Z, và không có ai nào đồng thời bằng 0 cho i = 1, 2, , n.
Trường hợp a i , b ∈ Q, i = 1,2, , n được đưa về trường hơp 1 bằng cách qui đồng mẫu số và khử mẫu số chung.
Nếu d không phải là ước của b, phương trình sẽ không có nghiệm nguyên Ngược lại, nếu d là ước của b, phương trình sẽ có nghiệm nguyên, theo một định lý nổi tiếng trong lý thuyết số học.
Nếu phương trình có nghiệm và d khác 1, ta có thể nhân cả hai vế của phương trình với d Trong trường hợp d = 1, chúng ta vẫn giữ tính tổng quát bằng cách xem xét ước chung lớn nhất là một số dương.
Nếu a_i = 0 với mọi i từ 1 đến n, phương trình sẽ có nghiệm nguyên tổng quát là x_i = k_i ∈ Z khi b = 0 Đây là trường hợp duy nhất mà phương trình có n nghiệm tổng quát Ngược lại, nếu b khác 0, phương trình sẽ không có nghiệm.
(b) Nếu ∃i,1 6 i 6 n sao cho a i = ±1 thì nghiệm tổng quát của phương trình là: x i = −a i ( n
Thuật toán có thể được viết như dưới đây: Đầu vào: phương trình: a 1 x 1 +a 2 x 2 + + a n x n = b (15) a i , b ∈ Z, a i 6= ±1, i = 1,2, , n với tất cả các a i không đồng thời bằng 0 và (a 1 , , a n ) = 1. Đầu ra:
Nghiệm nguyên tổng quát của phương trình.
1 6 i,j 6 n{|r|, r = a i (moda j ),|r| < |a j |}và xác định r và cặp (i,j) mà r đạt giá trị nhỏ nhất ( khi có nhiều kết quả giống nhau ta chọn một trong các kết quả đó)
Bước 3 Nếu |r| 6= 1 ta thực hiện bước 4.
(A) Thay các giá trị đã xác định của các ẩn số vào tất cả các biểu thức (p), p=1,2, ( nếu có thể).
(B) Từ biểu thức cuối cùng (p) có được trong thuật toán này thay thế vào tất cả các biểu thức (p−1),(p−2),
(C)Mỗi biểu thức bắt đầu theo thứ tự từ (p−1) phải được áp dụng giống như cách làm ở (B): sau đó (p−2),(p−3), tương ứng.
(D) Viết giá trị của các ẩn x i , i= 1,2, , ntừ phương trình ban đầu Thay các tham số nguyên k 1 , k 2 , k n−1 tương ứng với các ẩn ở vế phải Dừng.
Bước 4 Viết biểu thức (p): x j = t h − a i −r aj x i
Bước 5 Gán: x j := t h ; h := h+ 1 ai := r; p := p+ 1Các hệ số và biến khác vẫn không thay đổi, quay lại bước 2.
Tính đúng đắn của thuật toán:
Hãy xét phương trình tuyến tính a 1 x 1 + a 2 x 2 + + a n x n = b, a i , b ∈ Z, a i 6= ±1, i = 1,2, , n
Ta có các tính chất sau.
2.2.8 Bổ đề Tập M = {|r|, r = a i (moda j ),0 < |r| < |a j |} có giá trị nhỏ nhất.
Chứng minh Hiển nhiên M ⊂ N ∗ và M là hữu hạn vì phương trình có hữu hạn các hệ số: n, và có tối đa n 2 các cặp (ai, aj).
Thật vậy, điều kiện M = ∅ tương đương với việc ai ≡ 0(modaj) cho mọi i, j từ 1 đến n Sự tương đương này chỉ xảy ra khi |ai| = |aj| cho mọi i, j từ 1 đến n, dẫn đến (a1, , an) = ai cho mọi i từ 1 đến n Tuy nhiên, theo giả thiết (a1, , an) = 1, vì nếu (a1, , an) = d với d khác 1, ta có thể chia cả hai vế của phương trình cho d.
Mâu thuẫn với giả thiết ai 6= ±1,∀i = 1,2, , n ở trên Vậy M 6= ∅ và hữu hạn Do đó M có giá trị nhỏ nhất.
Chứng minh Ta giả sử ngược lại: ∃i 0 ,1 6 i0 6 n sao cho |r| > |a i 0 | Khi đó |r| > min
|a p 0 | > |a j | và a p 0 không chia hết cho a j 0
Trong phương trình có hệ số |a j 0 |, đây là số nhỏ nhất và các hệ số không đồng nhất Điều này ngụ ý rằng (a 1, , a n) không thể bằng a 1 = ±1 Hơn nữa, các hệ số có giá trị tuyệt đối lớn hơn |a j 0 | không phải tất cả đều chia hết cho |a j 0 |, nếu không thì (a 1, , a n) sẽ bằng a j 0 khác ±1.
Trong bài viết này, chúng ta xem xét một số nguyên \( q_0 \in Z \) và \( r_0 = a_{p_0} - q_0 a_{j_0} \in Z \) Theo đó, ta có \( a_{p_0} = r_0 \, (\text{mod} \, a_{j_0}) \) với điều kiện \( 0 < |r_0| < |a_{j_0}| \leq 6|r| \) Do đó, việc tồn tại một \( |r_0| < |r| \) sẽ dẫn đến mâu thuẫn với định nghĩa về giá trị nhỏ nhất của \( r \).
2.2.10 Bổ đề Nếu |r| = minM = 1 đối với cặp chỉ số (i, j) thì
X s=1 s / ∈{i,j} a s k s + r −ai a j b) xs = ks, s ∈ {1,2, , n} \ {i, j} là một nghiệm nguyên tổng quát của phương trình (15).
Chứng minh Đặt (x 0 1 , x 0 2 , , x 0 n ) là một nghiêm nguyên riêng của phương trình (15) Khi đó ∃k s = x 0 s ∈ Z, s = {1,2, , n} \ {i, j} và t h = x 0 j + a i −r aj x 0 i ∈ Z (vì a i −r ∈ M a j ) sao cho: x i = r(−a j (x 0 j + a i −r a j x 0 i )− n
Thay giá trị x i , i = 1,2, n vào phương trình (15) ta được một đẳng thức đúng.
2.2.11 Bổ đề Giả sử |r| 6= 1và (i,j) là cặp chỉ số mà r đạt được giá trị nhỏ nhất Hãy xét hệ phương trình tuyến tính sau:
Khi đó x e = x 0 e , e = 1,2, , n là nghiệm nguyên riêng của phương trình (15) khi và chỉ khi x e = x 0 e , e ∈ {1,2, , n} \ {j} và t h = t 0 h = x 0 j + a i −r aj x i là một nghiệm nguyên riêng của phương trình (16).
Chứng minh xe = x 0 e , e = 1,2, , n là nghiệm riêng của phương trình (15) khi và chỉ khi n
⇔ xe = x 0 e , e ∈ {1,2, , n} \ {j} và th = t 0 h là nghiệm nguyên riêng của phương trình (16)
2.2.12 Bổ đề Thuật toán trên là hữu hạn
Khi |r|= 1, thuật toán dừng lại ở bước 3 Đối với trường hợp |r| ≠ 1, theo định nghĩa, |r| thuộc N* Chúng ta sẽ chứng minh rằng giá trị r sẽ giảm ít nhất 1 sau mỗi vòng lặp Giả sử giá trị ban đầu là r1 Nếu |r1| ≠ 1, chúng ta thực hiện Bước 4 và sau đó là Bước 5, theo Bổ đề 2.2.9.
Chúng ta sẽ áp dụng thuật toán lần thứ hai, trong đó phương trình (theo Bước 5) sẽ thay thế r1 Theo Bổ đề 2.2.9, giá trị |r| mới được viết lại thành |r2| và có tính chất |r2| < |r1|.
Ta sẽ có |r| = 1 vì |r| > 1 và |r| < ∞, và nếu |r| 6= 1, theo thuật toán một lần nữa ta có |r| < |r 1 | và tiếp tục như thế Do đó thuật toán hữu hạn bước.
Tính đúng đắn của thuật toán:
Thuật toán tính nghiệm tổng quát của phương trình tuyến tính.