Tài liệu Một vài vấn đề về phương trình Diophantine (Luận văn thạc sĩ)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ NGỌC KHÁNH MỘT VÀI VẤN ĐỀ VỀ PHƯƠNG TRÌNH DIOPHANTINE LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ NGỌC KHÁNH MỘT VÀI VẤN ĐỀ VỀ PHƯƠNG TRÌNH DIOPHANTINE LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 01 13 Người hướng dẫn khoa học PGS.TS. ĐÀM VĂN NHỈ THÁI NGUYÊN - NĂM 2015 i Mục lục Mở đầu 1 1 Giải phương trình Diophantine 1.1 Phương trình Diophantine . . . . . . . . . . . . . . . 1.1.1 Vành chính Z . . . . . . . . . . . . . . . . . . 1.1.2 Phép chia với dư . . . . . . . . . . . . . . . . 1.1.3 Khái niệm phương trình Diophantine . . . . . 1.1.4 Phương trình Diophantine có điều kiện . . . . 1.1.5 Tổng các số chính phương . . . . . . . . . . . . 1.2 Một vài phương pháp giải phương trình Diophantine . 1.2.1 Phương pháp phân tích thành nhân tử . . . . . 1.2.2 Phương pháp đồng dư . . . . . . . . . . . . . . 1.2.3 Phương pháp đánh giá . . . . . . . . . . . . . 1.2.4 Phương pháp tham số hóa . . . . . . . . . . . 1.2.5 Phương trình nghiệm hữu tỷ qua tham số hóa . 1.2.6 Chứng minh phương trình nhiều vô hạn nghiệm 1.2.7 Công thức tính nghiệm . . . . . . . . . . . . . 1.3 Một vài phương trình cổ điển . . . . . . . . . . . . . . 1.3.1 Phương trình Pythagoras . . . . . . . . . . . . 1.3.2 Phương trình Mordell . . . . . . . . . . . . . . 1.3.3 Phương trình Pell . . . . . . . . . . . . . . . . 2 Hệ phương trình Pell 2.1 Hệ phương trình Pell . . . . 2.1.1 Tiêu chuẩn Legendre 2.1.2 Hệ phương trình Pell 2.2 Phương trình ba hệ số tổ hợp . . . . . . . . . . . . . . . liên tiếp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 4 5 8 11 13 13 15 16 18 21 26 28 29 29 32 34 . . . . 40 40 40 41 42 ii Kết luận 45 Tài liệu tham khảo 46 1 MỞ ĐẦU Số học nói chung và Phương trình Diophantine nói riêng là những lĩnh vực cổ xưa nhất của Toán học, và cũng là lĩnh vực còn tồn tại nhiều những bài toán, giả thuyết chưa có câu trả lời. Trong suốt quá trình phát triển của Toán học, phương trình Diophantine luôn thu hút được nhiều người quan tâm nghiên cứu và tìm hiểu. Chính việc đi tìm lời giải cho các bài toán hay chứng minh các giả thuyết về phương trình Diophantine đã làm nảy sinh các lý thuyết, phương pháp khác của Toán học. Các bài toán về phương trình Diophantine không có quy tắc giải tổng quát, hoặc nếu có cũng chỉ là đối với các dạng đơn giản. Mỗi phương trình với dạng riêng của nó đòi hỏi một cách giải đặc trưng phù hợp. Điều này có tác dụng rèn luyện tư duy mền dẻo, linh hoạt hơn cho người làm toán.Chính vì thế, trong hầu hết các kỳ thi quan trọng như thi học sinh giỏi Toán quốc gia, quốc tế, thi Olympic toán..., các bài toán liên quan đến phương trình Diophantine cũng hay được đề cập đến và thường là những bài toán khó. Việc hệ thống một cách tương đối các phương pháp giải phương trình Diophantine và đưa ra các vấn đề mở về phương trình Diophantine là cần thiết đối với việc giảng dạy và nghiên cứu toán học, đặc biệt là công tác ôn luyện học sinh giỏi. Với lý do đó, trong luận văn này, tôi trình bày khái niệm phương trình Diophantine, hệ phương trình Pell và tổng hợp một số phương pháp giải phương trình và hệ phương trình này. Ngoài phần Mở đầu và Kết luận, luận văn được chia làm hai chương đề cập đến các vấn đề sau: Chương 1: Giải phương trình Diophantine. 1.1 Phương trình Diophantine. 1.2 Một vài cách giải phương trình Diophantine. 1.3 Một vài phương trình cổ điển. Chương 2: Hệ phương trình Pell 2.1 Trình bày Hệ phương trình Pell. 2 2.2 Trình bày Phương trình ba hệ số tổ hợp liên tiếp. Luận văn được hoàn thành với sự hướng dẫn nhiệt tình của PGS.TS. Đàm Văn Nhỉ. Tôi bày tỏ lòng kính trọng và biết ơn sâu sắc đến Thầy, người đã dành cho tôi sự hướng dẫn chu đáo, nghiêm túc trong qua trình học tập, nghiên cứu và thực hiện luận văn. Tôi xin gửi lời cảm ơn sâu sắc tới các Thầy Cô khoa Toán trường Đại Học Khoa Học - Đại Học Thái Nguyên,các Thầy, Cô tham gia giảng dạy khóa Cao học 2013 - 2015,Trường THPT Lý Tự Trọng và bạn bè đồng nghiệp đã giúp đỡ tạo điều kiện cho tôi hoàn thành bản luận văn này. Thái Nguyên, ngày 20 tháng 4 năm 2015 Vũ Ngọc Khánh 3 Chương 1 Giải phương trình Diophantine 1.1 Phương trình Diophantine 1.1.1 Vành chính Z Định nghĩa 1.1.1. Miền nguyên R được gọi là một vành chính nếu mỗi iđêan của R đều là một iđêan chính. Ta sẽ sử dụng kết quả về vành Euclide để chỉ ra rằng, vành Z là một vành chính, có nghĩa: Mỗi iđêan của Z đều do một phần tử sinh ra. Do vậy, ta sẽ bắt đầu bằng khái niệm vành Euclide. Định nghĩa 1.1.2. Cho miền nguyên R. Ánh xạ δ : R∗ → N, x 7→ δ(x), từ tập các phần tử khác 0 của R đến tập các số tự nhiên N thỏa mãn hai điều kiện sau đây: (1) Với mọi a, b ∈ R∗ và a|b thì δ(a) 6 δ(b). (2) Với mọi a, b ∈ R, b 6= 0, có tồn tại q, r ∈ R sao cho a = qb + r với hoặc r = 0 hoặc δ(r) < δ(b) khi r 6= 0 được gọi là một ánh xạ Euclide. Định nghĩa 1.1.3. Miền nguyên R được gọi là một vành Euclide nếu có một ánh xạ Euclide tác động lên tập R∗ . Bổ đề 1.1.4. Mỗi vành Euclide đều là một vành chính. Chứng minh: Giả sử R là vành Euclide với ánh xạ Euclide δ : R∗ → N. Vì R là vành Euclide nên nó là một miền nguyên. Giả sử I là một iđêan của R. Nếu I = 0 thì I = (0) là một iđêan chính. Nếu I 6= 0 thì có phần tử a ∈ I, a 6= 0. Đặt 4 I ∗ = I \ {0}. Vì δ(I ∗ ) ⊂ N nên có a0 ∈ I ∗ thỏa mãn δ(a0 ) 6 δ(x) với mọi x ∈ I ∗ . Vì a0 ∈ I nên iđêan (a0 ) ⊆ I. Bây giờ ta chỉ ra I = (a0 ). Thật vậy, giả sử a ∈ I. Do a0 6= 0 và R là vành Euclide nên tồn tại q, r ∈ R sao ch a = qa0 + r với r = 0 hoặc δ(r) < δ(a0 ). Nếu r 6= 0 thì r ∈ I ∗ và δ(r) < δ(a0 ) : mâu thuẫn. Vậy r = 0 và a = qa0 . Từ đây suy ra a ∈ (a0 ). Do a được lấy tùy ý nên I = (a0 ) và như vậy R là một vành iđêan chính. Hệ quả 1.1.5. Vành Z là một vành chính. Chứng minh: Vành Z là một miền nguyên. Ánh xạ δ : Z∗ → N, n 7→ |n|, là một ánh xạ Euclide. Do vậy, vành Z là một vành Euclide. Theo Bổ đề 1.1.4, vành Z là một vành iđêan chính. 1.1.2 Phép chia với dư Định nghĩa 1.1.6. Cho hai số nguyên a, b ∈ Z, b 6= 0. Số a được gọi là chia hết cho số b hay b chia hết a nếu có c ∈ Z thỏa mãn a = bc. . Trong nhiều trường hợp, thay cho việc nói a chia hết cho b ta viết a .. b hoặc nói b chia hết a và viết b|a. Khi a = bc thì b được gọi là một ước của a.. Ví dụ 1.1.7. Chứng minh rằng, tồn tại vô số số nguyên n thỏa mãn n4 + 1871 chia hết cho 1952. Bài giải: Vì n4 + 1871 = n4 − 81 + 1952 nên n4 + 1871 chia hết cho 1952 khi và chỉ khi n4 − 81 chia hết cho 1952 hay (n − 3)(n + 3)(n2 + 9) chia hết cho 1952. Ta chỉ cần lấy n = 1952k ± 3 với k ∈ Z. Định lý 1.1.8. Với mỗi cặp số nguyên a, b ∈ Z, b 6= 0, luôn luôn tồn tại duy nhất một cặp số nguyên q, r ∈ Z sao cho a = qb + r, trong đó 0 6 r < |b|. Chứng minh: Sự tồn tại: Đặt T = {n|b| sao cho n|b| 6 a, n ∈ Z}. Vì |b| > 1 nên −|a||b| 6 −|a| 6 a. Do đó −|a||b| ∈ T. Vậy T 6= ∅. Vì T là tập bị chặn trên nên T có một số lớn nhất m|b|. Từ m|b| 6 a ta suy ra r = a − m|b| > 0 và r ∈ Z. Ta lại có (m + 1)|b| = m|b| + |b| > m|b|. Do tính lớn nhất của m|b| trong T nên (m + 1)|b| > a. Như vậy |b| > a − m|b| = r và ta có a = qb + r với 0 6 r < |b|. Tính duy nhất: Giả sử có hai sự biểu diễn a = qb+r với 0 6 r < |b| và a = q1 b+r1 với 0 6 r1 < |b|. Trừ vế cho vế, ta có r − r1 = b(q1 − q). Từ |r − r1 | < |b| ta suy ra |q1 − q||b| < |b|. Vậy q = q1 và hiển nhiên r = r1 . 5 Hệ quả 1.1.9. Với biểu diễn a = qb + r, 0 6 r < |b|, có (a, b) = (b, r). Ví dụ 1.1.10. Đặt an = 12011 + 22011 + · · · + n2011 với n ∈ N∗ . Chứng minh rằng an không chia hết cho n + 2. Bài giải: Ta có 2an = [n2005 + 22005 ] + [(n − 1)2005 + 32005 ] + · · · + [22005 + n2005 ] + 2. Vậy 2an = (n + 2)d + 2, d ∈ N∗ và ta suy ra an không chia hết cho n + 2. 1.1.3 Khái niệm phương trình Diophantine Một vấn đề khá cổ điển trong Số học là giải phương trình đa thức với hệ số nguyên trong tập Z. Đó là giải phương trình nghiệm nguyên hay còn gọi là phương trình Diophantine. Để hiểu rõ bài toán này, trước tiên ta nhắc lại một vài khái niệm. Định nghĩa 1.1.11. Cho đa thức f (x1 , . . . , xn ) với các hệ số là các số hữu tỉ hoặc các số nguyên. Phương trình f (x1 , . . . , xn ) = 0 được gọi là phương trình Diophantine. Giải phương trình Diophantine f (x1 , . . . , xn ) = 0 tức là tìm tất cả các số hữu tỉ, các số nguyên hay các số nguyên không âm α1 , . . . , αn để sao cho f (α1 , . . . , αn ) = 0. Cho b, a1 , a2 , . . . , an ∈ Z và các số ai không đồng thời bằng 0. Phương trình dạng a1 x1 + a2 x2 + · · · + an xn = b, (D1 ), được gọi là phương trình Diophantine bậc nhất hay phương trình Diophantine tuyến tính. Ta có ba kết quả chính và một vấn đề mở sau đây. Định lý 1.1.12. Phương trình (D1 ) có nghiệm nguyên (zi ) khi và chỉ khi b chia hết cho d = (a1 , . . . , an ). Có thể chọn nghiệm nguyên (zi ) thỏa mãn điều kiện |zi | 6 |b| + (n − 1) max{|aj | | j = 1, . . . , n}, ∀i. Đặc biệt, nếu (a1 , . . . , an ) = 1 thì (D1 ) có nghiệm nguyên với mọi số nguyên b. Chứng minh: Đặt (a1 , . . . , an ) = d. Nếu (D1 ) có nghiệm thì b phải chia hết cho d; còn nếu b không chia hết cho d thì (D1 ) vô nghiệm. Vậy, không làm mất tính tổng quát, ta có thể giả thiết d = 1, b 6= 0. Vì vành Z là vành các iđêan chính và (a1 , . . . , an ) = 1 nên tồn tại các số nguyên α1 , . . . , αn ∈ Z thỏa mãn a1 α1 + a2 α2 + · · · + an αn = 1 và như thế a1 bα1 + a2 bα2 + · · · + an bαn = b. Điều 6 này chứng tỏ phương trình (D1 ) nhận x1 = bα1 , . . . , xn = bαn làm một nghiệm nguyên. Tiếp theo, giả sử x1 , . . . , xn là một nghiệm nguyên của phương trình (D1 ). Ta biểu diễn xi = qi an + zi , 0 6 zi < |an |, i = 1, . . . , n − 1, với qi , zi nguyên. Đặt n−1 n n−1 n−1 n P P P P P zn = xn + ai qi . Vậy b = ai xi = ai (qi an + zi ) + an (zn − ai q i ) = ai zi . i=1 i=1 i=1 i=1 i=1 Điều này chứng tỏ (zi ) là nghiệm của (D1 ). Ta có |zi | < |an | cho mọi i = 1, . . . , n−1; n−1 P còn cho zn ta có |an zn | = |b − ai zi | 6 |b| + (n − 1)|an | max{|aj | | j = 1, . . . , n}. i=1 Chia cho |an |, ta được |zi | 6 |b| + (n − 1) max{|aj | | j = 1, . . . , n}, i = 1, . . . , n. Định lý 1.1.13. Cho b, a1 , a2 , . . . , an ∈ Z và các số ai không dồng thời bằng 0. Nếu b chia hết cho (a1 , a2 , . . . , an ) thì phương trình (D1 ) có nhiều vô hạn nghiệm nguyên. Chứng minh: Theo Định lý 1.1.12, khi b chia hết cho (a1 , a2 , . . . , an ) thì phương trình (D1 ) có nghiệm nguyên (α1 , . . . , αn ). Vì a1 , a2 , . . . , an không đồng thời bằng 0 nên tồn tại ai 6= 0. Không hạn chế có thể giả thiết an 6= 0. Xét x1 = α1 + n−1 P ai ti với các ti ∈ Z. Khi đó an t1 , . . . , xn−1 = αn−1 + an tn−1 và xn = αn − n P i=1 ai xi = b hay (x1 , . . . , xn ) là nghiệm của (D1 ). Vì các ti nhận các giá trị tùy ý i=1 thuộc Z nên (D1 ) có nhiều vô hạn nghiệm. Ví dụ 1.1.14. Giải phương trình tuyến tính sau đây trong tập Z : 3x + 4y + 5z = 6. Bài giải: Vì(3, 4, 5) = 1, mà 6 :̇ 1, nên phương trình đã cho có nghiệm. Trong Z5 ta xét 3x + 4y = 1 hay 3x + 4y = 1 + 5t. Dễ dàng nhận được x0 = −1 + 3t, y0 = 1 − t. Nghiệm tổng quát của 3x + 4y = 1 + 5t là x = −1 + 3t + 4u, y = 1 − t − 3u. Dễ dàng suy ra z = 1 − t. Tóm lại, nghiệm tổng quát của phương trình đã cho là x = −1 + 3t + 4u, y = 1 − t − 3u, z = 1 − t với t, u ∈ Z. Ví dụ 1.1.15. Số nghiệm nguyên không âm của phương trình tuyến tính x1 +
· · · + xk = n bằng n+k−1 k−1 . Bài giải: Ký hiệu số nghiệm nguyên không âm của phương trình là Nk (n). Ta có N1 (n) = 1. Tính N2 (n), tức là tính số nghiệm nguyên không âm của phương trình x1 + x2 = n. Phương trình này có các nghiệm (0, n), (1, n − 1), ..., (n, 0) nên
N2 (n) = n + 1 = n+1 1 . Để tính N3 (n) ta xét phương trình x1 + x2 + x3 = n. Cho 7 x3 = 0, 1, 2, ..., n, ta có N3 (n) = N2 (n) + N2 (n − 1) + · · · + N2 (2)  + N2 (1) + N 2 (0) =
n + k − 1 (n + 1) + · · · + 1. Vậy N3 (n) = n+2 bằng 2 . Ta chứng minh Nk (n) = k−1 qui nạp. Hiển nhiên + Nk−1 (n − 2) + · · · + Nk−1 (0). k−1 (n) + N k−1 (n − 1)  Nk (n)= N n+k−2 n+k−3 k−2 n+k−1 + + ··· + = . Do đó Nk (n) = k−2 k−2 k−2 k−1 Ví dụ 1.1.16. Cho k, m, n là những số nguyên dương. Tính số nghiệm nguyên không âm của hệ  x1 + · · · + xn = y 1 + · · · + y m + 1 x1 + · · · + xn 6 nk, m < n. Bài giải: Cho mỗi số nguyên dương s, 1 6 s 6 nk, ta kí hiệu số nghiệm nguyên không âm của hệ x1 + x2 + · · · + xn = s là Nn (s). Khi đó số nghiệm nguyên không âm của hệ  x1 + · · · + xn = s y1 + · · · + ym = s − 1  là Nn (s)Nm (s − 1) =  n+s−1 n−1  m+s−2 m−1 theo Ví dụ 1.1.15. Hiển nhiên, nếu s < n thì Nn (s) =0. Vậy, số nghiệm nguyên phương trình  âm của hệ   đã cho  không nk nk P n+s−1 m+s−2 P n+s−1 m+s−2 . = là S(m, n) = n−1 m−1 n−1 m−1 s=n s=2 Định lý 1.1.17. Giả thiết các số a1 , a2 , . . . , an ∈ N+ và (a1 , . . . , an ) = 1. Nếu n−1 P b > (an − 1) ai thì phương trình (D1 ) có ít nhất một nghiệm nguyên không i=1 âm (α1 , . . . , αn ) ∈ Nn . Chứng minh: Theo Định lý 1.1.13, tồn tại các số nguyên y1 , . . . , yn thỏa mãn a1 y1 +a2 y2 +· · ·+an yn = b. Sử dụng phép chia với dư, ta biểu diễn yi = qi an +αi , 0 6 αi 6 an − 1, i = 1, . . . , n − 1, với qi , αi nguyên. Đặt αn = yn + n−1 P ai qi . Vậy i=1 b= n−1 X ai y i + an y n = i=1 n−1 X i=1 ai (qi an + αi ) + an (αn − n−1 X i=1 ai q i ) = n−1 X ai α i + an α n . i=1 Điều này chứng tỏ (αi ) là một nghiệm của (D1 ) và b 6 (an − 1) n−1 P ai + an αn . Vì i=1 b > (an − 1) n−1 P ai nên an αn > 0 và như vậy αn > 0. i=1 Hai ví dụ dưới đây chính là bài toán: Xác định số nguyên dương bé nhất ` để sao cho phương trình ax + by = b giải được trong N với mọi số nguyên dương b > `. 8 Ví dụ 1.1.18. Với những con tem 4 xu và 5 xu ta có thể tạo được những loại bưu phí nào? Bài giải: Ta có ngay những loại bưu phí 4, 5, 8 = 2.4, 9 = 4 + 5, 10 = 2.5, 12 = 3.4, 13 = 2.4 + 5, 14 = 2.5 + 4 và 15 = 3.5 được dán bằng hai loại tem trên. Bây giờ ta chỉ ra, mọi bưu phí n > 12 xu cũng được dán bằng hai loại tem trên. Thực ra ta chỉ cần xét n > 15. Giả sử n > 16 được biểu diễn bằng n = k.4 + h.5. Nếu k > 1 thì n + 1 = (k − 1).4 + (h + 1).5; Nếu k = 0 thì h > 3. Khi đó n + 1 = 1 + h.5 = 5.4 + (h − 4).5. Từ đó có điều cần chứng minh. Ví dụ 1.1.19. Với những con tem 5 xu và 6 xu ta có thể tạo được những loại bưu phí nào? Bài giải: Ta có ngay những loại bưu phí 5, 6, 10 = 2.5, 11 = 5 + 6, 12 = 2.6, 15 = 3.5, 16 = 2.5 + 6, 17 = 2.6 + 5, 18 = 3.6, 20 = 4.5, 21 = 3.5 + 6, 22 = 2.5 + 2.6, 23 = 3.6 + 5, 24 = 4.6 được dán bằng hai loại tem trên. Bây giờ ta chỉ ra, mọi bưu phí b với b > 19 xu đều dán được bằng hai loại tem trên. Đã kiểm tra các số 20, 21, 22, 23, 24. Giả sử n > 24 được biểu diễn bằng n = k.5 + h.6. Nếu k > 1 thì n + 1 = (k − 1).5 + (h + 1).6; Nếu k = 0 thì h > 4. Khi đó n + 1 = 5.5 + (h − 4).6. Vậy n + 1 = s.5 + r.6 và suy ra điều cần chứng minh. 1.1.4 Phương trình Diophantine có điều kiện Tiếp theo, xét phương trình Diophantine có điều kiện: Giả sử các ai là những số nguyên dương. Tìm số nghiệm nguyên của phương trình tuyến tính a1 x1 + a2 x2 + · · · + an xn = b thỏa mãn xi > αi > 0 với mọi i = 1, . . . , n. P ka1   P kan  . Hệ số của xb x ··· x Xét chuỗi lũy thừa hình thức f (x) = k=α1 k=αn trong f (x) chính là số nghiệm của hệ đã cho. Dễ dàng chỉ ra n P ai αi xi=1 f (x) = . (1 − xa1 )(1 − xa2 ) . . . (1 − xan ) Vậy ta có kết quả sau đây: Định lý 1.1.20. Ký hiệu Nb là số nghiệm nguyên của hệ  a1 x 1 + a2 x 2 + · · · + an x n = b xi > αi > 0, i = 1, . . . , n. n P ai αi xi=1 Khi đó hàm sinh của dãy (Nb ) là f (x) = . (1 − xa1 )(1 − xa2 ) . . . (1 − xan ) 9 Ví dụ 1.1.21. Xác định số nghiệm nguyên của hệ phương trình sau:  2x1 + 2x2 + x3 = 2010 x1 > 0, x2 > 2, x3 > 100. Bài giải: Ta xác định hệ số của x2010 trong khai triển tích 3 chuỗi lũy thừa hình thức sau f (x) = (1 + x2 + x4 + x6 + · · · )(x4 + x6 + x8 + · · · ) (x100 + x101 + x102 + · · · ) x104 x104 = = . (1 − x2 )(1 − x2 )(1 − x) (1 − x)3 (1 + x)2 ∞ P 1 r−1 Bằng phương pháp quy nạp theo r, dễ dàng chỉ ra = xs . Cr−1+s (1 − x)r s=0 P  P  ∞ ∞ Vậy f (x) = x104 C22+s xs C11+s (−x)s . Hệ số của x2010 cũng chính là số s=0 s=0 nghiệm của hệ và bằng 1906 P (−1)s C22+s C11907−s . s=0 Ví dụ 1.1.22. Xác định số nghiệm nguyên của hệ phương trình sau:  2x1 + x2 + x3 + 2x4 = 18 x1 > 0, x2 > 3, x3 > 2, x4 > 1. Bài giải: Ta xác định hệ số của x18 trong khai triển tích 4 chuỗi lũy thừa hình thức sau f (x) = (1 + x2 + x4 + x6 + · · · )(x4 + x5 + x6 + · · · ) (x2 + x3 + x4 + · · · )(x2 + x4 + x6 + · · · ) x8 x8 = = (1 − x2 )(1 − x)(1 − x)(1 − x2 ) (1 − x)4 (1 + x)2 = x 8 ∞ X C33+s xs ∞  X s=0 C11+s (−x)s  . s=0 Số nghiệm của hệ bằng hệ số của x18 trong f (x) và nó chính bằng hệ số của x10 P  P  ∞ ∞ 10 P trong khai triển C33+s xs C11+s (−x)s . Số đó bằng (−1)s C33+s C111−s . s=0 s=0 s=0 Cuối cùng là việc xét phương trình Diophantine có điều kiện ngặt hơn: Giả sử các ai là những số nguyên dương. Tìm số nghiệm nguyên của phương trình a1 x1 + a2 x2 + · · · + an xn = b thỏa mãn βi > xi > αi > 0 với mọi i = 1, . . . , n. Xét chuỗi lũy thừa hình thức f (x) =  P β1 k=α1 xka1  P β2 xka2 k=α2 số của xb trong f (x) chính là số nghiệm của hệ đã cho.  ···  P βn k=αn xkan  . Hệ 10 Ví dụ 1.1.23. Xác định số nguyên dương n để có số nguyên dương m viết được trong dạng m = a1 + a2 + · · · + an với a1 ∈ {1}, a2 ∈ {1, 2}, . . . , an ∈ {1, 2, . . . , n} với ít nhất (n − 1)! cách. Bài giải: Với mỗi n ta xét đa thức fn (x) = x(x + x2 ) . . . (x + x2 + · · · + xn ). Đa thức này có bậc deg f = n(n + 1) . Giả sử biểu diễn đa thức 2 f (x) = a1 x + a2 x2 + · · · + am xm + · · · + a n(n+1) x n(n+1) 2 . 2 Khi đó hệ số am là số cách viết m = a1 + a2 + · · · + an với a1 ∈ {1}, a2 ∈ {1, 2}, . . . , an ∈ {1, 2, . . . , n}. Ví dụ 1.1.24. Với số nguyên dương n, hãy xác định số đa thức p(x) với các hệ số thuộc tập {0, 1, 2, 3} thỏa mãn p(2) = n. Bài giải: Giả sử p(x) = am xm + am−1 xm−1 + · · · + a1 x + a0 với các ai ∈ {0, 1, 2, 3} và p(2) = n. Việc xác định số đa thức p(x) thỏa mãn yêu cầu đặt ra tương đương với việc tìm số các dãy (a0 , a1 , a2 , . . .) thỏa mãn điều kiện các ai ∈ {0, 1, 2, 3} và a0 + 2a1 + 22 a2 + · · · = n. Xét hàm sinh thường f (x) = (1 + x + x2 + x3 )(1 + x2 + x4 + x6 )(1 + x4 + x8 + x12 ) . . . , ở đó 1 + x + x2 + x3 thể hiện việc chọn khác nhau cho a0 , 1 + x2 + x4 + x6 thể hiện việc chọn khác nhau cho a1 , 1 + x4 + x8 + x12 thể hiện việc chọn khác nhau cho a2 , v.v.... Ta có ngay f (x) = x4 − 1 x8 − 1 x16 − 1 x64 − 1 1 . 2 . 4 . 8 ... = và được x−1 x −1 x −1 x −1 (x − 1)(x2 − 1) 1 1 f (x) = (x − 1)−2 + 2 2   1 −x  h i 1 −2 −2 2 2 4 = (1 − x+ x − · · · ) + (1 + x + x + · · · ) 2 1 2 h với h 1 2
(−2)(−3) . . . (−2 − n + 1) −2 n n! i = (−1)n (n + 1). Từ đây được biểu diễn f (x) = i (1 + 2x + 3x2 + · · · ) + (1 + x2 + x4 + · · · ) đa thức p(x) thỏa mãn đầu bài. = ∞  m P [ r=0 n ] + 1 xr . Như vậy có [ ] + 1 2 2  11 1.1.5 Tổng các số chính phương Trong mục này ta tìm điều kiện cần và đủ để số tự nhiên n có thể biểu diễn thành tổng các số chính phương. Định lý 1.1.25. Cho số nguyên dương n ≥ 2 với biểu diễn n = x2 + y 2 , trong đó x, y nguyên và x > y > 0. Nếu p là số nguyên tố thỏa mãn các điều kiện pe |n, pe+1 6 |n và p ≡ 3(mod 4) thì 2|e. Chứng minh: Giả sử p là số nguyên tố thỏa mãn pe |n, pe+1 6 |n và n = x2 +y 2 ≥ 2. Ta cần phải chỉ ra, nếu p và e đều là số lẻ thì p ≡ 1(mod 4). Thật vậy, đặt d = (x, y). Khi đó có u, v ∈ Z để x = du, y = dv với (u, v) = 1 và n = d2 (u2 + v 2 ). Gọi j là số nguyên lớn nhất để pj |d. Khi đó e − 2j là số nguyên lớn nhất để pe−2j |(u2 + v 2 ). Vì e là số lẻ nên e − 2j > 1. Do đó p|(u2 + v 2 ). Vì (u, v) = 1 nên p ≡ 1(mod 4). Vì p ≡ 3(mod 4) nên 2|e. Định lý 1.1.26. [Wilson] Với số nguyên tố p có (p − 1)! + 1 ≡ 0(mod p). Chứng minh: Khi p = 2, kết quả là hiển nhiên. Khi p > 2, mỗi số nguyên n thỏa mãn 1 6 n 6 p − 1 đều nguyên tố với p. Vậy có đúng một số nguyên s p−1 cặp (n, s) như vậy. Lấy 2 p−3 các phương trình ns ≡ 1(mod p) với n > 2 như vậy được 2.3.4 . . . (p − tích 2 3)(p − 2) ≡ 1(mod p). Nhân hai vế phương rình này với tích 1 và p − 1 được thỏa mãn 1 6 s 6 p − 1 và ns ≡ 1(mod p). Ta có (p − 1)! + 1 ≡ 0(mod p). Ví dụ 1.1.27. Phương trình  p − 1
2 2 ! + 1 ≡ 0(mod p) thỏa mãn với tất cả các số nguyên tố p dạng 4n + 1. Bài giải: Theo Định lý 1.1.26 có (p − 1)! + 1 ≡ 0(mod p) hay biểu diễn (p−1)/2 Y k=1 (p−1)/2 k Y (p − k) + 1 ≡ 0(mod p). Như vậy, ta có thể biến đổi k=1 (p−1)/2 (p−1)/2 Q Q p − 1

