Luận văn Thạc sĩ Toán học: Một số phương pháp giải các đề thi Olympic về phương trình Diophant

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:82

Thêm vào BST

Báo xấu

29
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong các kì thi học sinh giỏi toán các cấp, Olympic Toán sinh viên, các bài toán liên quan tới phương trình Diophant (dạng tuyến tính và phi tuyến) thường xuyên được đề cập. Những dạng toán này thường được xem là thuộc loại khó vì phần kiến thức về phương trình Diophant tổng quát không nằm trong chương trình chính thức của giáo trình Số học và Đại số bậc trung học phổ thông.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số phương pháp giải các đề thi Olympic về phương trình Diophant

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- ĐẶNG THỊ THU HÀ MỘT SỐ PHƢƠNG PHÁP GIẢI CÁC ĐỀ THI OLYMPIC VỀ PHƢƠNG TRÌNH DIOPHANT LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- ĐẶNG THỊ THU HÀ MỘT SỐ PHƢƠNG PHÁP GIẢI CÁC ĐỀ THI OLYMPIC VỀ PHƢƠNG TRÌNH DIOPHANT Chuyên ngành: Phƣơng pháp Toán sơ cấp Mã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. Nguyễn Văn Mậu THÁI NGUYÊN - 2019
i Lời cảm ơn Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên. Tác giả xin bày tỏ lòng biết ơn sâu sắc đối với GS.TSKH Nguyễn Văn Mậu (Trường ĐH Khoa học Tự nhiên, ĐHQGHN), thầy đã trực tiếp hướng dẫn tận tình và động viên tác giả trong suốt thời gian nghiên cứu vừa qua. Xin chân thành cảm ơn tới các quý thầy, cô giáo đã trực tiếp giảng dạy lớp cao học Toán K11, các bạn học viên, và các bạn đồng nghiệp đã tạo điều kiện thuận lợi, động viên giúp đỡ tác giả trong quá trình học tập và nghiên cứu tại trường. Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân luôn khuyến khích động viên tác giả trong suốt quá trình học cao học và viết luận văn này. Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp của các thầy cô và các bạn đọc để luận văn được hoàn thiện hơn. Xin chân thành cảm ơn! Thái Nguyên, tháng 11 năm 2019 Tác giả Đặng Thị Thu Hà
ii Mục lục MỞ ĐẦU 1 Chương 1. Phương trình Diophant và hệ Diophant cơ bản 2 1.1 Phương trình Diophant tuyến tính . . . . . . . . . . . . . . . . . . 2 1.1.1 Nghiệm riêng . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Nghiệm nguyên dương . . . . . . . . . . . . . . . . . . . . . 9 1.2 Nghiệm nguyên dương của hệ phương trình Diophant tuyến tính cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Chương 2. Các phương pháp giải phương trình Diophant 19 2.1 Phương pháp phân tích thành nhân tử . . . . . . . . . . . . . . . . 19 2.2 Phương pháp đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Phương pháp đánh giá . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4 Phương pháp tham số hóa . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Phương pháp quy nạp toán học . . . . . . . . . . . . . . . . . . . 30 2.6 Phương pháp xuống thang . . . . . . . . . . . . . . . . . . . . . . 33 2.7 Một số phương pháp khác . . . . . . . . . . . . . . . . . . . . . . . 40 Chương 3. Các dạng toán liên quan đến phương trình và hệ phương trình Diophant 47 3.1 Một số dạng toán về đa thức nguyên . . . . . . . . . . . . . . . . . 47 3.2 Một số dạng toán lượng giác liên quan . . . . . . . . . . . . . . . . 50 3.3 Một số dạng toán thi Olympic liên quan . . . . . . . . . . . . . . . 66 KẾT LUẬN 77 TÀI LIỆU THAM KHẢO 78
1 Mở đầu Trong các kì thi học sinh giỏi toán các cấp, Olympic Toán sinh viên, các bài toán liên quan tới phương trình Diophant (dạng tuyến tính và phi tuyến) thường xuyên được đề cập. Những dạng toán này thường được xem là thuộc loại khó vì phần kiến thức về phương trình Diophant tổng quát không nằm trong chương trình chính thức của giáo trình Số học và Đại số bậc trung học phổ thông. Để đáp ứng nhu cầu bồi dưỡng giáo viên và bồi dưỡng học sinh giỏi về chuyên đề phương trình Diophant, tôi chọn đề tài luận văn "Một số phương pháp giải các đề thi Olympic về phương trình Diophant". Tiếp theo, khảo sát một số lớp hệ phương trình Diophant liên quan. Cấu trúc luận văn gồm 3 chương: Chương 1. Các kiến thức bổ túc về số học và phương trình Diophant cơ bản. Chương 2. Các phương pháp giải phương trình Diophant. Chương 3. Các dạng toán liên quan đến hệ phương trình Diophant. Tiếp theo, cuối các chương đều trình bày các bài tập áp dụng và giải các đề thi HSG quốc gia và Olympic liên quan.
2 Chương 1. Phương trình Diophant và hệ Diophant cơ bản 1.1 Phương trình Diophant tuyến tính Ta nhắc lại thuật toán Euclid và liên phân số đã được trình bày tương đối chi tiết trong chương trình toán bậc THCS. Định nghĩa 1.1. Số nguyên c được gọi là một ước số chung của hai số nguyên a và b (không đồng thời bằng không) nếu c chia hết a và c chia hết b (hay a và b đều chia hết cho c). Định nghĩa 1.2 (xem [3,5, 7]). Một ước số chung d của hai số nguyên a và b (không đồng thời bằng không) được gọi là ước số chung lớn nhất của a và b nếu mọi ước số chung c của a và b đều là ước của d. Nhận xét 1.1. Nếu d là ước số chung lớn nhất của a và b thì −d cũng là ước số chung lớn nhất của a và b. Vì vậy, ta quy ước rằng ước số chung lớn nhất của a và b là số nguyên dương. Ước số chung lớn nhất của hai số a và b được ký hiệu là (a, b) hay gcd(a,b) (greatest common divisor). Như vậy d = (a, b) hay d = gcd(a, b). Ví dụ 1.1. (25,30) = 5, (25,-72) = 1. Định nghĩa 1.3 (xem [3,5,7]). Một số nguyên c được gọi là một ước số chung của bộ n số nguyên a1 , a2 , a3 , . . . , an (không đồng thời bằng không) nếu c là ước của mỗi số đó. Định nghĩa 1.4 (xem [5,7]). Một ước số chung d của bộ n số nguyên a1 , a2 , a3 , . . . , an (không đồng thời bằng không) được gọi là ước số chung lớn nhất của a1 , a2 , a3 , . . . , an nếu mọi ước số chung c của a1 , a2 , a3 , . . . , an đều là ước của d. Tương tự, ta cũng quy ước rằng ước số chung lớn nhất của n số nguyên a1 , a2 , a3 , . . . , an là số nguyên dương.
3 Ước số chung lớn nhất của a1 , a2 , a3 , . . . , an ký hiệu là (a1 , a2 , a3 , . . . , an ) hay gcd(a1 , a2 , a3 , . . . , an ). Như vậy d = (a1 , a2 , a3 , . . . , an ) hay d = gcd(a1 , a2 , a3 , . . . , an ). Định lý 1.1 (Ước số chung lớn nhất của nhiều số). Cho các số nguyên a1 , a2 , a3 , . . . , an không đồng thời bằng không. Khi đó tồn tại ước số chung lớn nhất của a1 , a2 , a3 , . . . , an . Tính chất 1.1. Cho a, b, q, r là các số nguyên (a2 + b2 6= 0). Nếu a = bq + r và 0 ≤ r < |b| thì (a, b) = (b, r). 1.1.1 Nghiệm riêng Trong mục này, ta trình bày hai thuật toán tìm nghiệm riêng của phương trình Diophant, đó là thuật toán giản phân và thuật toán Euclid. Xét phương trình Diophant tuyến tính Ax + By = C. (1.1) Để tìm nghiệm riêng dựa vào giản phân, ta tiến hành thực hiện theo các bước như sau: - Bước 1. Tìm d = (A, B) để đưa phương trình (1.1) về phương trình (1.2) với (a, b) = 1. phương trình Diophant tuyến tính ax + by = c. (1.2) a - Bước 2. Viết = [a0 ; a1 , a2 , . . . , an ]. |b| pn−1 - Bước 3. Tính giản phân Cn−1 = [a0 ; a1 , . . . , an−1 ] = . Suy ra pn−1 và qn−1 qn−1 . - Bước 4. Suy ra một nghiệm riêng (x0 , y0 ) của phương trình (1.2). x = (−1)n−1 .c.q 0 n−1 Nếu b > 0 thì y = (−1)n .c.p .  0 n−1 x = (−1)n−1 .c.q 0 n−1 Nếu b < 0 thì y = (−1)n−1 .c.p . 0 n−1 Bài toán 1.1. Giải phương trình Diophant tuyến tính 342x − 123y = 15. (1.3)
4 Lời giải. Phương trình đã cho tương đương với phương trình 114x − 41y = 5. (1.4) 114 Ta có = [2; 1, 3, 1, 1, 4], với n = 5. 41  C4 = p4 = [2; 1, 3, 1, 1] = 25   p = 25 4 q4 9 nên (p4 , q4 ) = 1  q = 9. 4 Do b = −41 < 0 nên một nghiệm riêng của (1.4) là  x = (−1)5−1 .5.9 = 45 0 y = (−1)5−1 .5.25 = 125. 0 Vậy nghiệm của phương trình (1.4), tức phương trình (1.14) là  x = 45 + 41t , t ∈ Z. y = 125 + 114t Để tìm nghiệm riêng dựa vào thuật toán Euclid, ta tiến hành thực hiện theo các bước như sau: - Bước 1. Xác định d = (|A| , |B|) theo thuật toán Euclid mở rộng. - Bước 2. Biểu thị d như một tổ hợp tuyến tính của A và B , chẳng hạn d = nA + mB (n, m ∈ Z) . C - Bước 3. Nhân hai vế đẳng thức trên với ta thu được d Cn Cm A +B = C. d d - Bước 4. Suy ra một nghiệm riêng (x0 , y0 ) của phương trình (1.1) là  Cn   x0 = d     y0 = Cm .    d Bài toán 1.2. Giải phương trình Diophant tuyến tính 342x − 123y = 15. (1.5)
5 Lời giải. Vì (342, −123) = 3 |15 nên phương trình đã cho có nghiệm. Ta có 342 = 123.2 + 96, 123 = 96.1 + 27, 96 = 27.3 + 15, 27 = 15.1 + 12, 15 = 12.1 + 3, 12 = 3.4 + 0. Suy ra 3 = 15 − 12.1 = 15 − (27 − 15.1).1 = 15.2 − 27.1 = (96 − 27.3).2 − 27.1 = 96.2 − 27.7 = 96.2 − (123 − 96.1).7 = 96.9 − 123.7 = (342 − 123.2).9 − 123.7 = = 342.9 − 123.25. Suy ra 342.45 − 123.125 = 15. Từ đó, phương trình (1.14) có một nghiệm riêng là (x0 ; y0 ) = (45; 125). Suy ra nghiệm tổng quát của phương trình (1.14) là  123   x = 45 + t 3    ,t∈Z 342    y = 125 +  t 3 hay  x = 45 + 41t , t ∈ Z. y = 125 + 114t Định lý 1.2. Xét phương trình Diophant tuyến tính a1 x1 + a2 x2 + . . . + an xn = c. (1.6) 1. Phương trình (1.6) có nghiệm khi và chỉ khi d = (a1 , a2 , . . . , an ) |c . 2. Nếu phương trình (1.6) có nghiệm thì nó sẽ có vô số nghiệm.
6 Chứng minh. 1) ⇒). Giả sử (x1 , x2 , . . . , xn ) là một nghiệm của phương trình (1.6), tức là n X ai xi = c. i=1
Pn Ta có d = (a1 , a2 , . . . , an ), suy ra d
ai xi , suy ra d |c .
i=1 ⇐) Ta chứng minh khẳng định bằng phương pháp quy nạp theo n. Với n = 2, khẳng định là đúng. Giả sử khẳng định đúng với n = k (k ≥ 2). Với n = k + 1, xét d = (a1 , a2 , . . . , ak+1 ) |c , đặt h = (a1 , a2 , . . . , ak ). Khi đó, ta có d = (h, ak+1 ) |c Suy ra, tồn tại t, xk+1 ∈ Z để ht + ak+1 xk+1 = c. Vì h |ht nên theo giả thiết quy nạp sẽ tồn tại x1 , x2 , . . . , xk ∈ Z để k X ai xi = ht. i=1 Do đó k+1 X ai xi = c. i=1 Vậy nên phương trình a1 x1 +a2 x2 +. . .+ak+1 xk+1 = c có nghiệm (x1 , x2 , . . . , xk+1 ). 2). Ta chứng minh khẳng định bằng phương pháp quy nạp theo n. Với n = 2: khẳng định là đúng. Giả sử khẳng định đúng với n = k (k ≥ 2), tức là Pk phương trình ai xi = c nếu có nghiệm thì sẽ có vô số nghiệm. Với n = k + 1, ta i=1 k+1 P sẽ chứng tỏ phương trình ai xi = c nếu có nghiệm thì sẽ có vô số nghiệm. i=1 k+1 P Thật vậy, gọi (t1 , t2 , . . . , tk+1 ) là một nghiệm của phương trình ai xi = c, tức i=1 là k+1 X ai ti = c. i=1
7 Khi đó k X ai ti = c − ak+1 tk+1 . i=1 Xét phương trình k X ai xi = c − ak+1 tk+1 (1.7) i=1 có vế phải là hằng số và có một nghiệm là (t1 , t2 , . . . , tk ) nên theo giả thiết quy nạp thì phương trình này có vô số nghiệm. k+1 P Ứng với mỗi nghiệm (x1 , x2 , . . . , xk ) của (6) thì phương trình ai xi = c có i=1 k+1 P nghiệm là (x1 , x2 , . . . , xk , tk+1 ). Chứng tỏ phương trình ai xi = c có vô số i=1 nghiệm. Ta dễ dàng chứng minh được nghiệm tổng quát của phương trình (1.6) có dạng n−1  P    x 1 = x1 + Li1 ti , i=1      n−1 x2 = x2 + P Li2 ti ,  i=1     ...   n−1 P xn = xn + Lin ti .   i=1 trong đó (x1 , x2 , . . . , xn ) là một nghiệm riêng của (1.6), ti ∈ Z, ∀i = 1, 2, . . . , n. Tuy nhiên, các hệ số Lij (i, j = 1, 2, . . . , n) không có công thức tính tường minh. Bài toán 1.3. Giải phương trình Diophant tuyến tính 6x + 15y + 10z = 3. (1.8) Lời giải. Phương trình đã cho tương đương với 6(x + z) + 15y + 4z = 3. Đặt u = x + z, ta thu được phương trình 15y + 4z = 3 − 6u. (1.9) Ta nhận thấy phương trình 15y + 4z = 1
8 có một nghiệm riêng là (y1 ; z1 ) = (−1; 4) nên phương trình (7a) có một nghiệm riêng là (y0 ; z0 ) = (−3 + 6u; 12 − 24u). Do đó nghiệm tổng quát của phương trình (1.9) là  y = −3 + 6u + 4t , u, t ∈ Z. z = 12 − 24u − 15t Mặt khác, u = x + z suy ra x = u − z = −12 + 25u + 15t. Vậy nên phương trình (1.8) có nghiệm tổng quát là     x = −12 + 25u + 15t  y = −3 + 6u + 4t , u, t ∈ Z.   z = 12 − 24u − 15t  Nhận xét 1.2. Có thể tóm lược cách giải phương trình Diophant tuyến tính nhiều ẩn trên như sau: Từ phương trình Diophant tuyến tính n ẩn, ta đưa về phương trình Diophant tuyến tính n − 1 ẩn (giảm ẩn), tiếp tục như vậy, sau hữu hạn bước, ta nhận được phương trình Diophant tuyến tính 2 ẩn. Mỗi lần giảm số ẩn như vậy ta lại giải phương trình Diophant tuyến tính 2 ẩn (chứa tham số). Vì lẽ đó, ta thu được hệ nghiệm phụ thuộc vào n − 1 tham số. Ví dụ 1.2. Xét phương trình (1.6) với n ≥ 3, ai 6= 0, ∀i = 1, 2, . . . , n. Gọi d = (an−1 , an ). Khi đó an−1 = d.bn−1 , an = d.bn , (bn−1 , bn ) = 1. Do đó (1.6) trở thành a1 x1 + a2 x2 + . . . + an−2 xn−2 + d (bn−1 xn−1 + bn xn ) = c. (1.10) Đưa vào ẩn mới t bằng hệ thức bn−1 xn−1 + bn xn = t. (1.11) Khi đó (1.6) trở thành a1 x1 + a2 x2 + . . . + an−2 xn−2 + dt = c. (1.12) Giả sử x1 , x2 , . . . , xn−2 , t là một nghiệm nguyên của (1.12). Ứng với số t xác định, xét phương trình bn−1 xn−1 + bn xn = t. (1.13)
Do (bn−1 , bn ) = 1
t nên (1.13) nhất định có nghiệm nguyên, chẳng hạn (xn−1 , xn ). Khi đó, rõ ràng (x1 , x2 , . . . , xn−2 , xn−1 , xn ) là nghiệm nguyên của (1.6). Dễ thấy mọi nghiệm nguyên của (1.13) chính là nghiệm của (1.12) với điều kiện (1.11).
9 1.1.2 Nghiệm nguyên dương Xét phương trình Dipophant tuyến tính a1 x1 + a2 x2 + . . . + an xn = c (1.14) với các hệ số ai , c ∈ Z+ , các biến số xi ∈ Z+ , ∀i = 1, 2, . . . , n. Khi đó phương trình (1.14) luôn có hữu hạn nghiệm nguyên dương x = (x1 , x2 , . . . , xn ). Từ giả thiết bài ra, ta có thể hạn chế điều kiện của các biến số bởi (c + ai ) − (a1 + a2 + . . . + an ) 1 ≤ xi ≤ , ∀i = 1, 2, . . . , n. ai Khi đó, cách đơn giản nhất để tìm nghiệm nguyên dương x = (x1 , x2 , . . . , xn ) của phương trình (1.14) là ta cho một biến số xi nào đó lần lượt chạy qua các giá trị có thể có của nó và tìm các biến số còn lại từ phương trình đã cho. Bài toán 1.4. Tìm các nghiệm nguyên dương của phương trình Diophant tuyến tính 6x + 15y + 10z = 200. (1.15) Lời giải. Theo giả thiết, ta có    1 ≤ x ≤ 29  1 ≤ y ≤ 12   1 ≤ z ≤ 17.  . . Hơn nữa, từ giả thiết bài ra, suy ra x .. 5 và y .. 2. - Với y = 2, ta có 3x + 5z = 85 nên     x = 5 thì z = 14;   x = 10 thì z = 11;      x = 15 thì z = 8;   x = 20 thì z = 5;       x = 25 thì z = 2.  - Với y = 4, ta có 3x + 5z = 70 nên    x = 5 thì z = 11;   x = 10 thì z = 8;    x = 15 thì z = 5;   x = 20 thì z = 2. 
10 - Với y = 6, ta có 3x + 5z = 55 nên     x = 5 thì z = 8;  x = 10 thì z = 5;   x = 15 thì z = 2.  - Với y = 8, ta có 3x + 5z = 40 nên  x = 5 thì z = 5; x = 10 thì z = 2. - Với y = 10, ta có 3x + 5z = 25 nên x = 5 thì z = 2. - Với y = 12, ta có 3x + 5z = 10. Phương trình này không có nghiệm nguyên dương. Như vậy, phương trình (1.15) có cả thảy 15 nghiệm nguyên dương (x, y, z) bao gồm (5, 2, 14) , (5, 4, 11) , (5, 6, 8) , (5, 8, 5) , (5, 10, 2) , (10, 2, 11) , (10, 4, 8) , (10, 6, 5) , (10, 8, 2) , (15, 2, 8) , (15, 4, 5) , (15, 6, 2) , (20, 2, 5) , (20, 4, 2) , (25, 2, 2) . 1.2 Nghiệm nguyên dương của hệ phương trình Diophant tuyến tính cơ bản Phần này đề cập tới hệ phương trình Diophant tuyến tính, trình bày về hệ hai phương trình ba ẩn với nguyện nguyên dương giải bằng phương pháp ”chìa khóa” (xem [1],[3] và [5]). Bài toán tổng quát 1.1. Tìm nghiệm nguyên dương của hệ phương trình   a x+b y+c z =s 1 1 1 1 (1.16)  a x+b y+c z =s . 2 2 2 2 Phương pháp giải: Ta gọi ”chìa khóa” của hệ (1) là bộ số (x0 , y0 , z0 ) thỏa mãn điều kiện: x0 , y0 , z0 ∈ Z và