ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
BÙI HỮU MÊN
MỘT SỐ LỚP PHƯƠNG TRÌNH DIOPHANTINE
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
BÙI HỮU MÊN
MỘT SỐ LỚP 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
GS.TSKH. ĐẶNG HÙNG THẮNG
Thái Nguyên - 2017
3
Mục lục
Danh sách kí hiệu
4
Mở đầu
5
Chương 1. Phương trình Diophantine tuyến tính
7
1.1 Phương trình bậc nhất hai ẩn . . . . . . . . . . . . . . . . . . . . . . .
8
1.2 Phương trình bậc nhất nhiều ẩn . . . . . . . . . . . . . . . . . . . . . .
15
Chương 2. Một số phương trình Diophantine phi tuyến
23
2.1 Phương trình Pell loại 1 . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.2 Phương trình Pell loại 2 . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.3 Phương trình Pythagoras . . . . . . . . . . . . . . . . . . . . . . . . .
38
Chương 3. Liên phân số và ứng dụng trong phương trình Diophantine
45
3.1 Liên phân số hữu hạn . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
3.2 Liên phân số vô hạn . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
3.3 Liên phân số vô hạn tuần hoàn . . . . . . . . . . . . . . . . . . . . . .
50
3.4 Áp dụng vào phương trình Diophante
. . . . . . . . . . . . . . . . . .
56
3.4.1
Phương trình bậc nhất hai ẩn Ax + By = C . . . . . . . . . . . .
56
3.4.2
Phương trình x2 − dy2 = ±1 . . . . . . . . . . . . . . . . . . .
57
Kết luận
62
Tài liệu tham khảo
63
4
Danh sách kí hiệu
N tập hợp các số tự nhiên
Z vành các số nguyên
Q trường các số hữu tỷ
R trường các số thực
C trường các số phức
trường có p phần tử Fp
K[X] vành đa thức với hệ số trên trường K
(cid:100)x(cid:101) trần của số x
deg P(X) bậc của đa thức P(X)
mod p modulo p
gcd(P(X), Q(X)) ước chung lớn nhất của hai đa thức P(X) và Q(X)
5
Mở đầu
Phương trình Diophantine là một chủ đề lớn của Lý thuyết số, chứa đựng nhiều lý
thuyết toán học sâu sắc, gắn liền với nhiều tên tuổi của nhiều nhà toán học xuất
sắc. Mục tiêu của đề tài luận văn là: Tìm hiểu một số lớp phương trình Diophantine
như: phương trình Diophantine tuyến tính; một số phương trình Diophantine phi
tuyến (phương trình Pell, phương trình Pell mở rộng, phương trình Pythagoras
Fermat). Liên phân số và ứng dụng trong phương trình Diophantine. Về mặt ứng
dụng, luận văn sẽ áp dụng lý thuyết để soi sáng những bài toán số học ở phổ thông,
hệ thống hóa, tổng quát hóa và sáng tác ra những bài toán số học mới.
Luận văn sẽ cố gắng trở thành một tài liệu tham khảo tốt, thiết thực phục vụ
cho việc giảng dạy, nhất là việc giảng dạy và bồi dưỡng học sinh giỏi. Ngoài ra
thông qua việc viết luận văn, tác giả luận văn có cơ hội mở rộng nâng cao hiểu biết
về toán sơ cấp nói chung và số học nói riêng, hình thành các kỹ năng chứng minh
các định lí số học và giải các bài toán số học, phục vụ tốt cho việc giảng dạy môn
Toán ở trường phổ thông.
Nội dung của luận văn được trình bày trong ba chương như sau:
• Chương 1. Phương trình Diophantine tuyến tính. Trong chương này chúng
tôi trình bày về phương trình bậc nhất hai ẩn, nhiều ẩn, và một số bài toán
chọn lọc.
• Chương 2. Một số phương trình Diophantine phi tuyến. Trong chương này
chúng tôi trình bày nội dung chính về các phương trình Pell loại 1, phương
trình Pell loại , và phương trình Pythagoras.
• Chương 3. Liên phân số và ứng dụng trong phương trình Diophantine. Trong
6
chương này chúng tôi trình bày một cách ngắn gọn các sự kiện về liên phân
số, đặc biệt là các ứng dụng của chúng để giải phương trình Pell.
Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái
Nguyên và hoàn thành với sự hướng dẫn của GS.TSKH. Đặng Hùng Thắng (Trường
ĐHKHTN - ĐHQG Hà Nội). Tác giả xin được bày tỏ lòng biết ơn chân thành và
sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu,
dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả
trong suốt quá trình làm luận văn.
Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại
học Thái Nguyên, Ban Chủ nhiệm Khoa Toán–Tin, cùng các giảng viên đã tham
gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu.
Tác giả muốn gửi những lời cảm ơn tốt đẹp nhất tới tập thể lớp Cao học Toán
khóa 9 (2015-2017) đã động viên và giúp đỡ tác giả rất nhiều trong suốt quá trình
học tập.
Nhân dịp này, tác giả cũng xin chân thành cảm ơn Sở Giáo dục và Đào tạo Hải
Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Thái Phiên đã tạo điều
kiện cho tác giả hoàn thành tốt nhiệm vụ học tập và công tác của mình.
Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến đại gia đình
vì những động viên và chia sẻ những khó khăn để tác giả hoàn thành luận văn này.
Thái Nguyên, ngày 10 tháng 11 năm 2017
Tác giả
Bùi Hữu Mên
7
Chương 1
Phương trình Diophantine tuyến tính
Phương trình Diophantine là một trong những chủ đề sâu sắc và rất rộng của Lý
thuyết số. Mục đích của chương này là nghiên cứu về phương trình Diophantine
bậc nhất hai và nhiều ẩn. Như một minh họa cho lý thuyết, các ví dụ là các bài
toán trích từ các đề thi sẽ được trình bày.
Đặc tính của các phương trình Diophantine là chúng có một hay nhiều ẩn số mà
mọi hệ số đều là số nguyên và chỉ yêu cầu tìm các nghiệm nguyên (hoặc nguyên
dương). Nhà toán học nổi tiếng thời cổ đại Diophantine đã có công lớn vì những
nghiên cứu tiên phong về chúng.
Với một phương trình Diophantine cho trước ta có thể đặt ra các câu hỏi sau
đây (xếp theo thứ tự từ dễ đến khó):
Câu hỏi 1. Nó có nghiệm nguyên hay không ?
Câu hỏi 2. Nó có một số hữu hạn nghiệm hay có vô số nghiệm?
Câu hỏi 3. Hãy tìm tất cả các nghiệm của nó.
Chẳng hạn, ta hãy xét phương trình Diophantine
xn + yn = zn
trong đó n là số nguyên dương lớn hơn hay bằng 2. Với n = 2 phương trình trên
có vô số nghiệm và ta có thể tìm được tường minh tất cả các nghiệm của nó. Với
n > 2, nhà toán học thiên tài của thế kỷ 17 Pierre de Fermat khẳng định rằng
8
phương trình trên không có nghiệm nguyên dương. Kết luận này ngày nay được
mang tên là Định lí lớn Fermat hay Định lí cuối cùng của Fermat. Người ta đã
không tìm thấy dấu vết của chứng minh khẳng định trên của Fermat mà chỉ thấy
một ghi chú của Fermat bên lề cuốn sách “Số học” của Diophantine: “Tôi đã tìm
được một chứng minh thật là tuyệt vời nhưng vì lề sách ở đây quá hẹp nên không
thể viết ra”.
Năm 1983, nhà toán học 29 tuổi người Đức là Faltings đã chứng minh thành
công một giả thuyết của Mordell trong lĩnh vực Hình học đại số rồi từ đó suy ra
rằng phương trình xn + yn = zn với n > 2 chỉ có một số hữu hạn nghiệm nguyên.
Với thành tựu này Faltings đã nhận được Giải thưởng Fields (giải thưởng quốc tế
cao nhất dành cho các nhà toán học không quá 40 tuổi).
Năm 1993 nhà toán học người Anh là Andrew Wiles đã công bố phép chứng
minh của Định lí lớn Fermat. Đây là một câu chuyện lớn của Toán học, có thể tham
khảo trong Amir D. Aczel [1].
Với sự ra đời của máy tính, người ta cũng đặt câu hỏi: Có tồn tại chăng một
thuật toán để với mọi phương trình Diophantine cho trước nhờ đó có thể khẳng
định được rằng phương trình này có nghiệm nguyên hay không. Tiếc thay câu trả
lời lại là: không có một thuật toán như vậy (Định lí Machiakevich).
1.1 Phương trình bậc nhất hai ẩn
Phương trình Diophantine đơn giản nhất là phương trình bậc nhất hai ẩn
ax + by = c (1.1)
trong đó a, b, c là những số nguyên cho trước khác 0. Vấn đề đặt ra là với điều kiện
nào của a, b, c thì phương trình (1.1) có nghiệm và nếu có thì cách tìm nghiệm thế
nào.
Định lí 1.1.1. Điều kiện cần và đủ để phương trình (1.1) có nghiệm nguyên là
9
(a, b) là ước của c.
Chứng minh. Điều kiện cần. Giả sử (x0, y0) là một nghiệm nguyên của (1.1). Khi
đó ax0 + by0 = c. Nếu d = (a, b) thì rõ ràng d | c.
Điều kiện đủ. Giả sử d = (a, b) và d | c. Ta có a = da1, b = db1, c = dc1 trong đó
(a1, b1) = 1. Phương trình (1.1) tương đương với a1x + b1y = c1.
Xét a1 số {b1k} với k = 0, 1, 2, . . . , a1 − 1. Vì (a1, b1) = 1 nên các số này khi
chia cho a1 sẽ cho ta các số dư khác nhau. Vậy tại k0, 0 ≤ k0 ≤ a1 − 1 sao cho
b1k0 = c1 (mod a1). Điều này có nghĩa là:
c1 − b1k0 = a1l0 với l0 ∈ Z hay c1 = a1l0 + b1k0.
Vậy (l0, k0) là một nghiệm của phương trình (1.1). Phép chứng minh định lí được
hoàn thành.
Tiếp theo ta hãy đi tìm tất cả các nghiệm của phương trình (1.1)
Định lí 1.1.2. Nếu (x0, y0) là một nghiệm nguyên của (1.1) thì nó có vô số nghiệm
nguyên và nghiệm nguyên (x, y) của nó được cho bởi công thức
t, x = x0 + (1.2)
t, y = y0 − b d a d
trong đó t ∈ Z và d = (a, b).
Chứng minh. Trước hết ta kiểm tra mọi cặp số (x, y) cho bởi công thức (1.2) là
nghiệm. Thật vậy
ax + by = ax0 + by0 = c.
Đảo lại, giả sử (x1, y1) là một nghiệm của (1.1) tức là ax1 + by1 = c. Trừ đẳng thức
này vào đẳng thức ax0 + by0 = c ta thu được
(1.3) a(x1 − x0) = b(y0 − y1).
10
Vì d = (a, b) nên a = a1d, b = b1d với (a1, b1) = 1. Thay vào (1.3) ta được a1(x1 −
x0) = b1(y0 − y1). Vì (a1, b1) = 1 nên y0 − y1 = ta1 và x1 − x0 = tb1. Vậy
. và y1 = y0 − ta1 = y0 − x1 = x0 + tb1 = x0 + at d bt d
Phép chứng minh được kết thúc.
Thuật toán tìm nghiệm của phương trình Diophantine bậc nhất. Từ Định lí
1.1.2 ta thấy rằng để tìm tất cả các nghiệm của (1.1) ta chỉ cần tìm một nghiệm
(x0, y0) nào đó của nó. Ta gọi một nghiệm cụ thể như thế là một nghiệm riêng còn
công thức (1.2) được gọi là nghiệm tổng quát. Sau đây ta sẽ trình bày một thuật
toán cho phép xác định khá nhanh một nghiệm riêng của (1.1).
Giả sử q0, q1, . . . là một dãy các số nguyên dương. Với mỗi i ≥ 0 ta kí hiệu
[q0, q1, . . . , qi] là phân số sau đây
1 . [q0, q1, . . . , qi] = q0 + 1 q1 + 1 q2 + · · · + 1 qi−1 + qi
Bằng phương pháp quy nạp có thể dễ dàng chứng minh được bổ đề sau:
Bổ đề 1.1.3. Giả sử {hn}, {kn} là hai dãy số nguyên được xác định như sau:
i ≥ 0, h−2 = 0, h−1 = 1, h1 = qihi−1 + hi−2,
i ≥ 2. k0 = 1, k1 = q1, ki = qihki−1 + ki−2,
Khi đó với mọi i ≥ 1 ta có:
(a) hiki−1 − hi−1ki = (−1)i−1;
. (b) [q0, q1, . . . , qi] = hi ki
11
Bây giờ cho hai số dương a, b với a > b. Ta hãy viết thuật toán Euclid tìm ước
chung lớn nhất của a và b.
a = bq0 + r1
b = r1q1 + r2
(1.4) . . .
rn−1 = rnqn−1 + rn+1
rn = rn+1qn.
Từ hệ (1.4) ta suy ra
= [q0, q1, . . . , qn] a b
Từ khẳng định (b) của Bổ đề 1.1.3 ta có
= . a b hn kn
Từ (a) ta suy ra (hn, kn) = 1. Do đó nếu (a, b) = 1 thì a = hn và b = kn. Vậy thì
akn−1 − bhn−1 = (−1)n−1.
Thành thử tồn tại x0 ∈ {kn−1} và y0 ∈ {hn−1} sao cho
ax0 + by0 = 1.
Ta thử từng trường hợp (nhiều nhất là bốn phép thử) để xác định x0, y0.
Như vậy để giải phương trình (1.1) ta sẽ tiến hành lần lượt các bước sau đây.
Bước 1. Tìm d = (a, b) sau đó chia hai vế cho d để được một phương trình tương
đương a1x + b1y = c1 , ở đó
a = da1, b = db1, c = dc1, (a1, b1) = 1.
Bước 2. Viết thuật toán Euclid cho hai số |a1| và |b1|. Giả sử |a1| > |b1|.
|a1| = |b1|q0 + r1
12
|b1| = r1q1 + r2
. . .
rn−1 = rnqn−1 + rn+1
rn = rn+1qn.
Bước 3. Tính [q0, q1, . . . , qn−1] = h k .
0) của phương trình a1x + b1y = 1 thoả mãn điều
Bước 4. Lấy nghiệm riêng (x(cid:48)
0, y(cid:48) 0| = h.
0| = k, |y(cid:48)
kiện |x(cid:48)
0 bằng cách thử.
0 và y(cid:48)
Ta xác định dấu của x(cid:48)
0, y0 = c1y(cid:48)
0 là nghiệm riêng của phương trình (1.1). Khi
Bước 5. Ta có x0 = c1x(cid:48)
đó nghiệm tổng quát là
với t ∈ Z. x = x0 + b1t, y = y0 + a1t,
Ví dụ 1.1.4. Giải phương trình Diophantine 342x − 123y = 15.
Lời giải. Ta sẽ làm lần lượt theo các bước như trên.
Bước 1. Ứớc chung lớn nhất của 342 và 123 là 3. phương trình đã cho tương đương
với 114x − 41y = 5.
Bước 2. Ta viết thuật toán Euclid cho 114 và 41.
114 = 41 · 2 + 32
41 = 32 · 1 + 9
32 = 9 · 3 + 5
9 = 5 · 1 + 4
5 = 4 · 1 + 1
4 = 1 · 4.
13
Bước 3. Ta biểu diễn theo liên phân số
1 = . = 2 + h k 25 9 1 1 +
1 3 +
1 1 + 1
0 của phương trình 114x − 41y = 1 thoả mãn điều
Như vậy h = 25, k = 9.
0 = 25.
0 = 9, y(cid:48)
0, y(cid:48) 0| = 25. Bằng cách thử ta tìm được x(cid:48)
kiện |x(cid:48) Bước 4. Lấy nghiệm riêng x(cid:48) 0| = 9 và |y(cid:48)
Bước 5. Nghiệm riêng x0, y0 của phương trình đã cho là x0 = 9 · 5 = 45, y0 =
25 · 5 = 125 và nghiệm tổng quát là
x = 45 + 41t, y = 125 + 114t, với t ∈ Z.
Nhận xét 1.1.5.
1. Nếu a | c ta có thể lấy nghiệm riêng
, x0 = y0 = 0. c a
2. Xét trường hợp (a, b) = 1. Theo Định lí Euler ta có
aϕ(b) − 1 = kb với k ∈ Z.
Vậy caϕ(b) − bkc = c. Do đó
x0 = caϕ(b) − 1, y0 = −kc
là một nghiệm riêng của phương trình đang xét.
14
Một số bài toán chọn lọc
Bài toán 1.1.6. Cho hai số nguyên dương a, b. Chứng minh rằng (a, b) = 1 khi và
chỉ khi tồn tại các số nguyên dương u, v sao cho au − bv = 1.
Lời giải. Điều kiện đủ là hiển nhiên.
Đảo lại, giả sử (a, b) = 1. Theo Định lí 1.1.1, tồn tại các số nguyên x0, y0 để
cho ax0 + by0 = 1. Đặt
u = x0 + bt,
v = at − y0,
trong đó t ∈ Z được chọn sao cho
t > , . t > − x0 b y0 b
Khi đó u và v là các số nguyên dương và au − bv = ax0 + by0 = 1.
Bài toán 1.1.7. Giả sử (l, m) = 1 và al = bm, trong đó a, b, l, m ∈ N∗. Khi đó tồn
tại n để a = nm, b = nl.
Lời giải. Theo Bài toán 1.1.6 tồn tại các số r, s ∈ N∗ để lr − ms = 1. Ta có
(cid:19)m . a = alr−ms = alr ams = (cid:18)br as
as ∈ N∗. Suy ra a = nm. Từ đó bm = nl = nml, nên b = nl. Bài toán được chứng minh xong.
a = br bmr ams = a là một số hữu tỉ nên nó phải là số nguyên. Vậy n = br √ Suy ra m √ as . Vì m
Bài toán 1.1.8. Cho a ∈ N∗. Hãy tìm g = (am − 1, an − 1).
Lời giải. Trước hết xét trường hợp (m, n) = 1. Vì
(a − 1) | am − 1, (a − 1)an − 1
nên a − 1 là ước của g.
Đảo lại, ta sẽ chứng minh g cũng là ước của a − 1. Theo Bài toán 1.1.6 tồn tại
các số u, v ∈ N∗ sao cho mu − nv = 1.
15
Vì g | am − 1, g | an − 1 nên cũng có g | amu − 1, g | anv − 1. Suy ra
g | amu − anv = anv(amu−nv − 1) = anv(a − 1).
Mặt khác, dễ thấy (g, a) = 1. Vậy g | (a − 1).
Như vậy nếu (m, n) = 1 thì (am − 1, an − 1) = a − 1.
Với m, n bất kì, giả sử d = (m, n). Khi ấy m = dm1, n = dn1 và (m1, n1) = 1.
Ta có
(am − 1, an − 1) = ((ad)m1 − 1, (ad)n1 − 1) = ad − 1.
Tóm lại ta có công thức
(am − 1, an − 1) = a(m, n) − 1.
Bài toán 1.1.9. Cho (a, b) = 1 trong đó a, b ∈ N∗. Tìm giá trị c ∈ N∗ lớn nhất để
phương trình ax + by = c không có nghiệm nguyên dương.
Lời giải. Ta chứng minh rằng c = ab là giá trị cần tìm. Giả sử c > ab. Xét b số
a, 2a, . . . , ba. Vì (a, b) = 1 nên các số này khi chia cho b sẽ cho các số dư khác
nhau. Vậy tồn tại số k, 1 ≤ k ≤ b, sao cho ka ≡ c (mod b). Suy ra c − ka = lb trong đó l ∈ Z. Nếu c > ab thì c > ka, do đó lb > 0 hay l ∈ N∗. Như vậy (k, l) là nghiệm
nguyên dương của phương trình ax + by = c.
Mặt khác, giả sử (x0, y0) là nghiệm nguyên dương của phương trình ax + by =
ab. Khi đó ax0 = ab − by0 = b(a − y0).
Vì (a, b) = 1 nên từ đó suy ra x0 ... b. Tương tự, y0 ... a. Như vậy x0 ≥ b, y0 ≥ a,
do đó ab = ax0 + by0 ≥ 2ab. Vô lý. Phép chứng minh được kết thúc.
1.2 Phương trình bậc nhất nhiều ẩn
Trong mục này ta mở rộng kết quả của mục trước bằng cách xét phương trình
Diophantine bậc nhất n ẩn
(1.5) a1x1 + a2x2 + . . . + anxn = c.
16
trong đó a1, a2, . . . , an và c là các số nguyên cho trước, n ≥ 2.
Đối với bất kỳ một phương trình nào, câu hỏi đầu tiên là, trong những tình
huống nào của hệ số, ta có thể khẳng định về tính tồn tại nghiệm của nó. Về sự tồn
tại nghiệm của phương trình Diophantine bậc nhất n ẩn này ta có định lí sau đây.
Định lí 1.2.1. Điều kiện cần và đủ để phương trình (1.5) có nghiệm là
(a1, a2, . . . , an) | c.
Chứng minh. Điều kiện cần là hiển nhiên. Ta sẽ chứng minh điều kiện đủ bằng
phương pháp quy nạp, với n = 1 điều khẳng định là đúng do Định lí 1.1.1. Giả sử
định lí đúng với n = 1, ta chứng minh nó đúng với n. Kí hiệu
, , bi = c1 = ở đó d = (a1, a2, . . . , an). ai d c d
Phương trình (1.5) tương đương với
(1.6) b1x1 + b2x2 + . . . + bnxn = c1.
trong đó (b1, b2, . . . , bn) = 1. Đặt b = (b1, b2, . . . , bn−1). Ta có (b, bn) = 1. Theo
Định lí 1.1.1 tồn tại số nguyên ln và k sao cho:
(1.7) bnln + bk = c1.
i = bi
1, b(cid:48)
2, . . . s, b(cid:48)
n−1) = 1.
b với i = 1, 2, . . . , n − 1. Ta có (b(cid:48)
Kí hiệu b(cid:48)
1l1 + b(cid:48) b(cid:48)
2l2 + . . . + b(cid:48)
n−1ln−1 = k
Theo giả thiết quy nạp tồn tại các số nguyên l1, l2, . . . , ln−1 sao cho
hay
(1.8) b1l1 + b2l2 + . . . + bn−1ln−1 = bk.
Từ (1.7) và (1.8) ta suy ra
b1l1 + b2l2 + . . . + bn−1ln−1 + bnln = c1
tức là (l1, l2, . . . , ln) là nghiệm của phương trình (1.6). Định lí được chứng minh.
17
Chúng ta không đi sâu vào việc tìm biểu thức cho nghiệm tổng quát của nó
như đã làm đối với trường hợp n = 2. Tuy nhiên có thể thấy rằng nếu phương trình
(1.5) có nghiệm nguyên α1, α2, . . . , αn thì nó sẽ có vô số nghiệm nguyên phụ thuộc
vào n − 1 tham số. Thật vậy, dễ dàng kiểm tra được tất cả các bộ n số nguyên
x1, x2, . . . , xn xác định như sau là nghiệm của (1.5),
x1 = α1 + ant1
x2 + α2 + ant2
. . .
xn−1 = αn−1 + antn−1
xn = αn − a1t1 − a2t2 . . . − an−1tn−1
trong đó ti ∈ Z, i = 1, 2, . . . n − 1 được chọn tuỳ ý.
Bây giờ, ta sẽ thảo luận về cách giải phương trình (1.5). Về mặt thực hành ta
có thể tiến hành theo hai cách sau đây.
Cách 1. Đưa (1.5) về trường hợp có một hệ số bằng 1.
Cách 2. Nếu phương trình (1.5) có hai hệ số nguyên tố cùng nhau, chẳng hạn
(a1, a2) = 1 thì ta viết dưới dạng
a1x1 + a2x2 = c − a3x3 − . . . − anxn
rồi giải phương trình theo hai ẩn x1, x2.
Ta xét hai ví dụ sau đây, nó sẽ lần lượt minh họa cho hai cách trên.
Ví dụ 1.2.2. Tìm tất cả các nghiệm nguyên của phương trình
6x + 45y + 6z − 10t = 13.
Lời giải. Phương trình đã cho được viết dưới dạng
6(x + z) + 10(4y − t) + 5y = 13.
18
Đặt
x + z = x1, 4y − t = x2
ta được 6x1 + 10x2 + 5y = 13. Suy ra
x1 + 10x2 + 5(y + x1) = 13.
Đặt x1 + y = x3 ta được x1 + 10x2 + 5x3 = 13. Vậy
x1 = 13 − 10x2 − 5x3.
Từ đây, bằng tính toán trực tiếp ta có
y = x3 − x1 = x3 − (13 − 10x2 − 5x3) = 10x2 + 6x3 − 13;
t = 4y − x2 = 39x2 + 24x3 − 52;
x = x1 − z = 13 − 10x2 − 5x3 − z.
Vậy nghiệm tổng quát của phương trình đã cho là
x = 13 − 10x2 − 5x3 − x4,
y = 10x2 + 6x3 − 13,
z = x4,
t = 39x2 + 24x3 − 52.
trong đó x2, x3, x4 là các số nguyên tuỳ ý.
Ví dụ 1.2.3. Giải phương trình
6x + 15y + 10z = 3. (1.9)
Lời giải. Ta có thể viết (1.9) dưới dạng
6(x + z) + 15y = 3 − 4z.
Đặt u = x + z ta có 15y + 4z = 3 − 6u. Ta thấy (−1, 4) là nghiệm riêng của 15y +
4z = 1. Do đó (−3 + 6u, 12 − 24u) là nghiệm riêng của 15y + 4z = 3 − 6u. Suy ra
nghiệm tổng quát của nó là
y = −3 + 6u + 4t, z = 12 − 24u − 15t.
19
Từ u = x + z suy ra
x = u − z = u − (12 − 24u − 15t) = −12 + 25u + 15t.
Vậy nghiệm tổng quát của (1.9) là
x = −12 + 25u + 15t,
y = −3 + 6u + 4t,
z = 12 − 24u − 15,
với u, t ∈ Z.
Một số bài toán chọn lọc
Bài toán 1.2.4 (Đề thi Vô định Toán Quốc tế 1983). Cho a, b, c là các số nguyên
đôi một nguyên tố cùng nhau. Chứng minh rằng 2abc − ab − bc − ca là số nguyên
lớn nhất không viết được dưới dạng xbc + yca + zab với x, y, z là những số không
âm.
Lời giải. Bài toán tương đương với việc chứng minh rằng
Khẳng định 1. phương trình xbc + yca + zab = 2abc − ab − bc − ca không có
nghiệm nguyên không âm;
Khẳng định 2. Nếu n > 2b − ab − bc − ca thì phương trình có nghiệm nguyên
không âm.
Chứng minh Khẳng định 1. Giả sử tồn tại x0, y0, z0 ∈ N∗ sao cho
x0bc + y0ca + z0ab = 2abc − ab − bc − ca.
Điều này tương đương với
bc(x0 + 1) + ca(y0 + 1) + ab(z0 + 1) = 2abc.
20
Suy ra ab(z0 + 1) ... c. Mặt khác z0 + 1 ∈ N∗ nên
... c. Vì (ab, c) = 1 nên z0 + 1 z0 + 1 ≥ c. Tương tự y0 + 1 ≥ b, x0 + 1 ≥ a. Vậy
bc(x0 + 1) + ca(y0 + 1) + ab(z0 + 1) ≥ 3abc.
Điều này vô lí.
Chứng minh Khẳng định 2. Xét ab có dạng kbc + lac, với 0 ≤ k ≤ a − 1, 0 ≤ l ≤
b − 1..
Các số này khi chia cho ab sẽ cho ta các số dư khác nhau. Thật vậy, giả sử
k1bc + l1ac ≡ k2bc + l2ac (mod ab).
Vì (ab, c) = 1 nên suy ra b(k1 − k2) − a(l1 − l2) ... ab. Từ đó b(k1 − k2)
... b. Vì (a, b) = 1 nên k1 − k2 ... a và l1 − l2
... a và a(l1 − ... b. Mặt khác |k1 − k2| < a, |l1 − l2| < b l2) nên l1 −l2 = 0, k1 −k2 = 0. Do đó tồn tại x0, y0 ∈ Z+, 0 ≤ x0 ≤ a−1, 0 ≤ y0 ≤ b−1
để cho
bcx0 + acy0 ≡ n (mod ab).
Vậy tồn tại z0 ∈ Z để bcx0 + acy0 + abz0 = n. Ta có
ab(z0 + 1) = n − bcx0 − acy0 + ab
> 2abc − bcx0 − acy0 − bc − ca
= bc(a − 1 − x0) + ac(b − 1 − y0) ≥ 0.
Do đó z0 + 1 > 0. Suy ra z0 ≥ 0.
Bài toán 1.2.5. Cho các số nguyên không âm a, b thoả mãn điều kiện 5a ≥ 7b.
Chứng minh rằng hệ
x + 2y + 3z + 7u = a,
y + 2z + 5u = b
luôn có nghiệm nguyên không âm.
5 suy ra
21
5
Chứng minh. Giả sử b = 5u + v với 0 ≤ u, 0 ≤ v ≤ 4. Từ điều kiện a ≥ 7b a ≥ 7(5u+v) . Từ đây ta có
. a − 7u ≥ (1.10) 7v 5
Như vậy hệ phương trình có thể viết là
(cid:110) (1.11) x + 2y + 3z = a − yu y + 2z = b − 5u = v.
Với mỗi 0 ≤ v ≤ 4 ta sẽ chọn y, z thích hợp để có x = z − 7u − 2y − 3z ≥ 0.
5 = 0 (theo (1.10))).
• Nếu v = 0, ta lấy y = z = 0. Khi đó x = a − 7u ≥ 7v
• Nếu v = 1, ta thấy y = 1, z = 0. Khi đó
− 2 = − 2 > −1. x = a − yu − 2 ≥ 7v 5 7 5
Vậy x ≥ 0.
• Nếu v = 2, ta lấy y = 0, z = 1. Khi đó
x = a − 7u − 3 ≥ − 3 = − 3 > −1. 7v 5 14 5
Vậy x ≥ 0.
• Nếu v = 3, ta lấy y = z = 1. Khi đó
x = a − 7u − 5 ≥ − 5 = − 5 > −1. 7v 5 21 5
Vậy x ≥ 0.
• Nếu v = 4, ta lấy y = 0, z = 2. Khi đó
− 6 = − 6 > −1. x = a − 7u − 6 ≥ 7v 5 28 5
Vậy x ≥ 0.
Tóm lại với mọi v = 0, 1, 2, 3, 4 ta đều chọn được y, z, x không âm để (1.11) được
nghiệm đúng. Bài toán được giải xong.
22
Bài toán 1.2.6 (Đề thi vô địch Mỹ 1982). Chứng minh rằng tồn tại số tự nhiên k
sao cho tất cả các số kn + 1 với n = 1, 2, . . . đều là hợp số.
+ 1. Lời giải. Xét các số Fermat Fm = 22m
Ta đã biết Fm là số nguyên tố với m = 0, 1, 2, 3, 4, trong khi Euler phát hiệu
rằng F5 là một hợp số, F5 là tích của hai số nguyên tố 641 và 6700417.
Ký hiệu
với i = 0, 1, 2, 3, 4, ai = Fi
a5 = 641a6 = 6700417.
Theo Định lí Trung Hoa về thặng dư, tồn tại số tự nhiên k > max(a0, . . . , a6) để
k ≡ 1 (mod am) với m = 0, 1, 2, . . . , 5 và k ≡ −1 (mod a6).
Ta sẽ chứng minh k chính là số cần tìm. Xét n bất kỳ, n có thể viết dưới dạng
n = 2m p với 0 ≤ m và p lẻ.
p + 1 = (22m )p + 1 + 1 = am. Do đó k · 2n + 1 ... am.
(a) Nếu m ≤ 4, ta có k · 2n + 1 ≡ 2n + 1 (mod am). ... 22m Mặt khác 2n + 1 = 22m Vì k · 2n + 1 > k > am nên k · 2n + 1 là hợp số.
+ 1 ... 641 = a5. Vậy k · 2n + 1 ... a5. Mặt
(b) Nếu m = 5 thì k · 2n + 1 ≡ 2n + 1 (mod a5). 225(cid:17)p (cid:16) ... 225 + 1 = F5 Mặt khác 2n + 1 = khác k · 2n + 1 > a5, suy ra k · 2n + 1 là hợp số.
(c) Nếu m ≥ 6, khi đó n = 26b với b ∈ Z. Ta có
k · 2n + 1 ≡ −2n + 1 (mod a6),
2n = 225(cid:17)2b (cid:16) = (F5 − 1)2b ≡ (−1)2b ≡ 1 (mod a6) vì F5 ... a6.
Do đó k · 2n + 1 ≡ −1 + 1 = 0 (mod a6). Vì k · 2n + 1 > a6 nên k · 2n + 1 là hợp
số.
Vậy với mọi n, số k · 2n + 1 luôn là hợp số.
23
Chương 2
Một số phương trình Diophantine phi tuyến
2.1 Phương trình Pell loại 1
Phương trình Pell loại 1 là phương trình có dạng
x2 − Dy2 = 1, (2.1)
trong đó D ∈ N∗ và ta yêu cầu tìm nghiệm x, y ∈ N∗ . Trong tiết này khi nói đến
nghiệm của (2.1) ta hiểu là nghiệm nguyên dương.
Định lí 2.1.1 (Điều kiện tồn tại nghiệm). Phương trình (2.1) có nghiệm nguyên
dương khi và chỉ khi D là số không chính phương.
Chứng minh. Giả sử D = m2. Khi đó
x2−Dy2 = x2 − m2y2 = 1 → (x − my)(x + my) = 1
→ x − my = x + my = 1 → x = 1, y = 0.
Vậy (2.1) không có nghiệm nguyên dương.
Ngược lại giả sử D là số không chính phương. Ta có các bổ đề sau
Bổ đề 2.1.2. Cho α /∈ Q. Khi đó tồn tại vô số cặp nguyên (h, k) với k > 0 sao cho
< h k 1 k2 . (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) α − (cid:12) (cid:12)
24
Chứng minh. Ta sử dụng nhận xét đã biết sau: Với mỗi q ∈ N∗ tồn tại cặp số
< . h k 1 kq nguyên (h, k) với 1 ≤ k ≤ q sao cho (cid:12) (cid:12) α − (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
Ký hiệu (cid:26) (cid:27) < A = . (h, k) : 1 k2 h k (cid:12) (cid:12) (cid:12) (cid:12)
> ε với mọi (h, k) ∈ A. Chọn q ∈ N∗ sao cho h k (cid:12) (cid:12) α − (cid:12) (cid:12) Ta phải chứng minh |A| = ∞. Giả sử trái lại |A| < ∞. Khi đó tồn tại ε sao cho (cid:12) (cid:12) α − (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
(2.2) < ε. 1 q
Theo nhận xét trên tồn tại cặp số nguyên (h0, k0) với 1 ≤ q sao cho
< ≤ . (2.3) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) α − (cid:12) (cid:12) 1 k0q 1 k2 0
≥ > > ε. Nhưng > ε. Mâu Từ (2.3) ta có (h0, k0) ∈ A → 1 q (cid:12) (cid:12) α − (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) α − (cid:12) (cid:12) h0 k0 (cid:12) (cid:12) (cid:12) (cid:12) 1 k0q h0 k0 h0 k0 thuẫn với (2.2).
Bổ đề 2.1.3. Tồn tại vô số cặp số nguyên dương (x, y) sao cho
√ D. |x2 − Dy2| < 1 + 2
D − < 0 < 1 y2 . x y Chứng minh. Theo Bổ đề 2.1.2 tồn tại vô số cặp số nguyên (x, y) sao cho (cid:12) √ (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
Suy ra √ √ √ √ D D + = − < D. D + 2 x y x y 1 y2 + 2 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
Vậy
√ √ √ √ D D − + |x2 − Dy2| =|x − y D||x + y D| = y2 x y x y (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) √ √ D) = D. D < 1 + 2 √ 1 y2 + 2 < y2 1 y2 ( 1 y2 + 2
25
Chứng minh định lý Từ bổ đề 2.1.3 (x, y) tồn tại vô số cặp số nguyên dương
(x, y) sao cho √ D. |x2 − Dy2| < 1 + 2
√ √ d; 1 + 2 Đặt I = [−1 − 2 d]. Với mỗi k ∈ I ký hiệu
Ak = {(x, y) ∈ N∗ : x2 − Dy2 = k}
Do đó tồn tại k ∈ I để |Ak| = ∞. Suy ra tồn tại (x1, y1) (cid:54)= (x1, y1) ∈ Ak để
1 − Dy2 x2
1 = x2
2 − Dy2
2 = k,
(mod |k|) (mod |k|), x1 ≡ x2 y1 ≡ y2
Xét tích
√ √ √ (2.4) (x1 − y1 D)(x2 + y2 D)x1x2 − Dy1y2 + D(x1y2 − x2y1)
Vì
1 − Dy2
1 ≡ 0 (mod |k|)
x1x2 − Dy1y2 ≡ x2
x1y2 − x2y1 ≡ x1y1 − x1y1 ≡ 0 (mod |k|).
Vậy tồn tại u, v ∈ Z sao cho
(2.5) x1x2 − Dy1y2 = ku
(2.6) x1y2 − Dy1x2 = kv
Từ (2.4), (2.5), (2.6) suy ra
1 − dy2
1 =
√ √ D), (x1 − y1 D)(x2 + y2) = k(u + v √ √ D) = k(u − v D). (x1 + y1)(x2 − y2
2 = k ta được
Nhân hai đẳng thức trên với nhau và chú ý rằng (x1, y1, (x2, y2) ∈ Ak → x2 x2 2 − dy2
k2 = k2(u2 − Dv2) → u2 − Dv2 = 1.
26
1) = ±(x1 − y1
1 − Dy2
Ta chứng minh u, v > 0. Rõ ràng u > 0. Nếu trái lại v = 0 thì u = ±1 → (x1 − √ √ √ √ D)(x2 + y2 D)(x1 + y1 D) → x2 + y1 D) = ±k = ±(x2 √ √ D = x1 + y1 D → x1 = x2, y1 = y2. Ta có mâu thuẫn. Vậy (u, v) là nghiệm y2
nguyên dương của phương trình (2.1).
Định lí 2.1.4 (Công thức nghiệm). Ký hiệu (a, b) là nghiệm nhỏ nhất của phương
trình
x2 − Dy2 = 1.
Khi đó dãy (xn, yn) cho bởi
√ √ D)n (a + b , xn = √ √ (a + b D)n . yn = D)n + (a − b 2 D)n − (a − b √ D 2
cho tất cả các nghiệm của (2.2)
Dãy nghiệm (xn, yn) cũng có thể xác định theo công thức truy hồi sau
(2.7) x0 = 1, x1 = a, xn+2 = 2axn+1 − xn,
(2.8) y0 = 0, y1 = b, yn+2 = 2ayn+1 − yn.
Chứng minh. Ta có
√ √ √ D = (a + b d)n. (2.9) d)n, xn − yn = (a − b xn + yn
n − Dy2
n) = (a2 − Db2)n = 1.
Suy ra (x2
Đảo lại giả sử (x, y) là nghiệm bất kỳ của (2.1). Ta chứng minh tồn tại n ∈ N∗
để x = xn; y = yn. Vì D không chính phương nên điều này tương đương Tồn tại n ∈ N∗ để √ √ √ D = (a + b D)n. x + y D = xn + yn
Chứng minh bằng phản ứng. Giả sử trái lại
√ √ x + y D (cid:54)= (a + b D)n∀n ∈ N∗.
27
Khi đó tồn tại m ∈ N∗ sao cho
√ √ √ (a + b D)m < x + y D < (a + b D)m+1.
√ D)m ta được Nhân hai vế với (a − b
√ √ √ D)(a − b D)m < a + b D. 1 < (x + y
Do (2.9) ta có
√ √ √ √ (x + y D)(a − b D)m = (x + y D) D)(xm − ym √ D = (xxm − Dyym) + (xmy − ymx) √ = u + v D,
ở đó u = xxm − Dyym, v = xmy − ymx. Vậy
√ √ d < a + b d. 1 < u + v (2.10)
Ta có
u2 − Dv2 = (xxm − Dyym)2 − D(xmy − ymx)2,
m − Dy2
m) = 1.
= (x2 − Dy2)(x2
√ √ √ √ D)(u + v d nên u > 0. Lại có (u − v D) = 1 và 1 < Lại có x > y √ d, xm > ym √ √ u + v d < 1 < u + v d nên 0 < u − v √ d → v > 0. Vậy (u, v) là nghiệm của (2.1) √ d ≤ u + v do đó a ≤ u, b ≤ u → a + b d trái với (2.10). Định lý được chứng
minh.
Từ định lý trên ta thấy việc tìm nghiệm của phương trình Pell (2.1) quy về tìm
nghiệm nhỏ nhất (a, b) của nó. Cách đơn giản nhất là thử bằng tay: Thay lần lượt
y = 1, 2, . . . vào biểu thức 1 + Dy2 cho tới khi nào được số chính phương thì dừng
lại. Vì phương trình (2.1) có nghiệm nên chắc chắn quá trình này sẽ dừng lại sau √ 1 + Db2 . Nếu nghiệm nhỏ b phép thử. Khi đó nghiệm nhỏ nhất là (a, b) với a =
28
nhất b này lớn thì cách thử này không khả thi. Thí dụ với phương trình x2 − 61y2
thì cặp nghiệm nhỏ nhất là
a = 1766319049, b = 226153980.
Sau đây ta sẽ trình bày một thuật toán sử dụng liên phân số để tìm một nghiệm nhỏ
nhất (a, b) của (2.1).
Định nghĩa 2.1.5. Cho a0, a1, a2, . . . là dãy số nguyên trong đó ai > 0, i ≥ 1. Đặt
Ck = [a0; a1, . . . , ak].
Khi đó tồn tại giới hạn
limCk = α.
Ta gọi α là giá trị của liên phân số vô hạn [a0, a1, a2, . . .]và viết
α = [a0, a1, a2, . . .].
Định lí 2.1.6. α = [a1, a1, a2, . . .] là một số vô tỷ. Ngược lại mỗi số vô tỷ đều biểu
diễn duy nhất dưới dạng một liên phân số vô hạn.
Định nghĩa 2.1.7. Ta gọi liên phân số vô hạn α = [a1; a1, a2, . . .] là tuần hoàn nếu
dãy (an) tuần hoàn kể từ một chỉ số nào đó tức là: Tồn tại các số nguyên dương m
và k sao cho mọi n ≥ m ta có an = am+k. Số nguyên dương k được gọi là chu kỳ
của liên phân số α = [a0; a1, a2, . . .]. Khi đó ta viết
α = [a0; a1, a2, . . . , am−1, am, am+1, . . . , am+k−1].
√ Nếu D là số không chính phương, biểu diễn liên phân số của D được cho bởi
√ D là tuần hoàn và có dạng Định lí 2.1.8. Biểu diễn liên phân số của
√ D = [a; a1, a2, . . . , an, 2a].
√ với a = [ D]. Hơn nữa có công thức tường minh để xác định dãy (a1, . . . , an). Chú
ý rằng dãy (a1, . . . , an) là đối xứng tức là
a1 = an, a2 = an−1, . . .
29
Ví dụ 2.1.9.
√ 23 = [4; 1, 3, 1, 8] √ 29 = [5; 2, 1, 1, 2, 10] √ 31 = [5; 1, 1, 3, 5, 3, 1, 1, 10] √ 46 = [6; 1, 2, 1, 1, 2, 6, 2, 1, 1, 2, 1, 12] √ 76 = [8; 1, 2, 1, 1, 5, 4, 5, 1, 1, 2, 1, 16] √ 97 = [9; 1, 5, 1, 1, 1, 1, 1, 1, 5, 1, 18].
Định lí 2.1.10. Cho phương trình Pell
x2 − Dy2 = 1. (I)
√ 1. Biểu diễn D thành liên phân số
√ D = [a; a1, a2, . . . , an, 2a].
2. Nếu chu kỳ n là số chẵn ta tính giản phân thứ n − 1
. Cn−1 = pn−1 qn−1
3. Khi đó (pn−1, qn−1) là nghiệm nhỏ nhất của (2.1)
4. Nếu chu kỳ n là số lẻ ta tính giản phân thứ 2n − 1
. C2n−1 = p2n−1 q2n−1
5. Khi đó (p2n−1, q2n−1) là nghiệm nhỏ nhất của (2.1)
√ 14 = Ví dụ 2.1.11. Tìm nghiệm nhỏ nhất của phương trình x2 − 14y2 = 1. Ta có
[3; 1, 2, 1, 6]. Chu kỳ n = 4 là số chẵn. Vậy ta tính giản phân
1 C3 = [3, 1, 2, 1] = 3 + 1 1 +
2 + 1 1
30
= . 15 4
Vậy nghiệm nhỏ nhất là (15, 4).
√ 13 = Ví dụ 2.1.12. Tìm nghiệm nhỏ nhất của phương trình x2 − 13y2 = 1. Ta có
[3; 1, 1, 1, 1, 6] = [3, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, . . . Chu kỳ n = 5 là số lẻ. Vậy ta tính giải
phân
1 = . C9 = [3, 1, 1, 1, 1, 6, 1, 1, 1] = 3 + 649 180 1 + 1 1 . . . + 1 +
1 + 1 1
Vậy nghiệm nhỏ nhất là (649, 180) Trở lại phương trình x2 − 61y2 = 1. Ta có
√ 76 = [7; 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14]
Chu kỳ n = 11 là số lẻ. Ta tính giản phân
C21 = [7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1]
1 = 7 + 1 1 +
4 + 1 1 . . . + 3 +
4 + 1 1
= 1766319049 226153980
Vậy nghiệm nhỏ nhất là (1766319049, 226153980)
2.2 Phương trình Pell loại 2
Phương trình Pell loại 2 là phương trình
x2 − Dy2 = −1 (2.11)
ở đó D ∈ N∗ . Nghiệm của (2.11) luôn được hiểu là nghiệm nguyên dương.
31
Định lí 2.2.1. Điều kiện cần để (2.11) có nghiệm là D không là số chính phương
và D không có ước nguyên tố dạng 4k + 3.
Chứng minh. i) nếu D = m2 thì (2.11) trở thành (my − x)(my + x) = 1 → my −
x = my + x = 1 → x = 0 vậy (2.11) vô nghiệm.
ii) Nếu D có ước nguyên tố p = 4k + 3 : Giả sử (x, y) là nghiệm. Khi đó x2 + 1 =
Dy2 → p|x2 + 1. Vì p = 4k + 3 nên p|1. Mâu thuẫn.
Tuy nhiên, đây không là điều kiện đủ.
Định lí 2.2.2. Nếu D = p là số nguyên tố thì (2.11) có nghiệm khi và chỉ khi p = 2
hoặc p (cid:54)= 4k + 3.
Chứng minh. Nếu (2.11) có nghiệm thì từ Định lý 1 suy ra p = 2 hoặc p (cid:54)= 4k + 3.
Đảo lại nếu p = 2 thì phương trình x2 = −2y2 = −1 có nghiệm (x, y) = (1; 1). Xét
p ≡ 1( mod 4). Xét phương trình Pell loại I
x2 − Dy2 = 1 (2.12)
Gọi (a, b) là nghiệm nhỏ nhất của (2.12). Ta có a2 − 1 = pb2. Nếu a chẵn thì b lẻ
do đó b2 ≡ 1( mod 4) → a2 ≡ 1 + p ≡ 2( mod 4). Mâu thuẫn. Vậy a lẻ, b chẵn.
Đặt a = 2a1 + 1, b = 2b1. Ta có (a − 1)(a + 1) = pb2 ⇔ a1(a1 + 1) = pb2 1. Do p nguyên tố và (a1, a1 + 1) = 1 nên a1 = u2, a1 + 1 = pv2 hoặc a1 = pu2, a1 + 1 = v2. Nếu a1 = u2, a1 + 1 = pv2 → u2 − pv2 = −1. Vậy (2.11) có nghiệm (u, v). Nếu a1 = pu2, a1 + 1 = v2 → v2 − pu2 = 1. Vậy (v, u) là nghiệm của (2.12). Suy ra u ≥ a → a1 + 1 = v2 ≥ v ≥ a = 2a1 + 1. Mâu thuẫn.
Định lí 2.2.3. Gọi (a, b) là nghiệm nhỏ nhất của (2.12). Khi đó (2.11) có nghiệm
khi và chỉ khi
a = x2 + Dy2 (2.13)
b = 2xy
32
có nghiệm nguyên dương.
Hơn nữa nếu (2.13) hệ có nghiệm nó sẽ có nghiệm duy nhất. Nghiệm duy nhất
(x1, y1) này chính là nghiệm nhỏ nhất của (2.11).
Chứng minh. 1) Giả sử (2.11) có nghiệm. Gọi (x1, y1) là nghiệm nhỏ nhất của
1 +Dy2
(2.11). Đặt u = x2
1, v = 2x1, y1. Ta chứng minh u = a, v = b do đó (x1, y1) 1)2 = 1. Vậy (u, v) là
1 − Dy2
chính là nghiệm của (2.13). Ta có u2 − Dv2 = (x2
nghiệm của (2.12). Suy ra u ≥ a; v ≥ b. Ta có
1) = 1(−1) = −1 ⇔(ax1 − Dby1)2 − D(ay1 − bx1)2 = −1.
(a2 − Db2)(x1 − Dy2
Dễ thấy (ax1 − Dby1)2 > 0, (ay1 − bx1)2 > 0. Do (x1, y1) là nghiệm của
(2.11) nên
1 − x2
1 ≥ 2abDx1y1
(ax1 − Dby1)2 ≥ x2
1 ≥ 2abDx1y1
→ x2
1 ≥ 2abDx1y1
→ x2
1 + D2b2y2 1 ⇔ a2x2 1(a2 − 1) + D2b2y2 1Db2 + D2b2y2 1 + dy2
1) ≥ 2ax1y1 → bu ≥ av
→ b(x2
→ b2u2 ≥ a2v2 → b2(Dv2 + 1) ≥ v2(Db2 + 1)
→ b ≥ v → b = v → u = a.
2) Đảo lại giả sử (u, v) là nghiệm của (2.13). Ta có a2 −Db2 = 1 ⇔ (u2 +Dv2)2 −
D(2uv)2 = (u2 − Dv2)2 = 1. Vậy u2 − Dv2 = 1 hoặc u2 − Dv2 = −1. Nếu
u2 − Dv2 = 1 thì (u, v) là nghiệm của (2.12) do đó u ≥ a = u2 + Dv2. Mâu
thuẫn. Vậy u2 − Dv2 = −1 do đó (2.11) có nghiệm (u, v).
1 + D)2 =
1; b = 2uv = 2x1y1 → u2 + Dv2 + 2uv = x2
1 + Dy2
1 + 2x1y1 → (u + v
Tiếp theo ta chứng minh (u, v) là nghiệm nhỏ nhất của (2.11). Giả sử (x1, y1) là nghiệm nhỏ nhất của (2.11). Theo chứng minh ở 1) ta có a = u2 + Dv2 = x2 √ Dy2
(x1 + y1)2 → u = x1; v = y1. Định lý được chứng minh.
33
Ví dụ là một áp dụng của định lý 2. Nó cũng chỉ ra rằng điều kiện của định lý
1 chỉ là điều kiện cần.
Ví dụ 2.2.4. Chứng minh rằng phương trình x2 − 34y2 = −1 vô nghiệm (Ở đây
34 = 2.17 không số chính phương và cũng không có ước nguyên tố dạng 4k + 3).
Giải Phương trình x2 − 34y2 = 1 có nghiệm nhỏ nhất là (a; b) = (35; 6). Xét hệ
35 = x2 + 34y2
6 = 2xy
Từ phương trình thứ nhất của hệ suy ra (x; y) = (1; 1). Tuy nhiên (1; 1) không thoả
mãn phương trình thứ hai. Vậy hệ vô nghiệm do đó theo định lý 2 phương trình
x2 − 34y2 = −1 vô nghiệm.
Ta thừa nhận định lý
Định lí 2.2.5. Phương trình Pell loại 2
x2 − Dy2 = −1
√ D thành liên phân số có nghiệm khi và chỉ khi trong biểu diễn
√ D = [a; a1, a2, . . . , an, 2a]
chu kỳ n là số lẻ. Trong trường hợp đó (pn−1, qn−1) là nghiệm nhỏ nhất của phương
trình ở đó.
Cn−1 = pn−1 qn−1
là giải phân thứ n − 1.
√ Ví dụ 2.2.6. i) Xét phương trình x2 − 13y2 = −1. Ta có D = [3; 1, 1, 1, 1, 6].
Chu kỳ n = 5 là số lẻ. Vậy phương trình có nghiệm. Ta tính giản phân
C4 = [3, 1, 1, 1, 1]
34
1 = 3 + 1 1 + 1 1 +
1 + 1 1
= = 3 + 3 5 18 5
Vậy nghiệm nhỏ nhất là (18, 5)
√ ii) Xét phương trình x2 − 34y2 = −1. Ta có 34 = [5; 1, 4, 1, 10]. Chu kỳ n = 4
là số chẵn. Vậy phương trình vô nghiệm.
Định lí 2.2.7 (Công thức nghiệm). Giả sử phương trình Pell loại 2
x2 − Dy2 = −1 (II)
n=1 cho bởi
có nghiệm. Gọi (α, β ) là nghiệm nhỏ nhất của nó. Khi đó dãy (xn, yn)∞
√ √ D)2n−1 (α + β xn = √ √ D)2n−1 (α + β D)2n−1 + (α − β 2 D)2n−1 + (α − β √ yn = D 2
cho ta tất cả các nghiệm của (II).
Chứng minh. Giả sử (xn, yn) cho bởi công thức trên. Khi đó
√ √ D)2n−1 D = (α + β xn + yn √ √ D)2n−1 D = (α − β xn − yn
n − Dy2
n = (a2 − Dβ 2)2n−1 = −1
→ x2
Ngược lại giả sử (x, y) là một nghiệm của (2.11). Ta có
√ √ √ D (x + y D)(α + β D) = (xα + Dyβ )(yα + xβ ) √ D = s + t
ở đó s = xα + Dyβ ,t = yα + xβ
→ s2 − Dt2 = (xα + Dyβ )2 − D(yα + xβ )2
35
= (x2 − Dy2)(α 2 − Dβ 2) = (−1)(−1) = 1
Vậy (s,t) là nghiệm của phương trình Pell loại 1 s2 − Dt2 = 1. Gọi (a, b) là nghiệm
nhỏ nhất của nó. Theo công thức nghiệm của phương trình Pell loại 1 và định lý 3 tồn tại n ∈ N∗ sao cho
√ √ √ √ (x + y D) = s + t D)n D)(α + β √ D = (a + b √ D)2)n = (α 2 + Dβ 2 + 2αβ D)n = (α + β √ D)2n
√ = (α + β √ √ D → x + y D = (α + β D)2n−1 = xn + yn
→ x = xn, y = yn
Một số bài toán chọn lọc
Bài toán 2.2.8. Số nguyên dương S được gọi là số Heron nếu nó là diện tích của
một tam giác có ba cạnh là ba số nguyên liên tiếp. Chứng minh rằng S là số Heron
khi và chỉ khi S khi là số hạng của dãy (Sn), n ≥ 1 xác định bởi
S0 = 0, S1 = 6, S2 = 84, Sn+2 = 14Sn+1 − Sn
Lời giải. Gọi S là diện tích của tam giác có ba cạnh là x − 1, x, x + 1 với x > 2, x ∈ N∗. Theo công thức Heron.
(cid:113) x S = 3(x2 − 4) → 16S2 = 3x2(x2 − 1) (2.14) 1 4
Vậy S là số Heron khi và chỉ khi phương trình (2.14) có nghiệm nguyên dương(S, x).
Dễ thấy x phải chẵn. Đặt x = 2y ta có
16S2 = 3x2(x2 − 1) ⇔ S2 = 3y2(y2 − 1)
(cid:113) → S = y 3(y2 − 1) → 3(y2 = −1) = h2
36
→ h = 3z → 3(y2 − 1) = 9z2
→ y2 − 3z2 = 1, S = 3yz
Ngược lại nếu (y, z) là nghiệm của phương trình Pell
y2 − 3z2 = 1 (2.15)
thì x = 2y, y > 1, S = 3yz là nghiệm của (2.14) Nghiệm nhỏ nhất của (2.15) là (2, 1)
Vậy tất cả nghiệm của (2.15) (yn, zn) cho bởi
√ √ 3)n (2 + yn = √ √ 3)n (2 + zn = 3)n + (2 − 2 3)n − (2 − √ 3 2
Do đó
√ √ 3)n − (7 − 4 3)n) ((7 + Sn = 3ynzn = √ 3 4
→ Sn+2 = 14Sn+1 − Sn, S0 = 0, S1 = 6, S2 = 84
Bài toán 2.2.9. Tìm tất cả các số nguyên dương n sao cho 2n + 1 và 3n + 1 đều là
số chính phương.
Lời giải. Vì (2n + 1, 3n + 1) = 1 nên 2n + 1 và 3n + 1 đều là số chính phương khi và chỉ khi (2n + 1)(3n + 1) = y2, y ∈ N∗. Suy ra (12n + 5)2 − 24y2 = 1. Đặt
x = 12n + 5 ta có x2 − 24y2 = 1. Gọi (xk, yk) là nghiệm của nó. Nghiệm nhỏ nhất
của phương trình Pell này là (5, 1). Do đó (xk) cho bởi hệ thức.
x0 = 1, x1 = 5, xk+2 = 10xk+1 − xk.
Dễ chứng minh xk ≡ 5 (mod 12) khi vào chỉ khi k lẻ. Vậy n = nk, k ≥ 1 ở đó
nk = x2k+1 − 5 12
Ta xác định hệ thức truy hồi của dãy (nk)
37
Đặt uk = x2k+1 = 12nk + 5. Ta có
x2k+3 = 10x2k+2 − x2k+1 = 10(10x2k+1 − x2k) − x2k+1
= 100x2k+1 − 10x2k − x2k+1 = 99x2k+1 = x2k+1 − x2k−1
= 98x2k+1 − x2k−1
→ uk+2 = 98uk+1 − uk
⇔ 12nk+2 + 5 = 98(12nk+1 + 5) = 12nk − 5
nk+2 = 98nk+1 − nk + 40
với n1 = 40, n2 = 3960
Bài toán 2.2.10. Cho dãy (xn, yn) xác định như sau (x0, y0) = (0, 1), (x1, y1) =
(3, 5) và
xn+1 = 3xn + 2yn + 1 (2.16)
yn+1 = 4xn + 3yn + 2
Chứng minh rằng (xn, yn) là tất cả các nghiệm nguyên dương của phương trình
x2 + (x + 1)2 = y2
Lời giải. Phương trình đã cho tương đương với
(2x + 1)2 − 2y2 = −1 (2.17)
Đặt u = 2x + 1, → u2 − 2y2 = −1. Nghiệm nhỏ nhất của phương trình này là (1.1).
Do vậy dãy nghiệm (un, yn) cho bởi √ √ (1 + 2)2n+1 un = √ √ (1 + 2)2n+1 yn = 2)2n+1 + (1 − 2 2)2n+1 − (1 − √ 2 2
Từ đó
u0 = 1, u1 = 7, uk+2 = 6uk+1 − uk
38
y0 = 1, y1 = 5, yk+2 = 6yk+1 − yk
Ta có un = 2xk+2 +1 → 2xk+2 +1 = 6(2nk+1 +1)−2nk −1 → x0 = 0, x1 = 3, xk+2 =
6xk+1 − xk + 2. Thành thử dãy nghiệm (xn, yn) của (2.17) cho bởi
x0 = 0, x1 = 3, xn+2 = 6xn+1 − xn + 2
y0 = 1, y1 = 5, yn+2 = 6yn+1 = yk
Thành thử ta chỉ cần chứng minh dãy (2.16) thoả mãn quan hệ
xn+2 = 6xn+1 − xn + 2
yn+2 = 6yn+1 − yk
Thật vậy đặt zn = 2xn + 1. Khi đó dễ kiểm tra
zn+1 = 3zn + 4yn
yn+1 = 2zn + 3yn
→ zn+2 = 3zn + 1 + 4yn+1 = 3zn+1 + 8zn + 12yn
= 3zn+1 + 8zn + 3zn+1 − 9zn = 6zn+1 − zn
→ 2xn+2 + 1 = 6(2xn+1 + 1) − 2xn−1
→ xn+2 = 6xn+1 − xn + 2
Tương tự yn+2 = 6yn+1 − yk
2.3 Phương trình Pythagoras
Trong mục này chúng ta sẽ đi tìm tất cả các nghiệm nguyên dương của phương
trình
x2 + y2 = z2 (2.18)
và xét một số ứng dụng của nó. Những phương trình Diophantine này được gọi là
các phương trình Pythagoras.
39
Định nghĩa 2.3.1. Một bộ ba số nguyên dương (x, y, z) thoả mãn phương trình
(2.18) gọi là một bộ ba số Pythagoras.
Các bộ ba số Pythagora biểu thị độ dài các cạnh của một tam giác vuông. Từ
một bộ ba số Pythagoras (x, y, z) nào đó ta suy ra dễ dàng một tập hợp vô hạn các
bộ ba số Pythagoras khác (tx,ty,tz) với t là số nguyên dương.
Ngược lại, cho (x, y, z) là một bộ ba số Pythagoras bất kỳ và giả sử d = (x, y, z).
Khi đó (x1, y1, z1) cũng là một bộ ba số Pythagoras, ở đó
, , , và x1 = y1 = z1 = (x1, y1, z1) = 1. x d y d z d
Định nghĩa 2.3.2. Một bộ ba số Pythagoras (x, y, z) là nguyên thuỷ nếu (x, y, z) = 1.
Rõ ràng từ lý luận trên ta chỉ cần đi tìm các bộ ba số Pythagoras nguyên thuỷ.
Dễ dàng nhận thấy nếu (x, y, z) là một bộ ba số Pythagoras nguyên thuỷ thì
chúng đôi một nguyên tố cùng nhau. Thật vậy, giả sử d = (x, y). Khi đó d2 là ước
của z2 nên d là ước của z do đó d là ước chung của x, y, z. Vậy d = 1.
Định lí sau đây cho công thức mô tả tất cả các bộ ba số Pythagoras nguyên
thuỷ.
Định lí 2.3.3. Giả sử (x, y, z) là một bộ ba số Pythagoras nguyên thuỷ. Khi đó x và
y có tính chẵn lẻ khác nhau. Nếu x chẵn, y lẻ chẳng hạn (x, y, z) có dạng
y = m2 − n2, n = m2 + n2 x = 2mn,
trong đó m, n là hai số nguyên đương nguyên tố cùng nhau, có tính chẵn lẻ khác
nhau.
Đảo lại, nếu m, n là hai số nguyên dương nguyên tố cùng nhau, một chẵn, một
lẻ thì ba bộ (x, y, z) xác định như trên là một bộ ba số Pythagoras nguyên thuỷ.
Chứng minh. Trước hết vì (x, y) = 1 nên x và y không cùng chẵn. Hai số x và y
cũng không thể cùng lẻ vì nếu như vậy thì z2 = x2 + y2 ≡ 2 (mod 4), điều này
không thể có vì một số chính phương chỉ đồng dư 0 hoặc 1 theo modulo 4.
40
Giả sử x chẵn, y lẻ. Khi đó z lẻ và x2 = z2 − y2(z + y)(z − y), điều này tương
đương với (cid:19) (cid:17)2 (cid:19) (cid:18)z − y = . (2.19) (cid:16) x 2 (cid:18)z + y 2
2 , z−y
2
2 (cid:1) = 1 vì (z, y) = 1. Suy ra tồn tại m, n ∈ N∗ để z+y
Dễ thấy rằng (cid:0) z+y 2 = m2 và z−y 2 = n2. Từ đó x = 2mn, y = m2 − n2, z = m2 + n2. Mặt khác (m2, n2) = 1 nên (m, n) = 1. Hơn nữa vì y và z lẻ nên m, n có tính chẵn lẻ khác nhau.
Bây giờ ta chứng minh phần đảo của định trong định lí trên. Dễ dàng kiểm tra
rằng x, y, z xác định theo công thức trên là bộ ba số Pythagoras.
Ta còn phải chứng minh đó là bộ ba số Pythagoras nguyên thuỷ. Giả sử d =
(y, z). Khi đó vì y, z lẻ nên d lẻ. Ta có d | y + z = 2m2 suy ra
d | m2 và d | z − y = 2n2 suy ra d | n2.
Vì (m, n) = 1 nên từ đó d = 1. Vậy (y, z) = 1 suy ra (x, y, z) = 1. Định lí được chứng
minh.
Sau đây là áp dụng quan trọng của Định lí 2.3.3.
Định lí 2.3.4. Không tồn tại hai số tự nhiên x và y để tổng các bình phương và
hiệu các bình phương của chúng đều là các số chính phương.
Chứng minh. Ta chứng minh bằng phản chứng. Giả sử tồn tại các số nguyên dương
x, y, có tính chất đã nêu.
Trong các cặp số (x, y) ta chọn (x0, y0) là cặp số mà x nhỏ nhất. Giả sử
0 + y2 x2 0 − y2 x2
0 = z2 0, 0 = t2 0 ,
(2.20)
với z0, t0 ≤ N∗.
0 và
Ta có (x0, y0) = 1. Thật vậy, giả sử d = (x0, y0). Từ (2.20) suy ra d2 | z2
0 . Từ đó d | z0 , d | t0 . Đặt
d2 | t2
, , . , y1 = z1 = y t1 = x0 d z0 d t0 d y0 d
41
1 + y2 x2
1 = z2 1,
1 − y2 x2
1 = t2 1 .
Ta có
1 + y2 x2
1 ≥ x2
0 + y2
0 = d(x2
1 + y2
1).
Suy ra (x1, y1) là một cặp thoả mãn tính chất đã nêu. Do đó
Vậy d = 1.
0 + t2
0 = 2x2
0. Do đó z0 và t0 có cùng tính chẵn lẻ.
Từ (2.20) suy ra z2
Đặt
, v = u = z0 + t0 2 z0 − t0 2
với u, v là các số nguyên dương.
Khi đó
(2.21) u + v = z0, u − v = t0vu2 + v2 = x2 0.
0. Mặt khác d | u + v = z0, suy ra
Ta có (u, v) = 1, vì nếu d = (u, v) thì d2 | x2
0 − x2
0 = y2
0 suy ra d | y0. Vậy d = 1.
d2 | z2
Theo (2.21) thì (u, v, x0) là một bộ ba số Pythagoras nguyên thuỷ. Theo Định
lí 2.3.3 tồn tại các số nguyên dương m, n chẵn lẻ khác nhau với (m, n) = 1, m > n
sao cho
u = 2mn, v = m2 − n2;
u = 2m2 − n2, v = 2mn. hoặc
Trong mọi trường hợp, uv = 2mn(m2 − n2). Ta lại có
2y = (u + v)2 − (u − v)2 = 4uv = 8mn(m2 − n2)
suy ra y = 4mn(m2 − n2), tức là y0 = 2k. Vậy
(2.22) mn(m2 − n2) = k2.
Ta có (m, n) = 1 nên (m + n, m) = 1 và (m − n, m) = 1. Vậy (m2 − n2, m) = 1.
42
Tương tự, (m2 − n2, n) = 1. Do điều này nên từ (2.3) suy ra tồn tại a, b, c ∈ N∗
để
(2.23) m = a2, n = b2, m2 − n2 = c2.
Gọi d = (m + n, m − n). Do m, n chẵn lẻ khác nhau nên m + n, m − n lẻ, từ đó d lẻ.
Vì d | m + n, d | m − n nên d | 2m, d | 2n suy ra d | m, d | n (do d lẻ). Suy ra d = 1. Do điều này nên từ (2.23) suy ra tồn tại r, s ∈ N∗ để
m − n = r2, m + n = s2.
Vậy
a2 + b2 = s2, a2 − b2 = r2,
tức là cặp (a, b) thoả mãn tính chất đã nêu trong định lí.
Mặt khác
0 = x2
0 = y2 0.
a2 + b2 = m + n ≤ 2m ≤ 2mn ≤ u = < z0 ≤ z2 z0 + t0 2
Điều này trái với cách chọn cặp (x0, y0). Định lí được chứng minh xong.
Một số bài toán chọn lọc
Bài toán 2.3.5 (Đề dự tuyển thi Toán quốc tế năm 1979). Chứng minh rằng không
tồn tại hình chóp tứ giác đều mà các cạnh, diện tích toàn phần và thể tích của nó
đều là các số nguyên.
Chứng minh. Giả sử g, f , h, S và V theo thứ tự là cạnh đáy, cạnh bên, chiều cao,
diện tích toàn phần và thể tích của một hình chóp tứ giác đều và chúng là những
số nguyên. Ta có
(cid:114) (cid:114)
f = h2 + , V = h2 + , . S = g2 + 2g g2h 3 g2 4
4 là số nguyên. Kí hiệu (cid:114)
g2 2 (cid:113) h2 + g2 Vì g, S là số nguyên nên 2g
h2 + y = g3. , x = 2g2 g2 4
43
Dễ thấy x, y ∈ N∗. Ta có
(cid:19) (cid:18) x2 − y2 = 4g4 − g6 = 4h2g4 = (2g2h)2 22 + g2 4
3 ∈ N∗. Do đó g2 ∈ N∗. Mặt khác,
là số chính phương, vì V = g2h
(cid:19) (cid:18) h2 + = 4g4 f 2 = (2g2 f )2. x2 + y2 = 4g4h2 + 2g6 = 4g4 g2 2
Vì 2g2 f ∈ N∗ nên x2 + y2 là số chính phương. Song điều này mâu thuẫn với Định
lí 2.3.4. Ta có điều cần chứng minh.
Bài toán 2.3.6. Chứng minh rằng phương trình
x4 − y4 = z2
không có nghiệm nguyên dương.
Chứng minh. Ta sẽ chứng minh bài toán này bằng phương pháp phản chứng. Giả
sử (x, y, z) là nghiệm nguyên dương của phương trình đã cho và d = (x, y). Ta có
x = dx0, y = dy0, (x0, y0) = 1.
Thay vào phương trình cho ta
0 − y4
0) = z2
0)(x2
0 − y4 0, x2
0, tức là (x2 0 − y2 0 + y2 0) = 1 bởi vì nếu d1 | (x2
0) = z2 0 − y2
0. Nếu x0 và y0 chẵn 0) và d1 | (x2 0) thì
0 + y2
d4(x4 d2 | z. suy ra
0 = z2 0 + y2 0 − y2 0. Vậy d1 = 1 (do d1 lẻ).
d1 | 2y2 Đặt z = d2z0 suy ra x4 lẻ khác nhau thì (x2 0 và d1 | 2x2
0 − y2
0 = a2, x2
0 − y2
0 = b2, trái với Định lí 2.3.4.
0 = 2a, x2
0 +y2
0 = 2b Suy ra x2
0 = a−b. 1, b = b2 1.
Do đó x2
1 = x2
0, a2
0 +y2 0 = a+b, y2 1. Vì (x0, y0) = 1 nên (a, b) = 1. Do đó a = a2 0, và điều này mâu thuẫn với Định lí 2.3.4.
Vậy a2 Ta có 4ab = z2 1 + b2 Nếu x0 và y0 cùng lẻ thì x2 0 suy ra ab = z2 1 − b2 1 = y2
44
Bài toán 2.3.7. Chứng minh rằng phương trình
x4 + y4 = z2
không có nghiệm nguyên dương.
Chứng minh. Giả sử trái lại, phương trình đã cho có nghiệm nguyên dương. Gọi
0, y2
0, z0) là một bộ ba số Pythagoras nguyên thuỷ. Không làm giảm tổng quát ta giả sử x0 lẻ. Theo
(x0, y0) là nghiệm nguyên dương sao cho tổng x là nhỏ nhất. Lập luận tương tự như trong chứng minh Định lí 2.3.4 ta thấy (x0, y0) = 1. Như vậy (x2
Định lí 2.3.3 tồn tại m, n với (m, n) = 1 sao cho
(cid:110) (2.24) x = m2 − n2, y = 2mn,z0 = m2 + n2.
Vì (m, n) = 1 nên từ (2.24) ta có (x0, n, m) là một bộ ba số Pythagoras nguyên thuỷ.
Vậy lại theo Định lí 2.3.3 tồn tại a, b với (a, b) = 1 sao cho
(cid:110) (2.25) x0 = a2 − b2, n = 2ab,m = a2 + b2.
1 (ở đây y0 = 2y1) suy ra a = a2
1, b = b2 1,
Ta có y2
0s = 2mn = 4abm suy ra abm = y2 1. Thay vào (2.25) ta có m2
1 = a4
1 + b4
1. Mặt khác
1 + b4 a4
1 = m2
1 = m < m2 + n2 = z0z2
0 = x4
0 + y4 0.
m = m2
Điều này trái với cách chọn (x0, y0). Vậy bài toán được chứng minh.
Nhận xét 2.3.8. Qua chứng minh 2.3.4. và lời giải của các Bài toán 2.3.5, 2.3.6,
2.3.7, ta có thể nhận thấy một phương pháp chung sau đây trong lí thuyết phương
trình Diophantine: Để chứng minh một phương trình Diophantine đã cho không
có nghiệm nguyên dương, ta hãy giả sử nó có và khi đó sẽ có một nghiệm nhỏ
nhất (theo một nghĩa nào đó). Sau đó ta sẽ cố gắng kiến thiết một nghiệm nhỏ hơn
nghiệm nhỏ nhất và như vậy ta dẫn đến mâu thuẫn.
45
Chương 3
Liên phân số và ứng dụng trong phương trình Diophantine
Như chúng ta đã biết, với một số thực cho trước, ta có thể biểu diễn nó theo nhiều
cách, chẳng hạn biểu diễn nó như là tích của các số nguyên tố (Định lí cơ bản của
Lý thuyết số), hay viết nó theo các hệ cơ số khác nhau. Trong các cách biểu diễn
ấy, người ta quan tâm đặc biệt đến các liên phân số, hay còn gọi là các phân số liên
tục (continued fractions). Các liên phân số cho phép người ta biểu diễn các số hữu
tỷ và vô tỷ thành các phân số nhiều tầng. Liên phân số là một chủ đề rất rộng lớn
và có nhiều ứng dụng đa dạng trong Lý thuyết số. Chương này dành để trình này
một cách ngắn gọn các sự kiện về liên phân số và đặc biệt là ứng dụng của chúng
để giải phương trình Pell.
3.1 Liên phân số hữu hạn
Định nghĩa 3.1.1. Liên phân số hay phân số liên tục là một biểu thức có dạng
1 a0 + 1 a1 + 1 a2 + · · · + 1 ai−1 + an
trong đó a0, a1, . . . , an là các số thực và a1, . . . , an (cid:54)= 0. Một liên phân số như vậy
được hiệu là [a0, a1, . . . , an].
46
Từ định nghĩa dễ thấy
. [a0, a1, . . . , ak+1] = a0 + 1 [a0, a1, . . . , ak+1]
Nếu a0 ∈ Z và a1, . . . , an là các số nguyên dương thì ta nói [a0; a1, . . . an] là một
liên phân số hữu hạn có độ dài n. Rõ ràng một liên phân số hữu hạn là một số hữu
tỷ. Ngược lại ta có:
Định lí 3.1.2. Mỗi số hữu tỷ đều có thể biểu diễn dưới dạng một liên phân số hữu
hạn.
b trong đó a, b ∈ Z và b > 0. Đặt r0 = a, r1 = b. Thuật
Chứng minh. Giả sử x = a
chia Euclide cho ta
r0 = r1q1 + r2, 0 < r2 < r1,
r1 = r2q2 + r3, 0 < r3 < r2,
. . .
rn−2 = rn−1qn−1 + rn, 0 < rn < rn−1,
rn−1 = rnqn.
Từ đó dễ thấy
= [q1; q2, . . . , qn]. a b
Ta có điều phải chứng minh.
Cho liên phân số hữu hạn [a0; a1, . . . , an]. Với mỗi k ≤ n liên phân số Ck =
[a0; a1, . . . , ak] gọi là giản phân thứ k của [a0; a1, . . . , an].
Công thức tính các giản phân được cho bởi định lí sau.
Định lí 3.1.3. Cho liên phân số hữu hạn [a0; a1, . . . , an]. Giả sử dãy số nguyên
dương p0, p1, . . . , pn và q0, q1, . . . , qn được xác định truy hồi như sau
p0 = a0, q0 = 1,
47
p1 = a0a1 + 1 q1 = a1,
. . .
pk = ak pk−1 + pk−2, qk = akqk−1 + qk−2.
Khi đó giản phân thứ k là Ck = [a0; a1, . . . , ak) được cho bởi
. Ck = pk qk
Chứng minh. Ta chứng minh bằng quy nạp. Với k = 0 ta có
C0 = [a0] = p0/q0.
Với k = 1 ta có
= C1 = [a0; a1] = a0 + = p1/q1. 1 a1 a0a1 + 1 a1
Giả sử định lí đúng cho mọi 0 ≤ k < n. Khi đó với 2 ≤ k < n,
= . Ck = [a0; a1, . . . , ak] == pk qk ak pk−1 + pk−2 akqk−1 + qk−2
Vậy
(cid:21) (cid:20) a0; a1, . . . , ak − 1, ak + Ck+1 = [a0; a1, . . . , ak, ak+1] = 1 ak+1
)pk−1 + pk−2 = )qk−1 + qk−2
=
= = . (ak + 1 ak+1 (ak + 1 ak+1 ak+1(ak pk−1 + pk−2) + pk−1 ak+1(akqk−1 + qk−2) + qk−1 ak+1 pk + pk−1 ak+1qk + qk−1 pk+1 qk+1
Định lí được chứng minh.
Bằng phương pháp quy nạp ta dễ dàng chứng minh được đẳng thức quan trọng
sau giữa các (pk) và (qk).
Định lí 3.1.4. pkqk−1 − pk−1qk = (−1)k−1.
48
Hệ quả 3.1.5. (pk, qk) = 1.
Tiếp theo, ta sẽ mô tả các quan hệ của giản phân.
Định lí 3.1.6. Giả sử (Ck) là dãy giản phân của liên phân số hữu hạn [a0; a1 . . . , an].
Ta có
, 1 ≤ k ≤ n, Ck −Ck−1 =
, 2 ≤ k ≤ n. Ck −Ck−2 = (−1)k−1 qkqk−1 ak(−1)k qkqk−2
Chứng minh. Với đẳng thức thứ nhất ta có
= . Ck −Ck−1 = pkqk−1 − pk−1qk qkqk−1 (−1)k−1 qkqk−1
Với đẳng thức thứ hai ta có
. Ck −Ck−2 = pkqk−2 − pk−2qk qkqk−2
Thay pk = ak pk−1 + pk−2, qk = akqk−1 = qk−2 vào tử số và áp dụng đẳng thức thứ
nhất ta thu được điều phải chứng minh.
Từ định lí trên ta thu được kết quả quan trọng sau.
Định lí 3.1.7. Ta có
C1 > C3 > C5 > . . . ,
C0 < C2 < C4 < . . .
Hơn nữa mỗi giản phân lẻ C2 j−1 đều lớn hơn mỗi giản phân chẵn C2i.
Chứng minh. Từ định lí trên ta thấy nếu k lẻ thì Ck < Ck−2 và nếu k chẵn thì
Ck > Ck−2. Cũng theo định lí trên, ta có)
< 0 suy ra C2m < C2m−1. C2m −C2m−1 = (−1)2m−1 q2mq2m−1
Vậy C2 j−1 > C2 j−1+2i > C2 j+2i > C2i.
49
3.2 Liên phân số vô hạn
Như kết quả mục trên, ta biết rằng mỗi số hữu tỷ sẽ được biểu diễn một cách duy
nhất bằng một liên phân số hữu hạn. Chuyển sang tình huống các số vô tỷ, ta sẽ
thấy, mỗi số vô tỷ sẽ được biểu thị duy nhất dưới dạng một liên phân số vô hạn.
Định lí 3.2.1. Cho a0, a1, a2 . . . là dãy vô hạn các số nguyên với ai > 0 với i ≥ 1.
Đặt
Ck = [a0; a1, . . . , ak].
Khi đó tồn tại giới hạn
Ck = α. lim k→∞
Ta gọi α là giá trị của liên phân số vô hạn [a0; a1; a2 . . .] và viết
α = [a0; a1; a2, . . .].
Chứng minh. Theo Định lí 3.1.7 ta có
C1 > C3 > C5 > . . . > C2n−1 > C2n+1 > . . .
C0 < C2 < C4 < . . . < C2n−2 < C2n < . . .
Hơn nữa dãy (C2k+1) là dãy giản và bị chặn dưới bởi C0 còn dãy (C2k) tăng và bị
chặn trên bởi C1. Vậy tồn tại
và C2k+1 = α1 C2k = α2. lim k→∞ lim k→∞
Ta cần chứng minh α1 = α2. Thật vậy theo Định lí 3.1.7 ta có
. C2k+1 −C2k = 1 q2k+1q2k
Bằng quy nạp) , ta có qk ≥ k. Do đó
C2k+1 −C2k = 0. lim k→∞
Vậy α1 = α2. Định lí được chứng minh.
50
Kết luận quan trọng cho ứng dụng là
Định lí 3.2.2. α = [a0; a1; a2, . . .] là một số vô tỷ.
Chứng minh. Ta sẽ chứng minh bằng phản chứng. Giả sử trái lại α = a/b ∈ Q.
Theo Định lí 3.1.7 ta có C2n < α < C2n+1. Vậy
. 0 < α −C2n < C2n+1 −C2n = 1 q2n+1q2n
Điều này tương đương với
< 0 < α − p2n q2n
⇔ 0 < αq2n − p2n <
⇔ 0 < αq2n − bp2n <
. ⇔ 1 < αq2n − bp2n < 1 q2n+1q2n 1 q2n+1 1 q2n+1 1 q2n+1
Cho k → ∞ ta có điều mâu thuẫn. Như vậy phép chứng minh được kết thúc.
Định lí 3.2.3. Mỗi số vô tỷ đều biểu diễn một cách duy nhất dưới dạng một liên
phân số vô hạn.
3.3 Liên phân số vô hạn tuần hoàn
Ta gọi liên phân số vô hạn [a0; a1, a2, . . .] là tuần hoàn nếu dãy (an)là tuần hoàn kể
từ một chỉ số nào đó tức là: tồn tại số nguyên dương m và k với mọi n ≥ m ta có
an = an+k. Số nguyên dương k được gọi là chu kỳ. Trong trường hợp đó ta viết
[a0; a1, a2, . . . , am−1, am, am+1, . . . , am+k−1]
Bài toán đặt ra là đặc trưng tất cả các số vô tỷ có biểu diễn liên phân số vô hạn
tuần hoàn. Ta có khái niệm sau
51
Định nghĩa 3.3.1. Số vô tỷ α được gọi là số vô tỷ bậc hai nếu nó là nghiệm của
một tam thức bậc hai với hệ số nguyên.
√ 3 là số vô tỷ bậc hai vì nó là nghiệm của x2 − 4x + Ví dụ 3.3.2. Số vô tỷ α = 2 +
1 = 0.
Bổ đề 3.3.3. Số thực α là vô tỷ bậc hai nếu và chỉ nếu có tồn tại các số nguyên
a, b, c với b > 0 và không chính phương, c (cid:54)= 0 sao cho
√ b . a = a + c
Chứng minh. Giả sử α là số vô tỷ bậc hai. Khi đó tồn tại các số nguyên A, B,C sao
cho α là nghiệm của phương trình Ax2 + Bx +C = 0. Vậy
√ B2 − AC −B ± . α == 2A
Đặt a = −B, b = B2 − 4AC, c = 2A hoặc a = B, b = B2 − 4AC, c = −2A ngược lại
nếu √ b . α = a + c
Thì α là số vô tỷ và nó là nghiệm của phương trình bậc hai c2x2 − 2acx + a2 − b =
0.
Bổ đề 3.3.4. Nếu α là số vô tỷ bậc hai thì (rα + s)/(tα + u) cũng là số vô tỷ bậc
hai nếu r, s,t, u là các số nguyên.
Chứng minh. Giả sử √ b . α = a + c
Tính toán cho ta
√ b (ar + c)(at + cu) − rtb + (r(at + cu) − t(ar + cs)) . = rα + s tα + u (at + cu)2 − tb2
52
Định nghĩa 3.3.5. Số vô tỷ
√ b . α =
a − c Được gọi là liên hợp của α và ký hiệu là α (cid:48).
Bổ đề 3.3.6. Nếu số vô tỷ bậc hai α là nghiệm của phương trình Ax2 + Bx +C = 0
thì liên hợp của nó cũng là nghiệm của phương trình đó.
Chứng minh. Thật vậy
α + α (cid:48) = 2a/c = −BA, (α)(α (cid:48)) = a2 − b/c2 = C/A.
Bằng phép tính ta dễ thấy
Bổ đề 3.3.7. Ta có các hệ thức sau:
(α ± β )(cid:48) = α (cid:48) ± β (cid:48),
(cid:19)(cid:48) = (αβ )(cid:48) = α (cid:48)β (cid:48), (cid:18)α β α (cid:48) β (cid:48) .
Ta có định lý cơ bản sau đây do Lagrange tìm ra
Định lí 3.3.8. Số vô tỷ α có biểu diễn liên phân số tuần hoàn khi và chỉ khi nó là
số vô tỷ bậc hai.
Chứng minh. Trước hết ta chứng minh rằng nếu α có biểu diễn liên phân số tuần
hoàn thì nó là số vô tỷ bậc hai.
Giả sử
[a0; a1, a2, . . . , am−1, am, am+1, . . . , am+k−1]
Đặt
β = [am, am+1, . . . , am+k−1]
53
Khi đó β = [am, am+1, . . . , am+k, β ] do đó
. (3.1) β = βPk + pk−1 βPk + pk−1
trong đó pk/qk và pk−1/qk−1 là hai giản phân cuối của [am, am+1, . . . am+k]. Từ
công thức (3.1) suy ra
qkβ 2 + (qk−1 − pk)β − pk−1 = 0.
Vậy β là số vô tỷ bậc hai. Ta lại có α = [a0; a1; a2, . . . , am−1, β ] do đó
. α = β pm−1 + pm−2 β qm−1 + qm−2
Do đó theo Bổ đề 3.3.6 ta có α là số vô tỷ bậc hai.
Ví dụ sau đây minh hoạ cách tìm số vô tỷ bậc hai từ biểu diễn liên phân số tuần
hoàn của nó.
Ví dụ 3.3.9. Tìm x biết rằng x = [3; 1, 2].
Ta có x = [3; y] với y = 1, 2. Ta có y = [1; 2, y] do đó
= . = 1 + 3y + 1 2y + 1 1 2 + 1 y
√ Suy ra 2y2 − 2y − 1 = 0. Vì y > 0 nên y = (1 + 3)/2. Vì x = 3 + 1/y nên ta tìm
được √ 2 = . x = 3 + 4 + 2 2 √ 1 + 2
Để chứng minh phần ngược lại ta cần bổ đề sau
Bổ đề 3.3.10. Nếu α là số vô tỷ bậc hai thì nó có thể biểu diễn dưới dạng
√ d α = P + Q
trong đó P, Q, d là các số nguyên sao cho Q | (d − P2).
54
√ Chứng minh. Ta có α = (a + b)/c. Nhân cả tử và mẫu với |c| ta được α =
(a|c|+)/c|c| . Đặt P = a|c|, d = bc2, Q = c|c| = ±c2. Khi đó d − P2 = c2(b − a2) chia hết Q = ±c2.
Giả sử α = α0 là số vô tỷ bậc hai. Ta xây dựng dãy (a0, a1, a2 . . .) như sau.
√ d)/Q0. Theo Bổ đề 3.3.10 ta có các số nguyên P0, Q0 và d sao cho α0 = (P0 +
Q0 | (d − P). Ta đặt a0 = [α0] và xác định P1 = a0Q0 − P1, Q1 = (d − P)/Q0,
α1 = (P1)/Q1. Tiếp đó đặt a1 = [α1]. Một cách tổng quát nếu có
√ d Pk ∈ Z, Qk ∈ Z, Qk | (d − P), ak = ak = [αk]. Pk + Qk
Ta sẽ đặt
Pk+1 = akQk − Pk, Qk+1 = (d − P)/Qk, ak+1 = ak+1 = [αk+1].
Khi đó tính toán cho thấy
sQk+1 = (d − P)/Qk + (2kPk − aQk)
do đó Qk+1 ∈ Z và vì Qk+1Qk = (d − P) nên Qk+1 | (d − P). Có thể chứng minh
được rằng
α = [a0, a1, a2, . . .]
và hơn nữa dãy (an) xác định như trên là tuần hoàn.
√ 28)/4. Ví dụ 3.3.11. Khai triển liên phân số của số α = (6 +
√ 28)/4, Chứng minh. Ta có P0 = 6, Q0 = 4, d = 28, 4 | (28 − 62) = −8, a0 = (6 +
a0 = [α0] = 2 và
√ 28)/6, a1 = [α1] = 1 P1 = 2.4 − 6 = 2, Q1 = (28 − 22)/4 = 6, α1 = (2 +
√ P2 = 1.6 − 2 − 4 = 4, Q2 = (28 − 42)/6 = 2, α2 = (4 + 28)/2, a2 = [α2] = 4
√ 28)/6, a3 = [α3] = 1 P3 = 4.2 − 4 = 4, Q3 = (28 − 42)/2 = 6, α3 = (4 +
√ P4 = 1.6 − 4 = 2, Q4 = (28 − 22)/6 = 4, α4 = (2 + 28)/4, a4 = [α4] = 1
55
√ P5 = 1.4 − 2 = 2, Q5 = (28 − 22)/6 = 4, α5 = (2 + 28)/4, a5 = [α4] = 1
Ta thấy P1 = P5, Q1 = Q5 do đó a1 = a5 và dãy tuần hoàn chu kỳ 4. Ta có √ 6 + 28 = [2; 1, 4, 1, 1, ] 4
Tiếp theo ta muốn tìm điều kiện để số vô tỷ bậc hai có biểu diễn liên phân
số tuần hoàn ngay từ đầu, tức là điều kiện để tồn tại số nguyên dương k sao cho
an = an+k với mọi n ≥ 0. Ta có định lý sau
Định lí 3.3.12. Số vô tỷ bậc hai α có biểu diễn tuần hoàn ngay từ đầu nếu và chỉ
nếu α > 1 và −1 < α (cid:48) < 0.
Chứng minh định lý này khá phức tạp nên ta bỏ qua. √ Bây giờ ta sẽ xác định biểu diễn liên phân số của d.
√ √ √ √ d + [ d] − Xét số α = d]. Ta có α (cid:48) = [ d do đó α > 1 và −1 < α (cid:48) < 0. √ √ d + [ d]] = Vậy α có biểu diễn tuần hoàn ngay từ đầu. Số hạng đầu tiên a0 = [ √ √ 2[ d] = 2a với a = [ d]. Ta có
√ √ √ d + a = d + [ d] = [2a; a1, a2, . . . , an]
= [2a; a1, a2, . . . an, 2a; a1, a2, . . . , an]
Suy ra √ d = [a; a1, a2, . . . , an, 2a].
Phân tích cẩn thận hơn ta còn có thể chứng minh được
a1 = an, a2 = an−1, . . .
tức là dãy (a1, . . . , an) đối xứng, tức là nó có dạng
√ d = [a; a1; a2, . . . , a2, a1, 2a]
√ ở đó a = [ d].
56
3.4 Áp dụng vào phương trình Diophante
3.4.1 Phương trình bậc nhất hai ẩn Ax + By = C
Chúng ta biết rằng phương trình có nghiệm nếu và chỉ nếu d = (A, B) là ước của
C. Trong trường hợp này giả sử A = ad, B = bd, C = cd thì (a, b) = 1 và phương
trình đã cho tương đương với
ax + by = c. (3.2)
Nếu (x0, y0) là một nghiệm của (3.2) thì tất cả các nghiệm (x, y) của (3.2) được
cho bởi công thức x = x0 + bt; y = y0 − at. Như vậy việc giải phương trình (3.2)
quy về tìm một nghiệm (x0, y0) của nó.
Xét phương trình
ax + by = 1. (3.3)
Nếu (x0, y0) là một nghiệm của (3.3) thì (cx0, cy0) là nghiệm của (3.2). Thành thử
ta quy về bài toán: Cho (a, b) = 1. Hãy tìm một nghiệm của phương trình (3.3).
Ta biểu diễn số a/|b| thành liên phân số hữu hạn
= [a0; a1; a2; . . . . . . ; an]. a |b|
Gọi pn−1/qn−1 và pn/qn là hai giản phân cuối cùng của liên phân số này. Ta có
a/|b| = pn/qn, (a, b) = 1, (pn, qn) = 1 nên a = pn, |b| = qn. Theo Định lý 3.3.8 ta có pnqn−1 − pn−1qn = (−1)n−1 suy ra aqn−1 − |b|qn−1 = (−1)n−1. Điều này kéo theo a(−1)n−1qn−1 + |b|(−1)n−1 pn−1 = 1.
Vậy, nếu b > 0 thì phương trình (3.3) có một nghiệm là
x = (−1)n−1qn−1, y = (−1)n pn−1.
Nếu b < 0 thì phương trình (3.3) có một nghiệm là
x = (−1)n−1qn−1, y = (−1)n−1 pn−1.
57
Ví dụ 3.4.1. Giải phương trình 342x − 123y = 15.
Lời giải. Vì (342, 123) = 5 nên phương trình đã cho tương đương với 114x −41y =
5.
Ta biểu diễn số 114/41 thành liên phân số. Ta có
114 = 2 · 41 + 32 41 = 1 · 32 + 932 = 3 · 9 + 5 9 = 1 · 5 + 45 = 1 · 4 + 1 4 = 4 · 1.
Do vậy
= [2; 1, 3, 1, 1, 4]. 114 41
Ta có n = 5, p4/p4 = [2; 1, 3, 1] = 25/9. Vì b = −41 < 0 nên một nghiệm của
phương trình 114x − 41y = 1 là x = q4 = 9, y = 25. Suy ra một nghiệm của phương
trình 114x − 41y = 5 là x = 5 · 9 = 54, y = 5 · 25 = 125. Nghiệm tổng quát của
phương trình đã cho là:
x = 45 + 41t, y = 125 + 114t với .t ∈ Z
3.4.2 Phương trình x2 − dy2 = ±1
Nhắc lại, ta gọi phương trình Pell là các phương trình có dạng
x2 − dy2 = ±1.
Bổ đề 3.4.2. Cho d là số không chính phương. Giả sử Pk, Qk, αk, ak là các số xác
√ d định trong việc tìm khai triển liên phân số của
k+1
√ d , αk = ak = [αk], Pk + Qk
. Pk+1 = akqk − pk, Qk+1 = d − P2 Qk
√ d , αk+1 = ak+1 = [αk+1].
k − dq2 p2
k = (−1)k−1Qk+1.
Pk+1 + Qk+1 √ d. Khi đó Giả sử pk/qk là giản phân thứ k của
58
√ Chứng minh. Vì d = α0 = [a0; a1, a2, . . . , ak, αk+1] nên ta có
√ . d = α0 = αk+1 pk + pk−1 αk+1qk + qk−1
√ d Vì αk+1 = Pk+1+ Qk+1
ta có
√ √ √ d = . (Pk+1 + (Pk+1 + d)pk + Qk+1 pk−1 d)pk + Qk+1qk−1
Do đó
√ √ d. d = (Pk+1 pk + Qk+1 pk−1) + pk npk = (Pk+1qk + Qk+1qk−1)
√ Từ đó suy ra (do d (cid:54)∈ Q)
nqk = Pk+1 pk + Qk+1 pk−1, Pk+1qk + Qk+1qk−1 = pk.
Từ đó (nhân phương trình đầu với qk, phương trình thứ hai với pk, rồi trừ cho nhau
k − dq2 p2
k = (pkqk−1 − pk−1qk)Qk−1 = (−1)k−1Qk+1.
ta được.
Ta có điều phải chứng minh.
√ Định lí 3.4.3. Giả sử chu kỳ của biểu diễn liên phân số của d là r. Gọi pk/qklà √ giản phân thứ k của
d. Nếu r chẵn thì x = ptr−1, y = qtr−1 với t = 1, 2 . . . là nghiệm của phương trình Pellx2 − dy2 = 1. Nếu r lẻ thì x = p2tr−1, y = q2tr−1, với t = 1, 2, . . . là nghiệm của phương trình Pell x2 − dy2 = 1.
√ √ d = 0 + Chứng minh. Vì d/1 nên Q0 = 1, suy ra Qkr = Q0 = 1 với mọi k.
kr−1 − dq2 p2
kr−1 = (−1)kr−2Qkr = (−1)kr.
Theo Bổ đề 3.4.2 ta có
2tr−1 −
kr−1 − dq2
kr−1 = 1 với mọi k ∈ N, nếu r lẻ thì p2
Như vậy nếu n chẵn thì p2
2tr−1 = 1.
dq2
59
Bổ đề 3.4.4. Ta có Qi (cid:54)= 1 với mọi i = 1, 2 . . . và Qk = 1 khi và chỉ khi k chia hết
cho r.
Để chứng minh đây là tất cả các nghiệm của phương trình Pell ta cần các bổ đề
sau
Bổ đề 3.4.5. Cho α là một số vô tỷ và r/s là số hữu tỷ tối giản với r > 0 và
(cid:12) (cid:12) (cid:12) < (cid:12) (cid:12) (cid:12)α − r s 1 2s2 .
Khi đó r/s phải là một giản phân của α.
Chứng minh. Giả sử r/s không là giản phân khi đó tồn tại k sao cho
qk ≤ s < qk+1.
Theo Bổ đề 3.4.2 ta có
|qkα − pk| ≤ |sα − r| = s|α − r/s| < 1/(2s).
Suy ra
|α − pk/qk| < 1/(2sqk).
Vì |spk − rqk| ≥ 1 nên ta có
≤ = − 1 sqk |spk − rqk| sqk pk qk
+ = (cid:12) (cid:12) (cid:12)α + (cid:12) (cid:12) (cid:12) r s (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) α − (cid:12) (cid:12) r s pk qk
< + (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) 1 2s2 . 1 2sqk
2s2 , tức là qk > s. Điều mâu thuẫn này đã chứng minh phát biểu của bổ
< 1
Vậy 1 2sqk đề là đúng.
√ Bổ đề 3.4.6. Giả sử x, y là các số nguyên dương sao cho x2 − dy2 = n và |n| < d. √ Khi đó x/y là một giản phân của d.
60
y −
√ √ d)(x − y d) = n suy ra x > Chứng minh. Xét trường hợp n > 0. Ta có (x + y √ √ y d. Vậy 0 < x d. Ta có
Lại có
√ √ d − d = = < < = x y x − y 1 2y2 . √ d √ d x2 − dy2 √ d y(x + y 2y2
n √ y(2y d √ Theo Bổ đề 3.4.5 thì x/y là một giản phân của d.
Giả sử n < 0. Khi đó
y2 − (1/d)x2 = −n/d. √ Ta có −n/d > 0, −|n|/d < 1/ d. Vậy theo bước trước y/x là một giản phân của √ √ √ d) = 1/ d. Nhưng khi đó x/y = 1/(y/x) là một giản phân của 1/(1/( d. Phép
chứng minh định lí được kết thúc.
Định lí 3.4.7. Cho phương trình Pell
x2 − dy2 = 1.
√ Gọi r là chu kỳ của biểu diễn liên phân số của d.
Nếu r chẵn thì tất cả các nghiệm của phương trình Pell là x = pkr−1, y = qkr−1.
Nếu r lẻ thì tất cả các nghiệm của phương trình Pell là x = p2tr−1, y = q2tr−1
với t ∈ N∗.
Chứng minh. Giả sử (x, y) là nghiệm của phương trình Pell. Theo Bổ đề 3.4.6, tồn
i − dq2 p2
i = 1.
tại i để x = pi, y = qi. Từ đó
Từ Bổ đề 3.4.2 rút ra (−1)i−1Qi+1 = 1. Suy ra Qi+1 = ±1. Vì qk+1 (cid:54)= −1 nên
Qi+1 = 1 và i lẻ. Theo Bổ đề 3.4.4 ta rút ra tồn tại ki + 1 = kr, kéo theo i = kr − 1
vàkr chẵn. Thành thử nếu r lẻ thì k chẵn, k = 2t. Phép chứng minh định lí được kết
thúc.
61
Xét phương trình
x2 − dy2 = −1 (3.4)
Ta có kết quả sau
Định lí 3.4.8. Phương trình x2 − dy2 = −1 có nghiệm khi và chỉ khi chu kỳ r của √ biểu diễn liên phân số của d là số lẻ. Trong trường hợp ấy các nghiệm của nó là
x = p(2tr−r−1), y = q(2tr−r−1) với t = 1, 2, . . ..
Chứng minh. Từ Bổ đề 3.4.2 dễ thấy nếu chu kỳ r của biểu diễn liên phân số của √ d là số lẻ thì x = p(2tr−r−1), y = q(2tr−r−1) với t = 1, 2, . . . là nghiệm.
Giả sử (x, y) là nghiệm của phương trình (3.4). Theo Bổ đề 3.4.6 tồn tại i để
i − dq2 p2
i = −1.
x = pi, y = qi. Từ đó
Từ Bổ đề 3.4.2 ta rút ra (−1)i−1Qi+1 = −1, suy ra Qi+1 = ±1. Vì Qi+1 (cid:54)= −1 nên Qi+1 = 1 và i chẵn. Theo Bổ đề 3.4.2 tồn tại k ∈ N sao choi + 1 = kr, suy ra
i = kr − 1 và kr lẻ. Thành thử nếu r chẵn thì kr luôn chẵn do đó phương trình vô
nghiêm.
Trong trường hợp r lẻ lý luận tương tự như trong trường hợp phương trình Pell
x2 − dy2 = 1 tất cả các nghiệm phải có dạng x = pkr−1, y = qkr−1 trong đó kr lẻ
tức là khi k lẻ hay x = p(2tr−r−1), y = q(2tr−r−1) với t = 1, 2, . . . Phép chứng minh
định lí được kết thúc.
62
Kết luận
1 Những kết quả đã đạt được
Luận văn “Một số lớp phương trình Diophantine” đã đạt được các kết quả sau:
1. Trình bày các kiến thức cơ sở về phương trình Diophantine tuyến tính (bậc
nhất hai ẩn và nhiều ẩn).
2. Trình bày về một số phương trình Diophantine phi tuyến, như Phương trình
Pell loại 1, loại 2, phương trình Pell tổng quát, Phương trình Pythagoras-
Fermat.
3. Ứng dụng của liên phân số trong phương trình Diophantine.
2 Đề xuất một số hướng nghiên cứu tiếp theo
Phương trình Diophantine là một trong những chủ đề rất rộng của Lý thuyết số.
Sau những kết quả đã đạt được trong luận văn, chúng tôi hi vọng và cố gắng sẽ tiếp
tục nghiên cứu các chủ đề liên quan, chẳng hạn:
• Các phương pháp và kỹ thuật khác để tấn công các phương trình Diophan-
tine, ví dụ phương pháp xuống thang, các phương pháp số học, đại số và
hình học, . . .
• Nghiên cứu về các các lớp phương trình Diophantine phi tuyến khác như
phương trình có chứa hàm mũ.
63
Tài liệu tham khảo
Tiếng Việt
[1] A.D. Aczel (2001), Câu chuyện hấp dẫn về bài toán Ferma (Người dịch: Trần
Văn Nhung, Đỗ Trung Hậu, Nguyễn Kim Chi), NXB Giáo dục.
[2] Vũ Ngọc Khánh (2015), Một số vấn đề về phương trình Diophantine, Luận
văn thạc sĩ toán học,
[3] Hà Huy Khoái (2004), Số học, NXB Giáo dục.
[4] Đặng Hùng Thắng (2010), Bài giảng số học, NXB Giáo dục.
Tiếng Anh
[5] K.H. Rosen (1986), Elementary Number Theory and its Applications,
Addison–Wesley Publishing Company.
[6] W. Siepinski (1964), Elementary Theory of Number, North-Holland Mathe-
matical Library (volume 31).
![Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250807/kimphuong1001/135x160/50321754536913.jpg)