2 ! + 1 = (−1)(p−1)/2 k (p − k) + 1 ≡ 0(mod p). 2 k=1 k=1 Ví dụ 1.1.28. Chứng minh rằng, nếu p là số nguyên tố thì phương trình x2 +1 ≡ 0(mod p) có nghiệm khi và chỉ khi hoặc p = 2 hoặc p ≡ 1(mod 4). 12 Bài giải: Với p = 2, phương trình x2 +1 ≡ 0(mod 2) có nghiệm x = 1, chẳng hạn. p−1 chẳng hạn, 2 theo ví dụ trên. Ngược lại, giả thiết phương trình x2 + 1 ≡ 0(mod p) có nghiệm Với p ≡ 1(mod 4) phương trình x2 + 1 ≡ 0(mod p) có nghiệm x = nguyên x0 . Khi đó x20 + 1 chia hết cho p. Từ đây suy ra x0 không chia hết cho p. Từ (x0 , p) = 1 suy ra xp−1 ≡ 1(mod p) theo Định lý Fermat bé. Giả sử p = 4k − 1 0 với k > 0. Vì x20 ≡ −1(mod p) nên 1 ≡ xp−1 ≡ x04k−2 ≡ (x20 )2k−1 ≡ −1(mod p). Do 0 vậy 2 ≡ 0(mod p). Vậy p = 2. Nếu p > 2 thì 2 ≡ 0(mod p) là sai. Vậy, điều giả sử là sai và suy ra p ≡ 1(mod 4). Ví dụ 1.1.29. Chứng minh rằng, nếu số nguyên tố p thỏa mãn điều kiện p ≡ 1(mod 4) thì ta luôn có biểu diễn p = x2 + y 2 với x, y nguyên. Bài giải: Kết quả được suy ra từ các ví dụ trên. Định lý 1.1.30. Với mọi số tự nhiên n ≥ 4, số n3 đều có thể biểu diễn được dưới dạng tổng của 5 lập phương các số nguyên với trị tuyệt đối nhỏ hơn n thực sự. Chứng minh: Trước tiên ta kiểm tra kết luận trực tiếp cho n = 4, 5, 6, 7 : 43 = 33 + 33 + 23 + 13 + 13 53 = 43 + 43 + (−1)3 + (−1)3 + (−1)3 63 = 53 + 43 + 33 + 03 + 03 73 = 63 + 53 + 13 + 13 + 03 . Xét n ≥ 8. Khi n là số nguyên dương lẻ, n = 2r + 1, ta có n3 = (2r + 1)3 = (2r − 1)3 + (r + 4)3 + (4 − r)3 + (−5)3 + (−1)3 với các số 2r − 1, r + 4, r − 4, −5, −1 đều có trị tuyệt đối nhỏ hơn n. Khi n là số nguyên dương chẵn, n = 2r, kết luận được chứng minh bằng phương pháp quy nạp theo r dựa vào nhận xét : Nếu có biểu diễn r3 = r13 + r23 + r33 + r43 + r53 thì n3 = (2r1 )3 + (2r2 )3 + (2r3 )3 + (2r4 )3 + (2r5 )3 . 13 1.2 1.2.1 Một vài phương pháp giải phương trình Diophantine Phương pháp phân tích thành nhân tử Xét phương trình f (x, y, . . . , z) = m. Giả sử ta có sự phân tích thành tích các nhân tử bất khả quy f (x, y, . . . , z) = f1 (x, y, . . . , z) . . . fs (x, y, . . . , z). Khi đó ta phân tích số nguyên m và ta nhận được hệ phương trình tương ứng. Ví dụ 1.2.1. Tìm tất cả các nghiệm nguyên (x, y) của phương trình (x2 + 1)(y 2 + 1) + 2(x − y)(1 − xy) = 4(1 + xy). Bài giải: Biểu diễn (x2 + 1)(y 2 + 1) + 2(x − y)(1 − xy) = 4(1 + xy) thành (xy − 1)2 + 9x − y)2 + 2(x − y)(1 − xy) = 4. Vậy [xy − 1 − (x − y)]2 = 4 hay (x + 1)(y − 1) = ±2. Như vậy ta có 8 hệ sau đây:   x+1=2 y−1=1  x+1=2 y − 1 = −1 x+1=1 y−1=2  x + 1 = −1 y−1=2  x + 1 = −2 y − 1 = −1  x + 1 = −2 y−1=1  x + 1 = −1 y − 1 = −2  x+1=1 y − 1 = −2. Giải ra được 8 nghiệm (1, 2), (0, 3), (−3, 0), (−2, −1), (1, 0), (−2, 3), (−3, 2), (0, −1). Ví dụ 1.2.2. Giả sử p và q là hai số nguyên tố phân biệt. Tìm tất cả các nghiệm nguyên dương (x, y) của phương trình 1 1 1 + = . x y pq Bài giải: Biểu diễn phương trình đã cho thành phương trình tương đương (x − pq)(y − pq) = p2 q 2 . 14 Từ 1 1 1 1 1 + = suy ra < và như vậy x > pq. Từ phương trình tương đương x y pq x pq suy ra các hệ sau đây;   x − pq = 1 y − pq = p2 q 2 ;  x − pq = p2 y − pq = q 2 ;   x − pq = p2 q y − pq = q;   x − pq = p y − pq = pq 2 ;  x − pq = pq y − pq = pq; x − pq = q 2 y − pq = p2 ; x − pq = q y − pq = p2 q x − pq = pq 2 y − pq = p  x − pq = p2 q 2 y − pq = 1. Giải từng hệ, ta nhận 9 nghiệm (pq+1, pq+p2 q 2 ), (p+pq, pq+pq 2 ), (q+pq, pq+p2 q), (p2 + pq, q 2 + pq), (2pq, 2pq), (pq + pq 2 , p + pq), (pq + p2 q, pq + q), (pq + q 2 , pq + p2 ), (pq + p2 q 2 , pq + 1). Ví dụ 1.2.3. [T. Andreescu and D. Andrica] Xác định tất cả các bộ ba số nguyên dương (x, y, z) thỏa mãn phương trình x3 + y 3 + z 3 − 3xyz = p với số nguyên tố p > 3. Bài giải: Vì p = x3 + y 3 + z 3 − 3xyz = (x + y + z)(x2 + y 2 + z 2 − xy − yz − zx) và (x + y + z > 1 nên x + y + z = p và (x − y)2 + (y − z)2 + (z − x)2 = 2. Không hạn chế có thể giả thiết x > y > z > 1. Như vậy, ta phải xét các trường hợp dưới đây: Trường hợp x = y : Ta có hệ y = z + 1, x = z + 1 và x + y + z = p. Vậy p−2 p+1 ,x = y = khi p = 3k + 2. 3 3 Trường hợp x > y = z : Ta có hệ y = z, x = y + 1 và x + y + z = p. Vậy p−1 p+2 y=z= ,x = khi p = 3k + 1. 3 3 Tóm lại, nếu p = 3k + 1 thì phương trình có ba nghiệm z= ( p−1 p−1 p+2 p−1 p+2 p−1 p+2 p−1 p−1 , , ), ( , , ), ( , , ). 3 3 3 3 3 3 3 3 3 Nếu p = 3k+2 thì phương trình có ba nghiệm ( và ( p+1 p+1 p−2 , , ). 3 3 3 p−2 p+1 p+1 p+1 p−2 p+1 , , ), ( , , ) 3 3 3 3 3 3 Ví dụ 1.2.4. [T. Andreescu] Xác định tất cả các số nguyên n để phương trình sau đây có nghiệm nguyên dương x3 + y 3 + z 3 − 3xyz = n. 15 Bài giải: Vì x3 + y 3 + z 3 − 3xyz = (x + y + z)(x2 + y 2 + z 2 − xy − yz − zx) nên (x − y)2 + (y − z)2 + (z − x)2 và x3 +y 3 +z 3 −3xyz = 2 (x + y + z)3 − 3(x + y + z)(xy + yz + zx). Theo cách viết thứ nhất, phương trình x3 +y 3 +z 3 −3xyz = (x+y +z) đã cho có nghiệm nguyên dương khi n = 3k + 1 và n = 3k + 2. Khi đó (k + 1, k, k) và (k + 1, k + 1, k), với k > 1, là nghiêm dương tương ứng. Nếu n chia hết cho 3 thì từ cách biểu diễn thứ hai, x + y + z chia hết cho 3 và như vậy n = x3 + y 3 + z 3 − 3xyz chia hết cho 9. Ngược lại, nếu n = 9k với k > 2, thì phương trình nhận nghiệm (k − 1, k, k + 1). Với n = 0, ta có nghiệm nguyên dương x = y = z ∈ N∗ . Với n = 9 phương trình không có nghiệm nguyên dương (x, y, z). 1.2.2 Phương pháp đồng dư Ví dụ 1.2.5. [Balkan MO 2013] Xác định tất cả các số nguyên dương x, y, z thỏa mãn phương trình x5 + 4y = 2013z . Bài giải: Dễ dàng kiểm tra x5 +4y ≡ 0(mod 11). Dễ dàng suy ra x5 ≡ ±1(mod 11) và như vậy 4y ≡ ±1(mod 11). Vì 4y ≡ −1(mod 11) không thỏa mãn cho mọi số nguyên dương y nên chỉ có 4y ≡ 1(mod 11) và như thế 5|y. Đặt y = 5s. Ta có x5 + 45s ≡ 0(mod 11). Đặt t = 4s . Khi đó x5 + t5 ≡ 0(mod 11) với (x, t) = 1 hay (x + t)(x4 − x3 t + x2 t2 − xt3 + t4 ) ≡ 0(mod 11). Ký hiệu A = x + t, B = x4 − x3 t + x2 t2 − xt3 + t4 . Khi đó A.B ≡ 0(mod 11). Vì B = A(x3 − −2x2 t + 3xt2 − 4t3 ) + 5t4 nên (A, B) = (A, 5t4 )|5. Vì 5 6 |2013z nên (A, B) = 1. Do vậy A = az , B = bz với các số nguyên dương a, b và a.b = 2013. Ví dụ 1.2.6. [Russia MO] Xác định tất cả các cặp số nguyên tố (p, q) thỏa mãn phương trình p3 − q 5 = (p + q)2 . Bài giải: Dễ dàng kiểm tra p > q. Nếu q = 3 thì p = 7 và ta có cặp số nguyên tố (7, 3). Nếu q > 3, xét Z3 . Khi đó p ≡ 1 hay 2(mod3), và q ≡ 1 hay 2(mod 3). Dễ dàng suy ra: Vế trái chia hết cho 3 còn vếp phải thì không. Nếu p 6≡ q(mod 3), thì vế phải chia hết cho 3, còn vế trái thì không. Trong trường hợp này, phương trình vô nghiệm. Ví dụ 1.2.7. [Balkan MO] Chứng minh rằng, phương trình x5 − y 2 = 4 không có nghiệm nguyên. 16 Bài giải: Xét vành Z11 . Dễ dàng kiểm tra (x5 )2 ≡ x10 ≡ 0 hay 1(mod 11) với mọi x ∈ Z. Do vậy x5 ≡ ±1 hay (mod 11). Từ đây suy ra x5 − 4 ≡ 6 hoặc 7 hoặc 8(mod 11). Vì thặng dư bậc hai modulo 11 chỉ có thể là 0, 1, 3, 4, 5, 9 nên phương trình đã cho không thể có nghiệm nguyên. Ví dụ 1.2.8. Tìm tất cả các số nguyên tố p, q, r thỏa mãn pq + q p = r. Bài giải: Tối thiểu phải có một số nguyên tố chẵn. Số đó phải bằng 2. Vì p, q là hai số nguyên tố nên r 6= 2. Khôn hạn chế có thể giả thiết q = 2. Vậy p2 + 2p = r. Vì r là số nguyên tố nên p phải là só lẻ. Nếu p 6= 3 thì p2 + 2p ≡ (±1)2 + (−1)p (mod 3) ≡ 1 − 1(mod 3). Vậy r chia hết cho 3, nhưng p2 + 2p = 3 chỉ thỏa mãn cho p = 1 : mâu thuẫn. Từ đây suy ra p = 3, r = 17. Ví dụ 1.2.9. Tìm tất cả các nghiệm nguyên của phương trình x3 + y 3 = z 6 + 3. Bài giải: Nếu phương trình có nghiệm trong Z thì nó cũng có nghiệm trong Z7 . Khi đó có x, y, z ∈ Z7 để x3 + y 3 = z 6 + 3. 3 3 3 3 3 3 3 Trong Z7 có 0 = 0, 1 = 1, 2 = 1, 3 = −1, 4 = −1, 5 = −1, 6 = −1. Vậy x3 hay y 3 chỉ có thể là 0 hoặc 1 hoặc −1. Qua kiểm tra ta có x3 + y 3 chỉ có thể là 0, 1, 2, −1, −2. Nhưng z 6 + 3 chỉ có thể là 0 + 3 = 3 hoặc 1 + 3 = 4. Điều này chứng tỏ phương trình vô nghiệm. Ví dụ 1.2.10. Tìm tất cả các nghiệm nguyên của phương trình sau: x2 + 4y 4 = z 6 + 6. Bài giải: Nếu phương trình có nghiệm trong Z thì nó cũng có nghiệm trong Z8 . Ta có x, y, z ∈ Z8 để x2 + 4y 4 = z 6 + 6 và những hệ thức 2 2 2 2 2 2 2 2 0 = 0, 1 = 1, 2 = 4, 3 = 1, 4 = 0, 5 = 1, 6 = 4, 7 = 1. Vậy x2 chỉ có thể là 0 hoặc 1 hoặc 4 và 4y 4 chỉ có thể là 0 hoặc 1. Qua kiểm tra ta có x3 + 4y 4 chỉ có thể là 0, 1, 2, 4, 5. Nhưng z 6 + 6 chỉ có thể là 0 + 6 = 6 hoặc 1 + 6 = 7 và suy ra phương trình vô nghiệm. 1.2.3 Phương pháp đánh giá Ví dụ 1.2.11. Giải phương trình x3 + y 3 = (x + y)2 với x, y ∈ Z.