Bài toán (Định lí về cấu trúc nghiệm của phương trình Pell loại 1) Cho $d$ là số nguyên dương không chính phương. Xét phương trình $x^2-dy^2=1\;\;\;(1)$. Gỉa sử $(a,b)$ là nghiệm nguyên dương nhỏ nhất (nghiệm cơ sở) của $(1)$. Xét hai dãy số $(x_n),(y_n)$ như sau : \[\left\{\begin{matrix} x_1=a,y_1=b\\ x_{n+1}=ax_n+dby_n\\ y_{n+1}=bx_n+ay_n \end{matrix}\right.\] Chứng minh rằng $(x,y)$ là một nghiệm của $(1)$ khi và chỉ khi tồn tại số nguyên dương $n$ sao cho $x=x_n,y=y_n$. Lời giải : Ta chứng minh với mọi $n$ thì $(x_n,y_n)$ là nghiệm của $(1)$. Thực vậy, ta có : Với $n=1$ thì hiển nhiên. Gỉa sử $(x_n,y_n)$ là nghiệm của $(1)$. Xét với $n+1$ : \[x_{n+1}^2-dy_{n+1}^2=(ax_n+dby_n)^2-d(bx_n+ay_n)^2=(a^2-db^2)x_n^2-dy_n^2(a^2-db^2)=x_n^2-dy_n^2=1\] Vậy $(x_{n+1},y_{n+1})$ cũng là nghiệm của $(1)$. Quy nạp xong. Ta chứng minh xong một chiều. Bây giờ ta sẽ chứng minh nếu $(x,y)$ là một nghiệm của $(1)$ thì tồn tại số nguyên dương $n$ sao cho $x=x_n,y=y_n$. Nếu $x=a$ thì $y=b$, khi đó tồn tại $n=1$ để $(x,y)=(a,b)=(x_1,y_1)$. Do $(a,b)$ là nghiệm nhỏ nhất của $(1)$ nên ta xét $x>a$. Ta chọn cặp $(u_1,v_1)=(ax-dby,bx-ay)$. Ta chứng minh $u_1,v_1$ đều nguyên dương. Thực vậy, ta có : \[\left\{\begin{matrix} a^2-db^2=1> 0\\ x^2-dy^2=1> 0 \end{matrix}\right.\Rightarrow a> b\sqrt{d},x> y\sqrt{d}\Rightarrow ax> bdy\] Và : \[\left\{\begin{matrix} a^2-db^2=1\\ x^2-dy^2=1\end{matrix}\right.\Rightarrow \left\{\begin{matrix} a^2y^2-db^2y^2=y^2\\ b^2x^2-db^2y^2=b^2 \end{matrix}\right.\] Chú ý vì $b<y$ nên $bx>ay$. Như vậy $(u_1,v_1)$ nguyên dương. Lại có : \[u_1^2-dv_1^2=(ax-dby)^2-d(bx-ay)^2=(a^2-db^2)x^2-dy^2(a^2-db^2)=x^2-dy^2=1\] Tức là $(u_1,v_1)$ cũng là một nghiệm nguyên dương của $(1)$. Chú ý vì ta có : \[u_1+v_1=(a+b)x-(a+bd)y< a(x-y)+b(x-dy)< x(x-y)+y(x-dy)=x^2-dy^2=1< x+y\] Tương tự nếu chọn $(u_2,v_2)=(au_1-dbv_1,bu_1-av_1)$ thì $(u_2,v_2)$ cũng là một nghiệm nguyên dương của $(1)$ và ta cũng có : \[u_2+v_2<u_1+v_1<x+y\]. Cứ tiếp tục quá trình này ta được : \[...< u_i+v_i<...<u_1+v_1<x+y\] Hơn nữa $x+y$ bị chặn dưới bởi $a+b$ nên chắc chắn phải tồn tại $k$ sao cho $u_k+v_k=a+b$, chú ý vì $(a,b)$ là nghiệm nhỏ nhất nên $u_k=a=x_1,v_k=b=y_1$. Dễ thấy $(u_n)(v_n)$ được xác định như sau : \[\left\{\begin{matrix} u_n=au_{n-1}-dbv_{n-1}\\ v_n=bu_{n-1}-av_{n-1} \end{matrix}\right.\Leftrightarrow \left\{\begin{matrix} u_{n-1}=au_n+bdv_n\\ v_{n-1}=bu_n+av_n \end{matrix}\right.\] Từ đó : \[u_{k-1}=au_{k}+bdv_k=ax_1+bdy_1=x_2,v_{k-1}=bu_k+av_k=bx_1+ay_1=y_2\] \[u_{k-2}=au_{k-1}+bdv_{k-1}=ax_2+bdy_2=x_3,v_{k-2}=bu_{k-1}+av_{k-1}=y_3\] \[...\] \[u_{1}=au_2+bdv_2=ax_{k-1}+bdy_{k-1}=x_k,v_1=bu_2+av_2=bx_{k-1}+bdy_{k-1}=y_k\] Ta có : \[\left\{\begin{matrix} u_1=ax-dby\\ v_1=bx-ay \end{matrix}\right.\Rightarrow \left\{\begin{matrix} x=au_1+bdv_1=ax_k+bdv_k=x_{k+1}\\ y=bu_1+av_1=bx_k+ay_k=y_{k+1} \end{matrix}\right.\] Chiều ngược lại của định lí cũng được chứng minh. Ta hoàn tất vấn đề. Có thể thấy một ứng dụng đẹp của định lí này là bài thi VMO 1999.

Định lí về cấu trúc nghiệm của phương trình Pell loại 1

Bài toán (Định lí về cấu trúc nghiệm của phương trình Pell loại 1)

Cho $d$ là số nguyên dương không chính phương. Xét phương trình $x^{2} - d y^{2} = 1 (1)$ . Gỉa sử $(a, b)$ là nghiệm nguyên dương nhỏ nhất (nghiệm cơ sở) của $(1)$ . Xét hai dãy số $(x_{n}), (y_{n})$ như sau :

$⎩ ⎨ ⎧ x_{1} = a, y_{1} = b x_{n + 1} = a x_{n} + d b y_{n} y_{n + 1} = b x_{n} + a y_{n}$

Chứng minh rằng $(x, y)$ là một nghiệm của $(1)$ khi và chỉ khi tồn tại số nguyên dương $n$ sao cho $x = x_{n}, y = y_{n}$ .

Lời giải :

Ta chứng minh với mọi $n$ thì $(x_{n}, y_{n})$ là nghiệm của $(1)$ . Thực vậy, ta có :

Với $n = 1$ thì hiển nhiên. Gỉa sử $(x_{n}, y_{n})$ là nghiệm của $(1)$ . Xét với $n + 1$ :

$x_{n + 1}^{2} - d y_{n + 1}^{2} = (a x_{n} + d b y_{n})^{2} - d (b x_{n} + a y_{n})^{2} = (a^{2} - d b^{2}) x_{n}^{2} - d y_{n}^{2} (a^{2} - d b^{2}) = x_{n}^{2} - d y_{n}^{2} = 1$

Vậy $(x_{n + 1}, y_{n + 1})$ cũng là nghiệm của $(1)$ . Quy nạp xong. Ta chứng minh xong một chiều.

Bây giờ ta sẽ chứng minh nếu $(x, y)$ là một nghiệm của $(1)$ thì tồn tại số nguyên dương $n$ sao cho $x = x_{n}, y = y_{n}$ .

Nếu $x = a$ thì $y = b$ , khi đó tồn tại $n = 1$ để $(x, y) = (a, b) = (x_{1}, y_{1})$ . Do $(a, b)$ là nghiệm nhỏ nhất của $(1)$ nên ta xét $x > a$ .

Ta chọn cặp $(u_{1}, v_{1}) = (a x - d b y, b x - a y)$ . Ta chứng minh $u_{1}, v_{1}$ đều nguyên dương. Thực vậy, ta có :

${a^{2} - d b^{2} = 1 > 0 x^{2} - d y^{2} = 1 > 0 \Rightarrow a > b d, x > y d \Rightarrow a x > b d y$

Và :

${a^{2} - d b^{2} = 1 x^{2} - d y^{2} = 1 \Rightarrow {a^{2} y^{2} - d b^{2} y^{2} = y^{2} b^{2} x^{2} - d b^{2} y^{2} = b^{2}$

Chú ý vì $b < y$ nên $b x > a y$ . Như vậy $(u_{1}, v_{1})$ nguyên dương. Lại có :

$u_{1}^{2} - d v_{1}^{2} = (a x - d b y)^{2} - d (b x - a y)^{2} = (a^{2} - d b^{2}) x^{2} - d y^{2} (a^{2} - d b^{2}) = x^{2} - d y^{2} = 1$

Tức là $(u_{1}, v_{1})$ cũng là một nghiệm nguyên dương của $(1)$ .

Chú ý vì ta có :

$u_{1} + v_{1} = (a + b) x - (a + b d) y < a (x - y) + b (x - d y) < x (x - y) + y (x - d y) = x^{2} - d y^{2} = 1 < x + y$

Tương tự nếu chọn $(u_{2}, v_{2}) = (a u_{1} - d b v_{1}, b u_{1} - a v_{1})$ thì $(u_{2}, v_{2})$ cũng là một nghiệm nguyên dương của $(1)$ và ta cũng có :

$u_{2} + v_{2} < u_{1} + v_{1} < x + y$ .

Cứ tiếp tục quá trình này ta được :

$... < u_{i} + v_{i} < ... < u_{1} + v_{1} < x + y$

Hơn nữa $x + y$ bị chặn dưới bởi $a + b$ nên chắc chắn phải tồn tại $k$ sao cho $u_{k} + v_{k} = a + b$ , chú ý vì $(a, b)$ là nghiệm nhỏ nhất nên $u_{k} = a = x_{1}, v_{k} = b = y_{1}$ .

Dễ thấy $(u_{n}) (v_{n})$ được xác định như sau :

${u_{n} = a u_{n - 1} - d b v_{n - 1} v_{n} = b u_{n - 1} - a v_{n - 1} \Leftrightarrow {u_{n - 1} = a u_{n} + b d v_{n} v_{n - 1} = b u_{n} + a v_{n}$

Từ đó :

$u_{k - 1} = a u_{k} + b d v_{k} = a x_{1} + b d y_{1} = x_{2}, v_{k - 1} = b u_{k} + a v_{k} = b x_{1} + a y_{1} = y_{2}$

$u_{k - 2} = a u_{k - 1} + b d v_{k - 1} = a x_{2} + b d y_{2} = x_{3}, v_{k - 2} = b u_{k - 1} + a v_{k - 1} = y_{3}$

$...$

$u_{1} = a u_{2} + b d v_{2} = a x_{k - 1} + b d y_{k - 1} = x_{k}, v_{1} = b u_{2} + a v_{2} = b x_{k - 1} + b d y_{k - 1} = y_{k}$

Ta có :

${u_{1} = a x - d b y v_{1} = b x - a y \Rightarrow {x = a u_{1} + b d v_{1} = a x_{k} + b d v_{k} = x_{k + 1} y = b u_{1} + a v_{1} = b x_{k} + a y_{k} = y_{k + 1}$

Chiều ngược lại của định lí cũng được chứng minh. Ta hoàn tất vấn đề.

Có thể thấy một ứng dụng đẹp của định lí này là bài thi VMO 1999.

Định lí về cấu trúc nghiệm của phương trình Pell loại 1

Đề bài

Mô tả