Đăng ký Đăng nhập
Trang chủ Về sự tồn tại nghiệm nguyên của một số dạng phương trình điôfan...

Tài liệu Về sự tồn tại nghiệm nguyên của một số dạng phương trình điôfan

.PDF
53
355
61

Mô tả:

MỞ ĐẦU Nhiều bài toán thực tế dẫn tới các phương trình đại số với hệ số là các số nguyên và đòi hỏi nghiệm của phương trình cũng là các số nguyên. Chẳng hạn, dựng tam giác vuông có ba cạnh a, b, c là các số nguyên, nghĩa là tìm bộ ba số nguyên (a, b, c) thỏa mãn hệ thức a2 + b2 = c2. Một số phương trình loại này đã quen thuộc ở bậc học phổ thông. Tuy nhiên còn nhiều loại phương trình như thế cũng rất đáng được quan tâm tìm hiểu và học tập. Phương trình Điôphăng là phương trình đại số đòi hỏi tìm nghiệm hữu tỉ hoặc nghiệm nguyên. Phương trình đại số là phương trình chỉ bao gồm các biểu thức đa thức của một hoặc nhiều biến số. Tính "Điôphăng" của phương trình biểu hiện ở chỗ các hệ số của đa thức phải là các số hữu tỉ (hoặc số nguyên) và nghiệm cũng chỉ có thể là số hữu tỉ (hoặc số nguyên). Có rất nhiều dạng phương trình Điôphăng, đơn giản và được giải quyết trọn vẹn hơn cả là phương trình Điôphăng tuyến tính của hai hay nhiều biến số, trong đó tất cả hệ số của các biến đều là các số nguyên (hay nói chung là các số hữu tỉ). Hai dạng phương trình quen biết từ thời sơ khai của lý thuyết số, có từ trước thời Điôphăng là những ví dụ rõ nhất về phương trình Điôphăng. Cả hai loại phương trình này đều đã được người Babylon biết đến. Đó là 1. Phương trình bậc nhất (tuyến tính), hai biến: ax + by = c. 2. Phương trình bậc hai (phi tuyến), ba biến: x2 + y2 = z2. Luận văn này có mục đích tìm hiểu và trình bày một số dạng đáng chú ý của phương trình Điôphăng bậc nhât (tuyến tính) và các bậc cao hơn (2, 3 và 4). Xét sự tồn tại nghiệm nguyên của các phương trình này, tính chất của các nghiệm nguyên của chúng và một số cách tìm nghiệm nguyên cho các loại phương trình được xét. Cụ thể trong luận văn sẽ đề cập tới các dạng phương trình Điôphăng sau đây: 1 a) Phương trình Điôphăng tuyến tính (bậc nhất): a1x1 + a2x2 + ... + anxn = b. b) Các dạng phương trình Điôphăng bậc hai của hai, ba hay bốn biến: x2 + y2 = n (hai biến), x2 + y2 = z2, x2 + axy + y2 = z2 (ba biến), x.y = z.w, x2 + y2 = z2 + w2, x2 + y2 + z2 = t2 (bốn biến). c) Phương trình Điôphăng bậc ba: x3 + y3 = z3 (ba biến). d) Phương trình Điôphăng bậc bốn (phương trình trùng phương): x4 ± x2y2 + y4 = z2, x4 ± y4 = z2 (ba biến), Luận văn được việt thành 3 chương: Chương 1 "Phương trình Điôphăng tuyến tính” trình bày khái niệm phương trình Điôphăng tuyến tính, nghiệm nguyên riêng và nghiệm nguyên tổng quát của phương trình, điều kiện cần và đủ để phương trình có nghiệm nguyên. Xét một số bài toán có liên quan về nghiệm nguyên không âm của phương trình Điôphăng bậc nhất và các ví dụ minh họa. Cuối chương nêu một số bài tập áp dụng. Chương 2 "Phương trình Điôphăng bậc hai" đề cập tới khái niệm bộ ba Pytago (x2 + y2 = z2), bộ bốn Pytago (x2 + y2 + z2 = t2) cùng các tính chất và một số dạng phương trình Điôphăng bậc hai của hai, ba hay bốn biến số (x2 + y2 = k(x - y), x 2 + y 2 = z 2, x2 + y2 + z2 + xy + yz + zx = 2w2). Nêu tính chất nghiệm của một số phương trình Điôphăng bậc hai khác (xy = zw, x2 + y2 = z2 + w2, x2 + xyw + y2 = z2, x2 + axy + by2 = z2). Cuối chương, nêu một số câu hỏi và bài tập áp dụng. Chương 3 "Một số phương trình Điôphăng bậc cao" đề cập tới tính không giải được của phương trình Điôphăng bậc cao hơn hai có dạng x3 + y3 = z3, x4 + y4 = z4, ... Đó là các trường hợp riêng của phương trình Fermat x n + yn = zn với x, y, z là các số nguyên. Tiếp đó giới thiệu định lý lớn Fermat (còn gọi là định lý cuối cùng của Fermat) nói rằng phương trình xn + yn = zn với n > 2 không có nghiệm nguyên khác không và giả thuyết Euler nói rằng phương trình xn + yn + zn = wn không có 2 Thang Long University Library nghiệm nguyên (khác không) nếu n là số nguyên lớn hơn hay bằng 4, cùng hai phản ví dụ. Xét một số dạng phương trình Điôphăng bậc cao x4  y4 = z2, x4 + y4 = 2z2, x4 + 6x2y2 + y4 = z2. Cuối chương nêu một số câu hỏi và bài tập áp 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 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ả Nguyễn Hải Hà 3 Chương 1 PHƯƠNG TRÌNH ĐIÔPHĂNG TUYẾN TÍNH Chương này đề cập tới phương trình Điôphăng tuyến tính, một số khái niệm có liên quan, điều kiện cần và đủ để phương trình có nghiệm nguyên, các ví dụ minh họa. Xét một số bài toán có liên quan về nghiệm nguyên không âm của phương trình Điôphăng tuyến tính. Cuối chương nêu một số bài tập áp dụng. Nội dung của chương được tham khảo từ các tài liệu [1], [2] và [3]. 1.1. ƯỚC CHUNG LỚN NHẤT Mục này nhắc lại một số khái niệm cần thiết trong lý thuyết số liên quan tới phương trình Điôphăng tuyến tính: ước số và phần dư, số nguyên tố và hợp số, ước chung lớn nhất của hai hay nhiều số nguyên ... 1.1.1. Ước số và phần dư Xét tập số nguyên ℤ = {0,  1,  2, ... }. Đị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 chía 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.1. Do 3 và - 5 là ước của 15 nên ta viết 3 | 15 và - 5 | 15. Nhưng - 2 và 7 không là ước của 15 nên ta viết - 2 ∤ 15 và 7 ∤ 15. Đị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. 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). Từ lý thuyết số, ta có kết quả sau 4 Thang Long University Library Đị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.2. a) Với a = 21, b = 5 ta có q = 4, r = 1, vì 21 = 54 + 1. b) Với a = 20, b = - 3 ta có q = - 6, r = 1, vì 20 = (- 3)(- 6) + 2. c) Với a = - 13, b = 2 ta có q = - 7, r = 1, vì - 13 = 2(- 7) + 1. d) Với a = - 11, b = - 7 ta có q = 2, r = 3, vì - 11 = (- 7)2 + 3. 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, ... Các hợp số: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, ... Đị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 ƯCLN (a, b) = d. Trong luận văn này ta sẽ sử dụng ƯCLN(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à 28. Ta thấy các ước của 8 là ±1, ±2, ±4, ±8; và các ước của 28 là ±1, ±2, ±4, ±7, ±14, 28. Từ đó, ước chung 5 của 8 và 28 là ±1, ±2, ±4. Vì thế, ước chung lớn nhất của 8 và 28 là 4. Ta viết gcd (8, 28) = 4. Có thể kiểm tra lại rằng ƯCLN(21, - 6) = 3; ƯCLN(- 10, 25) = 5, ... Định nghĩa 1.5. Nếu ước chung lớn nhất ƯCLN(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à ƯCLN(a, b) = d thì ƯCLN(a/d, b/d) = 1. Ví dụ 1.6. Hãy tìm ước chung lớn nhất của 15 và 40. Bằng cách phân tích ra thừa số nguyên tố ta có 15 = 3×5 và 40 = 23×5. Từ đó, ta tìm được ước chung lớn nhất của 15 và 40 bằng 5, tức là ƯCLN(15, 40) = 5. Ta thấy ƯCLN(15/5, 40/5) = ƯCLN(3, 8) = 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 đó ƯCLN(a + cb, b) = ƯCLN(a, b). Ví dụ 1.7. Xét ba số: a = 130, b = 52, c = 12. Theo Định lý 1.4, ta sẽ có ƯCLN(130 + 12×52, 52) = ƯCLN(130, 52) hay ƯCLN(754, 52) = ƯCLN (130, 52). Để kiểm tra đẳng thức này, ta cần tính ƯCLN(754, 52) vàƯCLN (130, 52). Ta thấy 52 = 22×13, 130 = 2×5×13 và 754 = 2×13×29. Từ đó suy ra ƯCLN(754, 52) = ƯCLN(130, 52) = 26. 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 =ƯCLN (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 = 57 và b = 247. Ta thấy 57 = 3×19 và 247 = 13×19. Từ đó ƯCLN(57, 247) = 19. Chọn x = 9, y = - 2, ta có 57×9 - 247×2 = 513 - 494 = 19 = ƯCLN(57, 171). 6 Thang Long University Library Đị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 = 18, b = 33, và c = 3. Ta có 18 = 3×6 và 33 = 3×11. Vì thế, 18 và 33 chia hết cho 3. Giả sử m = 8, n = - 2. Khi đó 8×18 - 2×33 = 144 - 66 = 78. Rõ ràng 3 là ước của 78, vì 78 = 3×26. Đị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 bằng tập các bội nguyên của ƯCLN(a, b). Ví dụ 1.10. Giả sử a = 68, b = 153. Ta thấy 52 = 22×17 và 117 = 32×17. Do đó ƯCLN(68, 153) = 17. Với bất kỳ x, y ∈ ℤ tìm được số nguyên k nghiệm đúng phương trình 68x + 153y = 17k. Tìm x và y để cho k = 2, tức là x, y thỏa mãn 68x + 153y = 17×2 = 34. Chia cả hai vế cho 17, 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 n  2 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 ƯCLN (a1, a2, ... , an). Ví dụ 1.11. Có thể thấy ƯCLN(3, 9, 12) = 3 và ƯCLN(5, 25, 45) = 5. 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ì ƯCLN(a1, a2, ... , an-1, an) =ƯCLN (a1, a2, ... , ƯCLN(an-1, an)). 7 Ví dụ 1.12. Tìm ước chung lớn nhất của 112, 378, 693 và 2016. 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 112 = 24×7, 378 = 233×7, 693 = 32×7×11, 2016 = 25×32×7. ƯCLN(112, 378, 693, 2016) =ƯCLN (112, 378. (693, 2016)) = ƯCLN(112, 378, 63) = ƯCLN(112, (378, 63)) =ƯCLN (112, 63) = 7. Định lý 1.10. Nếu c, d  ℤ và c = dq + r, với q, r  ℤ thì ƯCLN(c, d) = ƯCLN(r, d). Ví dụ 1.13. Xét đẳng thức 75 = 12×6 + 3. Nếu phân tích đẳng thức này theo Định lý 1.10, ta thấy c = 75, d = 12, q = 6 và r = 3. Ta có 75 = 52×3, 12 = 223. Áp dụng định lý ta được ƯCLN(75, 12) = ƯCLN(3, 12) = 3. 1.2. PHƯƠNG TRÌNH TUYẾN TÍNH VỚI CÁC HỆ SỐ NGUYÊN Phương trình có dạng a1x1 + a2x2 + ... + anxn = c, (1.1) trong đó a1, a2, ... , an, c là các số nguyên cho trước, được gọi là phương trình Điôphăng tuyến tính. Ta giả thiết n  1 và tất cả các hệ số a1, a2, ... , an đều khác 0. Ta bắt đầu với trường hợp n = 2. Kết quả cơ bản liên quan đến phương trình Điôphăng tuyến tính được nêu trong định lý sau. Định lý 1.11. Giả sử a, b, c là các số nguyên, a và b khác 0. Xét phương trình Điôphăng tuyến tính hai biến 8 Thang Long University Library ax + by = c, (1.2) 1. Phương trình (1.2) có nghiệm nguyên khi và chỉ khi d = ƯCLN(a, b) (ước chung lớn nhất của a và b) là ước số của c. 2. Nếu (x, y) = (x0, y0) là một nghiệm riêng của (1. 2) thì mọi nghiệm nguyên tổng quát của phương trình (1.2) có dạng x = x0 + b a t, y = y0 - t, d d (1.3) trong đó t là số nguyên. 3. Nếu c =ƯCLN (a, b) và |a| hoặc |b| khác 1 thì có thể tìm được một nghiệm riêng (x, y) = (x0, y0) của (1.3) sao cho |x0| < |b| và |y0| < |a|. Chứng minh. 1. Nếu d không là ước số của c thì rõ ràng phương trình không thể có nghiệm. Nếu d là ước số của c thì chia hai vế của (1.2) cho d, ta chỉ cần chứng minh rằng d là tổ hợp tuyến tính với các hệ số nguyên của a và b. Muốn vậy ta dùng thuật toán Ơclit. Rõ ràng là nếu b | a thì ƯCLN(a, b) = b. Trái lại, giả sử a = bq + r với các số nguyên q, r với 0 < r < b. Dễ kiểm tra lại rằng mọi ước chung của a và b cũng là ước chung của b và r và ngược lại. Tổng quát ta có ƯCLN (a, b) = ƯCLN(b, r). Nhận xét này đưa tới cách tính trực tiếp ước chung lớn nhất của hai số nguyên. Một cách hệ thống như sau: Ta đặt a = r1, b = r0 (giả thiết a > b > 0): r1 = r0q0 + r1, 0  r1 < r0, r0 = r1q1 + r2, 0  r2 < r1, r1 = r2q2 + r3, 0  r3 < r2, r2 = r3q3 + r4, 0  r4 < r3,   Phép chia này cuối cùng phải kết thúc, bởi vì phần dư ngày càng bé dần: 9 r1 > r0 > r1 > r2 > ...  0, và luôn không âm. Nói một cách khác, đến một lúc nào dó rn1 sẽ chia hết cho rn sau đó (và để lại phần dư rn+1 = 0). Ta nhận được   0  rn < rn1, rn2 = rn1qn1 + rn, rn1 = rnqn + 0 (rn+1 = 0). Từ đó suy ra rn =ƯCLN (rn1, rn) =ƯCLN (rn2, rn1) = ... =ƯCLN (rr1, r0) =ƯCLN (a, b). Có thể thực hiện theo thứ tự ngược trở lại các phép toán trên đây để biểu diễn ƯCLN(a, b) dưới dạng tổ hợp tuyến tính của a và b. Từ các công thức trên suy ngược trở lại ta có: r1 = r-1 - q0r0, r2 = r0 - q1r1. Tổng quát: rk = rk-2 - qk-1rk-1 với k = 1, 2, ... , n. Xác định các số nguyên xk và yk theo hệ thức truy hồi: x1 = 1, x0 = 0, xk = xk2  qk1xk1, k = 1, 2, ... , n. y1 = 0, y0 = 1, yk = yk2  qk1yk1, k = 1, 2, ... , n. Ta chứng minh bằng qui nạp rằng rk = axk + byk với k = 1, 2, ... , n. Thật vậy, r1  a = ax1 + by1 (theo định nghĩa của r1 và do x1 = 1, y1 = 0), r0  b = ax0 + by0 (theo định nghĩa của r0 và do x = 0, y = 1), ... rk = rk2  qk1rk-1 = (axk2 + byk2)  qk1(axk1 + byk1) = a(xk2  qk1xk1) + b(yk2  qk1yk1) = axk + byk với mọi k = 1, 2, ... , n. Nói riêng, ở bước k = n ta có ƯCLN(a, b) = rn = axn + byn. 0 = axn+1 + byn+1 = a(xn1  qnxn) + b(yn1  qnyn) = rn-1 - qnrn = 0. xn+1 = xn1  qnxn, yn+1 = yn1  qnyn, a|xn+1| = b|yn+1|. 10 Thang Long University Library Có thể kiểm tra thấy rằng {xk} và {yk} luân phiên đổi dấu, |xn+1| = b / ƯCLN(a, b) và |yn+1| = a /ƯCLN (a, b). Từ đó |xn| < b và |yn| < a, trừ khi n = 0 và q0 = 1, tức là trừ khi a = b = 1. 2. Ta có b  a    ax + by = a  x 0  t  + b  y 0  t  = ax0 + by0 = c với mọi t  ℤ. d  d    3. Kết luận đã được chứng minh ở điểm 1.  Kết quả chính liên quan tới phương trình Điôphăng tuyến tính tổng quát được cho trong định lý sau. Định lý 1.12. Phương trình (1.1) có nghiệm nguyên khi và chỉ khi ƯCLN(a1, a2, ... , an) | c. Nếu phương trình có nghiệm thì ta có thể chọn được (n - 1) nghiệm sao cho một nghiệm bất kỳ của phương trình là tổ hợp tuyến tính của (n - 1) nghiệm này. Chứng minh. Giả sử d =ƯCLN (a1, a2, ... , an). Nếu c không chia hết cho d thì (1.1) không có nghiệm, bởi vì với các số nguyên x1, x2, ... , xn bất kỳ thì vế trái (1.1) chia hết cho d, trong khi đó vế phải lại không chia hết cho d. Thực ra, ta cần chứng minh rằng ƯCLN (x1, x2, ... , xn) là một tổ hợp tuyến tính của x1, x2, ... , xn. Với n = 2. điều này được suy ra từ Định lý 1.11. Với n > 2 thì do ƯCLN(x1, x2, ... , xn) = ƯCLN(ƯCLN(x1, x2, ... , xn1), xn) Nên ƯCLN (x1, x2, ... , xn) là tổ hợp tuyến tính của xn và ƯCLN (x1, x2, ... , xn1). Bằng qui nạp cho thấy ƯCLN(x1, x2, ... , xn) là tổ hợp tuyến tính của x1, x2, ... , xn.  Ví dụ 1.14. Tìm nghiệm nguyên của phương trình 3x + 4y + 5z = 6. 11 Giải. Với đồng dư modulo 5 ta có 3x + 4y  1 (mod 5). Do đó 3x + 4y = 1 + 5s, s  ℤ. Một nghiệm của phương trình này là x0 = - 1 + 3s, y0 = 1 - s. Áp dụng (1.3) ta được x = - 1 + 3s + 4t, y = 1 - s - 3t, t  ℤ và thay thế ngược trở lại vào phương trình ban đầu cho z = 1 - s. Do đó các nghiệm của phương trình là (x, y, z) = (- 1 + 3s + 4t, 1 - s - 3t, 1 - s), s, t  ℤ.  1.3. BÀI TOÁN LIÊN QUAN Định nghĩa 1.8. Cho n số nguyên dương a1, a2, ... , an với ƯCLN (a1, a2, ... , an) = 1, ta định nghĩa g(a1, a2, ... , an) là số nguyên dương lớn nhất N sao cho phương trình a1x1 + a2x2 + ... + anxn = N không có nghiệm nguyên không âm. Bài toán xác định g(a1, a2, ... , an) được biết với tên gọi bài toán số tiền Frobenius (Frobenius coin problem). Frobenius là người nêu ra bài toán xác định số tiền lớn nhất không thể trả bằng các đồng tiền có mệnh giá a1, a2, ... , an. Ví dụ 1.15. (Sylvester, 1884) Cho a, b là hai số nguyên dương với ƯCLN (a, b) = 1. Khi đó g(a, b) = ab - a - b. Giải. Giả sử N > ab - a - b. Từ (1.3) suy ra rằng các nghiệm của phương trình ax + by = N có dạng (x, y) = (x0 + bt, y0  at), t  ℤ. Giả sử t là số nguyên sao cho 0  y0  at  a  1. Khi đó (x0 + bt)a = N  (y0  at)b > ab - a - b - (a - 1)b = - a, kéo theo x0 + bt > - 1, nghĩa là x0 + bt  0. Suy ra rằng trong trường hợp này phương trình ax + by = N có nghiệm nguyên không âm. Do vậy g(a, b)  ab  a  b. 12 Thang Long University Library Bây giờ ta chỉ còn phải chỉ ra rằng phương trình ax + by = ab  a  b không có nghiệm nguyên không âm. Thật vậy, nếu trái lại thi ab = a(x + 1) + b(y + 1). Do ƯCLN (a, b) = 1 nên ta thấy rằng a | (y + 1) và b | (x + 1), điều này kéo theo (y + 1)  a và (x + 1)  b. Vì thế ab = a(x + 1) + b(y + 1)  2ab. Mâu thuẫn này cho thấy rằng g(a, b)  ab  a  b. Vì thế g(a, b) = ab  a  b.  Nhận xét 1.1. Trường hợp n = 3 lần đầu tiên đã được Selmer và Beyer,giải quyết trọn vẹn, bằng cách sử dụng thuật toán phân số liên tục. Kết quả của hai ông đã được đơn giản hóa bởi Ro dseth và sau đó bởi Greenberg. Nhận xét 1.2. Chưa biết một công thức tổng quát nào cho n  4. Tuy nhiên, có một số cận trên đã được chứng minh. Năm 1942, Brauer đã chứng minh rằng g(a1, a2, ... , an)  n  d i1   1 ,  di   a i  i 1 trong đó di = gcd(a1, ... , ai). Erdo và Graham (1972) đã chỉ ra rằng a  g(a1, a2, ... , an)  2an1  n   an n và t2 2t 2  5t  (n, t)  , n 1 n trong đó (n, t) = max 0 a1  a n  t Bây giờ giả sử phương trình 13 g(a1, a2, ... , an). a1x1 + a2x2 + ... + amxm = n, trong đó a1, a2, ... , am > 0, có nghiệm nguyên không âm và giả sử An là số nghiệm nguyên không âm (x1, x2, ... , xm) của phương trình. Ta có Định lý 1.13. (i) Hàm sinh của dãy (An)n1 là f(x) = 1 , |x| < 1, (1  x a1 )(1  x a m ) nghĩa là An bằng hệ số của só hạng xn trong khai triển hàm f thành chuỗi lũy thừa. (ii) Đẳng thức sau là đúng An = 1 (n) f (0). n! (1.4) Chứng minh. (i) Dùng chuỗi lũy thừa, ta có 1 = 1 + x a k + x 2a k + ... , k = 1, 2, ... , m. ak 1 x Do đó f(x) = (1 + x a1 + x 2a1 + ... ) ... (1 + x a m + x 2a m + ... ) = 1 + A1x + ... + Anxn + ... (ii) Lấy đạo hàm cấp n của f tại x = 0, ta nhận được công thức (1.4).  Ví dụ 1.16. Tìm số cặp số nguyên không âm (x, y) sao cho x + 2y = n. Giải. Theo Định lý 1.13, số cần tìm bằng An = 1 (n) f (0), n! trong đó f(t) = 1 . (1  t )(1  t 2 ) Ta có 14 Thang Long University Library f(t) = 1 1 1 1 1 1 .  . + . , 2 ( t  1) 2 4 ( t  1) 4 ( t  1) do đó f(n)(t) = 1 (1) n (n  1)! 1 (1) n n! 1 (1) n n! .  . + . . 2 ( t  1) n 2 4 ( t  1) n 1 4 ( t  1) n 1 Như vậy (n  1)! n! ( 1) n n! f (0) = + + 4 2 4 (n) và 2n  3  (1) n 1 (n) An = f (0) = . 4 n!  1.4. BÀI TẬP ÁP DỤNG 1. Chứng minh các tính chất sau đây và cho ví dụ minh họa: a) Nếu a, b  ℤ và d = ƯCLN(a, b)  1 thì ƯCLN(a/d, b/d) = 1. b) Nếu a, b, c  ℤ sao cho a | bc và a, b nguyên tố cùng nhau thì a | c. c) Cho a, b, c  ℤ. Khi đó ƯCLN(a + cb, b) =ƯCLN (a, b). d) Giả sử a, b, c, m, n  ℤ. Nếu a | b và a | c thì a | (mb + nc). e) Nếu c, d  ℤ và c = dq + r, với q, r  ℤ thì ƯCLN (c, d) =ƯCLN (r, d). 2. Giải phương trình sau: 6x + 10y  15z = 1. Bài giải. Lấy modulo 3 ta thấy y  1 (mod 3). Do đó y = 1 + 3s, s ℤ. Phương trình trở thành 6x  15z = - 9 - 30s, hay tương đương 2x - 5z = - 3 - 10s. Chuyển qua modulo 2 ta được z  1 (mod 2), tức là z = 1 + 2t, t  ℤ, và x = 1 - 5s + 5t. Vậy nghiệm của phương trình đã cho là (x, y, z) = (1 - 5s + 5t, 1 + 3s, 1 + 2t). 15  3. Cho ba số nguyên dương a, b, c nguyên tố cùng nhau. Chứng minh rằng 2abc - ab - bc - ca là số dương lớn nhất không thể biểu diễn được dưới dạng xbc + yca + zab, trong đó x, y, z là các số nguyên và không âm. 4. Tìm số các bộ ba (x, y, z) nguyên, không âm sao cho x + y + 2z = n. Bài giải. Từ định lý 1.13 ta nhận thấy rằng số cần tìm là An = 1 (n) f (0), n! trong đó hàm sinh f được cho bởi f(t) = 1 . (1  t )(1  t )(1  t 2 ) Ta có f(t) = 1 1 1 1 1 1 1 1 . . . . +  + , 2 ( t  1) 3 4 ( t  1) 2 8 t  1 8 t  1 do đó 1 (1) n (n  2)! 1 (1) n (n  1)! f (t) =  . + . 4 ( t  1) n 3 4 ( t  1) n 2 (n) 1 (1) n n! 1 (1) n n!  . + . . 8 ( t  1) n 1 8 ( t  1) n 1 Như vậy (n  2)! (n  1)! n! ( 1) n n! f (0) = + +  8 8 4 4 (n) và 2(n  1)(n  3)  1  (1) n 1 (n) An = f (0) = . 8 n!  5. Tìm số nguyên dương n sao cho phương trình x + 2y + z = n 16 Thang Long University Library có đúng 100 nghiệm nguyên không âm (x, y, z). Bài giải. Dùng kết quả của bài tập 4, ta thấy rằng số bộ ba các số nguyên không âm (x, y, z) thỏa mãn phương trình x + 2y + z = n là 2(n  1)(n  3)  1  (1) n 1 (n) An = f (0) = . 8 n! Nếu n = 2k thì An = (k+1)2. Suy ra k = 9 và n = 18. Nếu n = 2k + 1 thì An = (k + 1)(k + 2) và để ý rằng phương trình (k + 1)(k + 2)  = 100 không có nghiệm nguyên. 6. Cho a, b, c, d là các số nguyên sao cho với bất kỳ hai số nguyên m và n luôn tồn tại hai số nguyên x và y thỏa mãn ax + by = m và cx + dy = n. Chứng minh rằng ad - bc =  1. 7. Cho n là số nguyên lớn hơn 3 và giả sử X là tập gồm 3n2 phần tử thuộc tập {1, 2, ... , n3}. Chứng minh rằng tồn tại 9 số khác nhau a1, a2, ... , a9 thuộc X sao cho hệ phương trình tuyến tính thuần nhất a1x + a2y + a3z = 0, a4x + a5y + a6z = 0, a7x + a8y + a9z = 0, có nghiệm nguyên khác 0. Bài giải. Đánh số các phần tử thuộc X theo thứ tự tăng dẫn x1 < x2 < ... < x3n2 và đặt X1 = {x1, ... , xn2}, X2 = {xn2+1, ... , x2n2}, X3 = {x2n2+1, ... , x3n2}. Ta xác định hàm f : X1X2X3  X  X như sau: f(a, b, c) = (b - a, c - b). Miền xác định của f gồm n2n2n2 = n6 phần tử. Mặt khác, miền giá trị của f là một tập con của X  X gồm các cặp có tổng không quá n3. Tập này có số phần tử là 17 n 3 (n 3  1 n 6 . k = < . 2 2 k 1 n 3 1 Theo nguyên lý chuồng bồ câu, ba bộ 3 (ai, bi, ci) (i = 1, 2, 3) nào đó tương ứng với cùng một cặp trong X  X, trong đó x = b1 - c1, y = c1 - a1, z = a1 - b1 là một nghiệm nguyên khác không. Để ý rằng ai không thể bằng bj do X1 và X2 là hai tập rời nhau, v.v ... và nếu a1 = a2 thì hai bộ 3 (a1, b1, c1) và (a2, b2, c2) trung nhau, ta gặp mâu thuẫn. Vậy 9 số trong ba bộ 3 nói trên là khác nhau.  8. Cho hệ phương trình tuyến tính thuần nhất a11x1 + a12x2 + ... + a1qxq = 0, a21x1 + a22x2 + ... + a2qxq = 0,     ap1x1 + ap2x2 + ... + apqxq = 0, trong đó q = 2p và aij  {- 1, 0, 1}. Chứng minh rằng tồn tại nghiệm {x1, x2, ... , xq} của hệ với các tính chất sau: (a) xj nguyên với mọi j = 1, 2, ... , q; (b) tồn tại j sao cho xj  0; 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 và ước chung lớn nhất của các số nguyên, thuật toán Euclid, bài toán tìm nghiệm nguyên của phương trình Điôphăng tuyến tính, điều kiện tồn tại nghiệm nguyên và xét bài toán liên quan tới phương trình Điôphăng tuyến tính. Cuối chương nêu một số bài tập áp dụng. 18 Thang Long University Library Chương 2 PHƯƠNG TRÌNH ĐIÔPHĂNG BẬC HAI Chương này đề cập tới bộ ba Pytago, bộ bốn Pytago cùng với các tính chất của chúng và một số dạng phương trình Điôphăng bậc hai của hai, ba hay bốn biến số. Trình bày tính chất nghiệm của một số phương trình Điôphăng bậc hai khác và các ví dụ, Tiếp theo, xét nghiệm nguyên không âm của một số bài toán có liên quan. Cuối chương nêu một số câu hỏi và bài tập áp dụng, liên quan tới phương trình Điôphăng bậc hai. Nội dung của chương được tham khảo chủ yếu từ tài liệu [4] và [5]. 2.1. BỘ BA PYTAGO VÀ CÁC BÀI TOÁN LIÊN QUAN Một trong những phương trình Điôphăng nổi tiếng nhất là phương trình Pytago x2 + y2 = z2, (2.1) Phương trình này liên quan tới các tam giác vuông có độ dài ba cạnh là các số nguyên, đã được Pytago nghiên cứu chi tiết và đã được biết đến ngay từ thời cổ xưa Babylon. Trước hết để ý là nếu bộ ba số nguyên (x0, y0, z0) thỏa mãn phương trình (2.1) thì mọi bộ ba số có dạng (kx0, ky0, kz0), k  ℤ cũng thỏa mãn (2.1). Đó là ly do cho phép ta chỉ cần tìm nghiệm (x, y, z) của (2.1) với gcd(x, y, z) = 1. Điều này tương đương với x, y, z từng đôi nguyên tố cùng nhau. Một nghiệm (x0, y0, z0) của (2.1) với x0, y0, z0 từng đôi nguyên tố cùng nhau gọi là một nghiệm nguyên thủy (primitive solution). Rõ ràng là trong một nghiệm nguyên thủy có đúng một số là chẵn x0 hoặc y0. 19 Định lý 2.1. Một nghiệm nguyên dương nguyên thủy bất kỳ của phương trình (2.1) (x, y, z) với y chẵn có dạng x = m2 - n2, y = 2mn, z = m2 + n2, (2.2) trong đó m, n là hai số nguyên dương, nguyên tố cùng nhau với m > n và m + n lẻ. Chứng minh. Các số nguyên x và y không thể cùng là số lẻ, bởi vì z2 = x2 + y2  2 (mod 4), ta gặp mâu thuẫn. Do đó có đúng một trong x và y là số chẵn. Đồng nhất thức (m2 - n2)2 + (2mn)2 = (m2 + n2)2 cho thấy rằng bộ ba số cho ở (2.2) thực sự là một nghiệm của phương trình (2.1) và y là số chẵn. Do x phải là số lẻ nên không mất tổng quát ta có thể giả thiết rằng m là số lẻ và n là số chẵn. Hơn nữa, nếu ƯCLN (m2 - n2, 2mn, m2 + n2) = d  2 thì d là ước của 2m2 = (m2 + n2) + (m2  n2) và d là ước của 2n2 = (m2 + n2)  (m2  n2). Do m và n nguyên tố cùng nhau nên ta suy ra d = 2. Vì thế m2 + n2 là số chẵn, trái với m lẻ và n chẵn. Từ đó suy ra d = 1 và vì thế nghiệm (2.2) là nguyên thủy. Ngược lại, giả sử (x, y, z) là một nghiệm nguyên thủy của (2.1) với y = 2a. Khi đó x và z là hai số lẻ và do đó các số nguyên z + x và z - x là các số chẵn. Giả sử z + x = 2b, z - x = 2c. Ta có thể giả thiết rằng b và c nguyên tố cùng nhau, bởi vì z và x sẽ có ước chung khác 1. Một mặt, 4a2 = y2 = z2 - x2 = (z + x)(z - c) = 4bc, tức là a2 = bc. Do b và c nguyên tố cùng nhau nên suy ra rằng b = m2 và c = n2 với m và n là hai số nguyên dương nào đó. Ta nhận thấy rằng m + n là số lẻ và x = b  c = m2  n2, y = 2mn, z = b + c = m2 + n2.  20 Thang Long University Library
- Xem thêm -

Tài liệu liên quan