Phương trình Pell

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Phương trình Pell (Pell's equation) là bài toán tìm nghiệm nguyên Diophantine bậc hai với yêu cầu là giải một trong những phương trình nghiệm nguyên sau:

dạng chính tắc (còn gọi là phương trình Pell loại I):
 x^2 - dy^2 = 1 ,
dạng phương trình Pell âm (còn gọi là phương trình Pell loại II):
 x^2 - dy^2 = -1 ,
Với d là số nguyên dương và không phải là số chính phương.

Ngoài ra, còn có các dạng:

Phương trình Pell chứa tham số:
 x^2 - dy^2 = n ,
Phương trình Pell dạng tổng quát:
 Ax^2 + By^2 = n .

Lagrange chứng minh rằng với d không phải là số chính phương, phương trình Pell có vô số nghiệm nguyên dương.

Phương trình được đặt tên là Pell bắt nguồn từ sơ suất của Leonhard Euler. Khi Euler đọc tác phẩm của Lord Brouncker, nhà toán học châu Âu đầu tiên tìm ra lời giải tổng quát của bài toán, Euler đã nhầm Brouncker với John Pell.

Phương trình này được nghiên cứu đầu tiên ở Ấn Độ cổ đại, bởi Brahmagupta (Brahmagupta là người đã phát triển phương pháp chakravala nhằm giải quyết phương trình Pell và các phương trình bậc hai bất định khác trong tác phẩm Brahma Sphuta Siddhanta vào năm 628, trước Pell 1000 năm). Tác phẩm Brahma Sphuta Siddhanta đã được dịch sang tiếng Arap vào năm 773, và dịch sang tiếng Latin vào năm 1126. Ngoài ra, Braskara II vào thế kỉ 12 và Narayana vào thế kỉ 14 đã tìm ra lời giải tổng quát cho phương trình Pell và các phương trình bậc hai bất định khác.

Lời giải cho một số dạng đặc biệt của phương trình Pell (ví dụ khi số biến nhiều hơn 2), đã được biết đến từ rất lâu ít nhất là từ thời Pi-ta-goHy Lạp cổ.

Muốn biết rõ hơn, hãy xem Lenstra (2002) and Barbeau (2003).

Lịch sử[sửa | sửa mã nguồn]

Từ năm 400 TCN, ở Ấn Độ và Hy Lạp, người ta đã nghiên cứu phương trình Pell. Chủ yếu trong trường hợp riêng:

 x^2 - 2y^2=1 \,

vì có nghiệm liên quan đến căn bậc hai của 2. Cụ thể hơn, nếu x, y là nghiệm nguyên của phương trình này, thì x / y xấp xỉ \sqrt 2 . Braudhayana khám phá ra rằng, với x = 17, y = 12 và x = 577, y = 408 là 2 nghiệm của phương trình Pell, đồng thời 17 / 12, 577 / 408 xấp xỉ rất sát với \sqrt 2 .

Sau đó, Ácsimét đã sử dụng một phương trình tương tự để ước lượng căn bậc hai của 3, và tìm ra phân số 1351/780.

Vào khoảng năm 250 Công Nguyên, Diophantus (Diophantine) đã nghiên cứu 1 dạng khác của phương trình Pell:

 a^2 x^2+c=y^2. \,

Diophantus đã giải phương trình trong trường hợp a = 1 và c = −1, 1, và 12, và cho a = 3 and c = 9.

Brahmagupta phát minh ra phương pháp tổng quát cho phương trình Pell, được biết đến với tên gọi phương pháp chakravala. Alkarkhi cũng nghiên cứu các vấn đề tương tự như Diophantus. Bhāskara I đã sáng tạo ra phương pháp sinh các nghiệm mới từ một nghiệm đã biết, công trình này được E. Strachey xuất bản bằng tiếng Anh vào năm 1813.

Vào năm 1766-1769, Lagrange đã phát triển 1 lý thuyết tổng quát về phương trình Pell, dựa trên phân số liên tục và các thao tác đại số với các số thực có dạng P+Q\sqrt{a}.[1]

Lời giải của phương trình Pell loại I và II[sửa | sửa mã nguồn]

Nhận xét, nếu (x,y) là nghiệm nguyên của phương trình đã cho thì (-x,y), (x,-y), (-x,-y) cũng là nghiệm, do đó ta chỉ cần quan tâm đến các nghiệm nguyên không âm.

Phương trình Pell  x^2 - dy^2 = 1 luôn có nghiệm tầm thường là x=1, y=0. Do đó, ta chỉ quan tâm đến các nghiệm nguyên không âm và không tầm thường.

Một số điều kiện của d để có nghiệm[sửa | sửa mã nguồn]

Định lý 1: Với mọi d không phải là số chính phương, phương trình x^2-dy^2=1 luôn có nghiệm nguyên dương.

Định lý 2: Nếu d có ước nguyên tố dạng 4k+3 thì phương trình x^2-dy^2=-1 vô nghiệm.

Phương pháp sinh từ nghiệm nguyên dương nhỏ nhất[sửa | sửa mã nguồn]

Nghiệm nguyên dương nhỏ nhất theo nghĩa: x,y >0 và x + y\sqrt d là nhỏ nhất.

Phương pháp này dùng để tìm tất cả các nghiệm nguyên dương của phương trình  x^2 - dy^2 = 1, với d không phải là số chính phương.

Khi biết nghiệm nhỏ nhất của phương trình là (x1,y1), cho phép tìm ra tất cả các nghiệm nguyên dương còn lại theo công thức tổng quát:

x_i + y_i\sqrt d = (x_1 + y_1\sqrt d)^i.

Công thức truy hồi tương đương:

\displaystyle x_{i+1} = x_1 x_i + d y_1 y_i,
\displaystyle y_{i+1} = x_1 y_i + y_1 x_i.

Ví dụ:

Trong ví dụ trước  x^2 - 2y^2 = 1 , ta tìm ra nghiệm nhỏ nhất là (3,2). Tìm các nghiệm còn lại:

x_2 + y_2\sqrt 2 = (3 + 2\sqrt 2)^2 = 17 + 12\sqrt 2, suy ra nghiệm (17,12);
x_3 + y_3\sqrt 2 = (3 + 2\sqrt 2)^3 = 99 + 70\sqrt 2, suy ra nghiệm (99,70).

Lời giải dựa trên phân số liên tục[sửa | sửa mã nguồn]

Xem thêm bài phân số liên tục, xem thêm [2].

Định lý 1[sửa | sửa mã nguồn]

Viết dãy các giản phân của  \sqrt d:  \frac {h_{n}} {k_{n}}.

Biểu diễn liên phân số của  \sqrt d có dạng vô hạn tuần hoàn, gọi r là độ dài của 1 chu kì. Khi đó:

nếu r chẵn thì tất cả các nghiệm nguyên dương của phương trình  x^2 - dy^2 = 1 là ( {h_{n}}, {k_{n}}) là với n có dạng k \cdot r - 1;
nếu r lẻ thì tất cả các nghiệm nguyên dương của phương trình  x^2 - dy^2 = 1 là( {h_{n}}, {k_{n}}) với n có dạng 2 \cdot t \cdot r - 1.

Ví dụ:

  • Giải phương trình nghiệm nguyên dương:
 x^2 - 2y^2 = 1 .
Biểu diễn liên phân số của  \sqrt 2 là:
 \sqrt 2 = [1;2,2,2,2, \,\ldots,] , biểu diễn này có chu kì r=1 lẻ, do đó nghiệm của phương trình là ( {h_{n}}, {k_{n}}) với n có dạng 2 \cdot t - 1, các giản phân ở vị trí lẻ.
Dãy giản phân của  \sqrt 2 :
 1,   \frac{3}{2},   \frac{7}{5},   \frac{17}{12},   \frac{41}{29},   \frac{99}{70},   \frac{239}{169},   \frac{577}{408},   \frac{1393}{985},   \frac{3363}{2378},   \frac{8119}{5741}, \,\ldots, .
Chú ý dãy số trên được bắt đầu với số thứ tự bằng 0.
Lấy các phân số ở vị trí lẻ ta được nghiệm nguyên dương của phương trình  x^2 - 2y^2 = 1 là: (3,2) (17,12), (99,70), (577,408), (3363,2378),...
và tất nhiên cả nghiệm tầm thường là (1,0).
  • Giải phương trình nghiệm nguyên dương:
 x^2 - 13y^2 = 1 .
Biểu diễn liên phân số của  \sqrt 13 là:
 \sqrt 13 = [3;1,1,1,1,6,1,1,1,1,6 \,\ldots,] , biểu diễn này có chu kì r=5 lẻ, các nghiệm cần tìm là ( {h_{n}}, {k_{n}}) với n có dạng 10 \cdot t - 1.
Dãy giản phân của  \sqrt 13 là (dãy này bắt đầu với số thứ tự là 0):
 3, \frac{4}{1} , \frac{7}{2}, \frac{11}{3} , \frac{18}{5} , \frac{119}{33} , \frac{137}{38} , \frac{256}{71} , \frac{393}{109}, \frac{649}{180}, \frac{4287}{1189}, \ldots .
Với t=1, n=9, ta tìm ra nghiệm nguyên dương nhỏ nhất của phương trình đã cho:
(649,180).

Định lý 2[sửa | sửa mã nguồn]

Phương trình Pell x^2-dy^2=-1 có nghiệm khi và chỉ khi biểu diễn liên phân số của  \sqrt d có chu kì r lẻ và các nghiệm nguyên dương của phương trình sẽ là (h_{n},k_{n}) với n có dạng 2 \cdot t \cdot r-r-1.

Ví dụ:

  • Giải phương trình nghiệm nguyên:
 x^2 - 13y^2 = 1 .
Theo như phân tích ở trên, thì r=5, do đó các nghiệm nguyên dương của phương trình có dạng (h_{10t-6},k_{10t-6}), với t=1 đó là cặp (18,5).

Dạng biểu diễn rút gọn và các thuật toán nhanh[sửa | sửa mã nguồn]

Trong các bài toán cụ thể, ngay cả nghiệm nhỏ nhất cũng có thể rất lớn. Và trong nhiều trường hợp, người ta phải biểu diễn nó dưới dạng gọn hơn là:

x_1+y_1\sqrt n = \prod_{i=1}^t (a_i + b_i\sqrt n)^{c_i}

với các hệ số ai, bi, and ci nhỏ hơn rất nhiều (nếu so sánh với nghiệm nhỏ nhất).

Ví dụ, bài toán đàn gia súc Archimedes có thể giải quyết bằng cách dùng phương trình Pell, nhưng nghiệm nhỏ nhất của nó quá lớn, nếu viết hết nghiệm này ra giấy có thể đến 206545 chữ số. Và như thế phải viết nghiệm đó dưới dạng rút gọn:

x_1+y_1\sqrt n=u^{2329},

với:

u = (x'_1+y'_1\sqrt{4729494})

\scriptstyle x'_1\scriptstyle y'_1 lần lượt có 45 và 41 chữ số thập phân.

Chính xác hơn là:

u = (300426607914281713365\sqrt{609}+84129507677858393258\sqrt{7766})^2. Lenstra 2002.

Các phương pháp liên quan đến sàng toàn phương (quadratic sieve) (dùng trong phân tích số ra ước số nhỏ hơn (integer factoriaztion)), được dùng để tập hợp các mối quan hệ giữa các số nguyên tố trong trường số tổng quát hóa bởi √n, và kết hợp các mối quan hệ này nhằm tìm ra dạng biểu diễn của dạng số đó. Những thuật toán sử dụng phương trình Pell hiệu quả hơn các thuật toán dùng liên phân số rất nhiều; bởi vì hàm thời gian của các thuật toán dùng phương trình Pell không phải là các hàm đa thức. Sử dụng giả thiết Riemann tổng quát hóa (generalized Riemann hypothesis), ta ước lượng được thời gian:

\exp O(\sqrt{\log N\log\log N}),

với N = log n kích thước dữ liệu vào, đối với sàng toàn phương Lenstra 2002.

Mối liên hệ với các đối tượng toán học khác[sửa | sửa mã nguồn]

Phương trình Pell có mỗi liên hệ với một số đối tượng toán học quan trọng khác

Lý thuyết số đại số[sửa | sửa mã nguồn]

Đa thức Chebyshev[sửa | sửa mã nguồn]

Demeyer (2007) đề cập về mối liên hệ giữa phương trình Pell và đa thức Chebyshev: Cụ thể, nếu Ti (x) và Ui (x) là đa thức Chebyshev loại Iđa thức Chebyshev loại II. Thì các đa thức thỏa mãn phương trình Pell trong vành đa số thực R[x], với  n = x^2-1 .

T_i^2 - (x^2-1) U_{i-1}^2 = 1. \,

Như vậy, có thể sử dụng các kĩ thuật giải phương trình Pell, để tìm công thức tổng quát và truy hồi của đa thức Chebyshev.

T_i + U_{i-1} \sqrt{x^2-1} = (x + \sqrt{x^2-1})^i. \,

Ngược lại, thay x = x1 vào ta có:

T_i(x_1) + U_{i-1}(x_1) \sqrt{x_1^2-1} = (x_1 + \sqrt{x_1^2-1})^i. \,

với  \sqrt{x_1^2-1} = y_1\sqrt d ,

T_i(x_1) + U_{i-1}(x_1) y_1\sqrt d = x_i + y_i\sqrt d. \,

Do đó, xi = Ti (x1) và yi = y1Ui − 1(x1) (Barbeau, chapter 3).

Phân số liên tục[sửa | sửa mã nguồn]

Các biến thể khác của phương trình Pell[sửa | sửa mã nguồn]

Xét phương trình Pell biến thể:

 u^2 - dv^2 = \pm k

với k là số tự nhiên lớn hơn 1.

I. k=2

 u^2 - dv^2 = \pm 2 (eq.3)

Legendre đã chứng minh rằng nếu d là số nguyên tố có dạng 4m+3 thì phương trình (eq3)có nghiệm, cụ thể hơn:

nếu d là số nguyên tố có dạng 8m+3, phương trình sau có nghiệm  u^2 - dv^2 = -2
nếu d là số nguyên tố có dạng 8m+7, phương trình sau có nghiệm  u^2 - dv^2 = +2 .

Phương trình (eq3) có các nghiệm liên hệ với phương trình Pell ở dạng chính tắc. Thật vậy, nếu ta bình phương hai vế của nó:

 (u^2-dv^2)^2 = (\pm 2)^2
 (u^2+dv^2)^2 - 4d(uv)^2 = 4

Thay  dv^2 = u^2 \mp 2 ta được

 (2u^2 \mp 2)^2 - 4d(uv)^2 = 4
 (u^2 \mp 1)^2 - d(uv)^2 = 1 .

Như vậy nếu (u,v) là nghiệm của phương trình: u^2 - dv^2 = \pm 2 , thì  (x,y) = (u^2\mp1, uv) là nghiệm của phương trình Pell chính tắc sau  x^2 - dy^2 = 1 . Ví dụ với d=3, (u,v) = (1,1) là nghiệm của  u^2 - 3v^2 = -2 , thì (x,y) = (2,1) là nghiệm của  x^2-3v^2 = 1 .

II. k = 4:

 u^2 - dv^2 = \pm 4 \, (eq.4)

Từ nghiệm của (eg.4) có thể tìm ra nghiệm của phương trình Pell chính tắc (cả Pell âm) với d tương ứng. Xem dạng biến thể [3], nếu nghiệm {u,v} đều là lẻ, thì có thể tìm được nghiệm cơ bản {x,y}.

1. Nếu u2-dv2 = -4, và {x,y} = {(u2+3)u/2, (u2+1)v/2}, thì x2-dy2 = -1.

Ví dụ: Cho d = 13, thì {u,v} = {3, 1}và {x,y} = {18, 5}.

2. Nếu u2-dv2 = 4, và {x,y} = {(u2-3)u/2, (u2-1)v/2}, thì x2-dy2 = 1.

Ví dụ. Cho d = 13, thì {u,v} = {11, 3} và {x,y} = {649, 180}.

3. Nếu u2-dv2 = -4, và {x,y} = {(u4+4u2+1)(u2+2)/2, (u2+3)(u2+1)uv/2}, thì x2-dy2 = 1.

Ví dụ. Cho d = 61, thì {u,v} = {39, 5} và {x,y} = {1766319049, 226153980}.

III.  k = a^2

Nếu (x,y) là nghiệm của phương trình  x^2 - dy^2 = \pm 1 thì (u,v) = (ax, ay) là nghiệm của  u^2 - dv^2 = \pm a^2 .

Xem thêm[sửa | sửa mã nguồn]

Phương trình Đi-ô-phăng

Số chính phương

Phân số liên tục

Bài toán đàn gia súc Archimedes

Ghi chú[sửa | sửa mã nguồn]

  1. ^ Solution d'un Probleme d'Arithmetique, in Oeuvres, t.1, 671–732
  2. ^ Một số chuyên đề bồi dưỡng toán học học sinh giỏi, chuyên đề "liên phân số" - Đặng Hùng Thắng, Hà Nội 2004
  3. ^ A Collection Of Identities: Pell Equations

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]