Pell’s equation II

Các bạn có thể xem phần đầu về phương trình Pell ở đây: https://nttuan.org/2007/12/15/pell-equation/

Cho $d$ là số nguyên dương không phải là số chính phương. Xét phương trình Pell âm

$\displaystyle x^2-dy^2=-1. \qquad (1)$

Định lý 1. Nếu $(x_1,y_1)$ và $(x_2,y_2)$ là hai nghiệm nguyên dương của (1) thì

$\displaystyle x_1<x_2 \Longleftrightarrow y_1<y_2 \Longleftrightarrow x_1+y_1\sqrt d<x_2+y_2\sqrt d.$

Chứng minh. Từ giả thiết, ta có

$\displaystyle (x_2-x_1)(x_2+x_1)=d(y_2-y_1)(y_2+y_1).$

Vì $x_1+x_2>0$ và $d(y_1+y_2)>0$ , hai hiệu $x_2-x_1$ và $y_2-y_1$ cùng dấu hoặc đồng thời bằng $0$ . Do đó tổng $(x_2-x_1)+(y_2-y_1)\sqrt d$ cũng cùng dấu với hai hiệu ấy. Các tương đương cần chứng minh suy ra ngay. $\Box$

Định lý 2. Giả sử (1) có nghiệm nguyên dương và $(x',y')$ là nghiệm có $x'$ nhỏ nhất. Khi đó cặp $(X_0,Y_0)$ xác định bởi

$\displaystyle X_0+Y_0\sqrt d=(x'+y'\sqrt d)^2$

là nghiệm cơ bản của phương trình $x^2-dy^2=1$ , tức là nghiệm nguyên dương có hoành độ nhỏ nhất.

Chứng minh. Đặt $\alpha=x'+y'\sqrt d>1$ . Ta có

$\displaystyle \alpha^{-1}=-x'+y'\sqrt d.$

Rõ ràng $X_0=x'^2+dy'^2$ và $Y_0=2x'y'$ là các số nguyên dương thỏa mãn $X_0^2-dY_0^2=1$ . Nếu đây chưa phải là nghiệm cơ bản thì tồn tại một nghiệm nguyên dương $(a,b)$ của phương trình này sao cho

$\displaystyle 1<\varepsilon=a+b\sqrt d<\alpha^2.$

Đặt

$\displaystyle \beta=\frac{\varepsilon}{\alpha}=(a+b\sqrt d)(-x'+y'\sqrt d)=u+v\sqrt d,$

với $u,v\in\mathbb Z$ . Khi đó

$\displaystyle u^2-dv^2=-1,\qquad \alpha^{-1}<\beta<\alpha.$

Do $u-v\sqrt d=-\beta^{-1}$ , ta có $v=(\beta+\beta^{-1})/(2\sqrt d)>0$ . Hơn nữa, $u\ne0$ , vì $u=0$ sẽ dẫn đến $dv^2=1$ , trái với $d\ge2$ . Vì vậy $(|u|,v)$ là một nghiệm nguyên dương của (1), nhưng

$\displaystyle |u|+v\sqrt d=\max\{\beta,\beta^{-1}\}<\alpha=x'+y'\sqrt d.$

Theo Định lý 1, điều này mâu thuẫn với tính nhỏ nhất của $x'$ . Vậy $(X_0,Y_0)$ là nghiệm cơ bản của phương trình $x^2-dy^2=1$ . $\Box$

Định lý 3. Giả sử (1) có nghiệm nguyên dương và $(x',y')$ là nghiệm có $x'$ nhỏ nhất. Khi đó tất cả các nghiệm nguyên dương của (1) là $(x_n,y_n)$ , với

$\displaystyle x_n+y_n\sqrt d=(x'+y'\sqrt d)^{2n+1},\qquad n=0,1,2,\ldots.$

Cặp $(x',y')$ được gọi là nghiệm cơ bản của phương trình Pell âm (1).

Chứng minh. Đặt $\alpha=x'+y'\sqrt d$ . Với mỗi $n\ge0$ , khai triển nhị thức cho thấy $x_n,y_n$ là các số nguyên dương. Đồng thời,

$\displaystyle x_n^2-dy_n^2=(x'^2-dy'^2)^{2n+1}=-1.$

Ngược lại, cho $(a,b)$ là một nghiệm nguyên dương bất kỳ của (1). Theo Định lý 1, $a+b\sqrt d\ge\alpha$ . Vì $\alpha>1$ , tồn tại số nguyên $n\ge0$ sao cho

$\displaystyle \alpha^{2n+1}\le a+b\sqrt d<\alpha^{2n+3}.$

Đặt

$\displaystyle \gamma=\frac{a+b\sqrt d}{\alpha^{2n+1}}=u+v\sqrt d.$

Vì $\alpha^{-1}=-x'+y'\sqrt d$ , ta có $u,v\in\mathbb Z$ . Hơn nữa,

$\displaystyle u^2-dv^2=1,\qquad 1\le\gamma<\alpha^2.$

Nếu $\gamma>1$ thì $u-v\sqrt d=\gamma^{-1}$ , nên

$\displaystyle u=\frac{\gamma+\gamma^{-1}}2>0,\qquad v=\frac{\gamma-\gamma^{-1}}{2\sqrt d}>0.$

Khi đó $(u,v)$ là một nghiệm nguyên dương của phương trình $x^2-dy^2=1$ với $u+v\sqrt d<\alpha^2$ , trái với Định lý 2. Vậy $\gamma=1$ , tức là $a+b\sqrt d=\alpha^{2n+1}$ . Do $\sqrt d$ vô tỉ, suy ra $(a,b)=(x_n,y_n)$ . $\Box$

Nhận xét. Phương trình Pell âm có thể vô nghiệm nguyên. Chẳng hạn, $x^2-3y^2=-1$ vô nghiệm, vì khi lấy modulo $3$ ta được $x^2\equiv2\pmod3$ , điều không thể xảy ra.

Cardinality of Sets and Countability

Với một tập hợp hữu hạn, ta đo kích thước của nó bằng số phần tử. Đối với các tập hợp vô hạn, việc so sánh kích thước được thực hiện thông qua các song ánh.

card Download

Existence of Non-Trivial Solutions in Homogeneous Linear Systems

Định lý. Cho hai số nguyên dương $N>M$ và một bảng các số thực (phức, hữu tỷ) $(a_{i,j})$ có cỡ $M\times N$ . Khi đó, hệ phương trình

$\displaystyle \sum_{j=1}^Na_{i,j}x_j=0,\quad i=1,2,\ldots,M$

luôn có nghiệm thực (tương ứng phức, hữu tỷ) không tầm thường.

Chứng minh. Ta chứng minh đồng thời cho các hệ có hệ số trong mỗi trường $\mathbb K\in\{\mathbb Q,\mathbb R,\mathbb C\}$ bằng quy nạp theo số phương trình $M$ .

Với $M=1$ , ta có $N\ge2$ . Nếu mọi hệ số $a_{1,j}$ đều bằng $0$ thì có thể lấy $(x_1,\ldots,x_N)=(1,0,\ldots,0)$ . Nếu không, chọn $k$ sao cho $a_{1,k}\ne0$ và chọn $\ell\ne k$ . Đặt

$\displaystyle x_\ell=1,\qquad x_k=-\frac{a_{1,\ell}}{a_{1,k}},\qquad x_j=0\quad(j\notin\{k,\ell\}).$

Đây là một nghiệm không tầm thường.

Giả sử kết luận đúng với mọi hệ gồm $M-1$ phương trình và có số ẩn lớn hơn $M-1$ . Xét hệ gồm $M$ phương trình với $N>M$ . Nếu phương trình thứ $M$ có mọi hệ số bằng $0$ , bỏ phương trình ấy rồi áp dụng giả thiết quy nạp.

Trong trường hợp còn lại, bằng cách đổi thứ tự các ẩn, ta có thể giả sử $a_{M,N}\ne0$ . Từ phương trình thứ $M$ , suy ra

$\displaystyle x_N=-\sum_{j=1}^{N-1}\frac{a_{M,j}}{a_{M,N}}x_j.$

Thay vào $M-1$ phương trình đầu, ta được hệ thuần nhất

$\displaystyle \sum_{j=1}^{N-1} \left(a_{i,j}-\frac{a_{i,N}a_{M,j}}{a_{M,N}}\right)x_j=0, \qquad i=1,\ldots,M-1.$

Hệ này có $N-1>M-1$ ẩn và các hệ số vẫn thuộc $\mathbb K$ . Theo giả thiết quy nạp, nó có nghiệm $(x_1,\ldots,x_{N-1})$ không tầm thường. Xác định $x_N$ bằng công thức trên, ta thu được một nghiệm của hệ ban đầu. Nghiệm này không tầm thường vì ít nhất một trong các số $x_1,\ldots,x_{N-1}$ khác $0$ .

Vậy kết luận đúng với mọi $M<n$ . $\Box$

Đây là một kết quả hữu ích khác về hệ phương trình tuyến tính nhiều ẩn https://nttuan.org/2007/10/21/siegel/

Continuous Solutions of d’Alembert’s Functional Equation

Dưới đây là một tài liệu trình bày trọn vẹn các bước chứng minh cho phương trình hàm d’Alembert đối với lớp hàm liên tục. Tài liệu gồm hai phần chính: Định lý 1 cho hàm liên tục $f:\mathbb{R}\to\mathbb{R}$ và Định lý 2 mở rộng cho hàm dương $f:(0,+\infty)\to(0,+\infty)$ .

dAlembert.feq Download

Useful Lemmas on Real Polynomials, Part III

Các bạn xem phần trước ở https://nttuan.org/2011/02/13/realpoly02/

Bổ đề 7. Cho $P(x)$ là một đa thức khác đa thức hằng với hệ số thực. Giả sử bậc của $P$ là chẵn và hệ số cao nhất của nó nhỏ hơn $0$ . Khi đó tồn tại số nguyên dương $K$ thỏa mãn đồng thời các điều kiện sau:

(1) hàm số đa thức $P(x)$ đồng biến trên khoảng $(-\infty;-K]$ và nghịch biến trên khoảng $[K;+\infty)$ ;

(2) với mỗi $x>K$ và $y \in [0; K]$ , ta có $P(x)< P(y)$ ;

(3) với mỗi $x<-K$ và $y \in [-K; 0]$ thì $P(x)< P(y)$ .

Chứng minh. Giả sử đa thức có dạng $P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$ , trong đó $n$ là số nguyên dương chẵn và $a_n < 0$ .

Xét đạo hàm của đa thức: $P'(x) = n a_n x^{n-1} + (n-1) a_{n-1} x^{n-2} + \dots + a_1$ . Vì $n$ là số chẵn nên $n-1$ là số lẻ. Đồng thời, do $a_n < 0$ nên hệ số bậc cao nhất của đa thức đạo hàm là $n a_n < 0$ . Do $P'(x)$ là đa thức bậc lẻ với hệ số cao nhất âm, giới hạn của nó ở hai đầu vô cực là $\lim_{x\to +\infty} P'(x) = -\infty$ và $\lim_{x\to -\infty} P'(x) = +\infty.$

Theo định nghĩa của giới hạn, tồn tại một số thực dương $M$ đủ lớn sao cho với mọi $x \ge M$ ta có $P'(x) < 0$ , và với mọi $x \le -M$ ta có $P'(x) > 0$ . Điều này có nghĩa là hàm số $P(x)$ nghịch biến ngặt trên khoảng $[M; +\infty)$ và đồng biến ngặt trên khoảng $(-\infty; -M]$ .

Vì hàm đa thức $P(x)$ liên tục trên các đoạn $[-M; 0]$ và $[0; M]$ , nó sẽ đạt giá trị nhỏ nhất trên từng đoạn này. Gọi $C_1 = \min_{x \in [0; M]} P(x)$ và $C_2 = \min_{x \in [-M; 0]} P(x)$ .

Mặt khác, vì bậc $n$ chẵn và $a_n < 0$ , giới hạn của đa thức $P(x)$ ở cả hai đầu vô cực đều là âm vô cực:

$\lim_{x\to \pm\infty} P(x) = -\infty.$

Dựa vào hai giới hạn này, ta có thể tìm được các số thực dương $M_1$ và $M_2$ lớn hơn $M$ sao cho: Với mọi $x \ge M_1$ , ta có $P(x) < C_1$ . Với mọi $x \le -M_2$ , ta có $P(x) < C_2$ .

Bây giờ, ta chọn $K$ là một số nguyên dương sao cho $K > \max\{M_1, M_2\}$ . Ta sẽ chứng minh $K$ thỏa mãn cả ba điều kiện của bổ đề.

Thứ nhất, vì $K > M$ nên hai khoảng $(-\infty; -K]$ và $[K; +\infty)$ lần lượt là tập con của $(-\infty; -M]$ và $[M; +\infty)$ . Do $P(x)$ đồng biến trên khoảng $(-\infty; -M]$ và nghịch biến trên khoảng $[M; +\infty)$ , nó cũng đồng biến trên khoảng $(-\infty; -K]$ và nghịch biến trên khoảng $[K; +\infty)$ . Điều kiện (1) được thỏa mãn.

Thứ hai, xét $x > K$ và $y \in [0; K]$ , ta chia thành hai trường hợp đối với $y$ :

Nếu $y \in [0; M]$ : Vì $x > K > M_1$ nên theo cách chọn $M_1$ , ta có $P(x) < C_1$ . Mặt khác $y \in [0; M]$ nên $P(y) \ge C_1$ . Suy ra $P(x) < P(y)$ .
Nếu $y \in (M; K]$ : Cả $x$ và $y$ đều thuộc khoảng $[M; +\infty)$ , nơi $P(x)$ nghịch biến. Vì $x > y$ nên $P(x) < P(y)$ .

Như vậy, với mọi $x > K$ và $y \in [0; K]$ , ta luôn có $P(x) < P(y)$ . Điều kiện (2) được thỏa mãn.

Thứ ba, xét $x < -K$ và $y \in [-K; 0]$ , ta cũng chia thành hai trường hợp đối với $y$ :

Nếu $y \in [-M; 0]$ : Vì $x < -K < -M_2$ nên theo cách chọn $M_2$ , ta có $P(x) < C_2$ . Trong khi đó $y \in [-M; 0]$ nên $P(y) \ge C_2$ . Suy ra $P(x) < P(y)$ .
Nếu $y \in [-K; -M)$ : Cả $x$ và $y$ đều thuộc khoảng $(-\infty; -M]$ , nơi $P(x)$ đồng biến. Do $x < y$ nên $P(x) < P(y)$ .

Như vậy, với mọi $x < -K$ và $y \in [-K; 0]$ , ta luôn có $P(x) < P(y)$ . Điều kiện (3) được thỏa mãn. $\Box$

Bổ đề 8. Cho $P(x)$ là một đa thức khác đa thức hằng với hệ số thực. Giả sử bậc của $P$ là $n$ . Khi đó tồn tại số nguyên dương $K$ và hai số thực dương $C_1$ , $C_2$ sao cho

$C_1|x|^n\leq |P(x)|\leq C_2|x|^n$

với mọi số thực $x$ thỏa mãn $|x|\geq K$ .

Chứng minh. Giả sử đa thức có dạng

$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0,$

trong đó $a_n \neq 0$ . Với mọi $x \neq 0$ , ta có

$\frac{P(x)}{x^n} = a_n + \frac{a_{n-1}}{x} + \dots + \frac{a_1}{x^{n-1}} + \frac{a_0}{x^n}.$

Từ đó ta có đánh giá

$\left| \frac{P(x)}{x^n} - a_n \right| = \left| \frac{a_{n-1}}{x} + \dots + \frac{a_1}{x^{n-1}} + \frac{a_0}{x^n} \right| \le \frac{|a_{n-1}|}{|x|} + \dots + \frac{|a_1|}{|x|^{n-1}} + \frac{|a_0|}{|x|^n}.$

Do $\lim_{|x|\to +\infty} \left( \frac{|a_{n-1}|}{|x|} + \dots + \frac{|a_1|}{|x|^{n-1}} + \frac{|a_0|}{|x|^n} \right) = 0$ , theo định nghĩa của giới hạn, tồn tại một số thực dương $M$ đủ lớn sao cho với mọi $x$ thỏa mãn $|x| \ge M$ , ta luôn có:

$\frac{|a_{n-1}|}{|x|} + \dots + \frac{|a_1|}{|x|^{n-1}} + \frac{|a_0|}{|x|^n} \le \frac{|a_n|}{2}.$

Ta chọn $K$ là một số nguyên dương sao cho $K \ge M$ . Khi đó, với mọi số thực $x$ thỏa mãn $|x| \ge K$ , ta có:

$\left| \frac{P(x)}{x^n} - a_n \right| \le \frac{|a_n|}{2},$

suy ra

$\frac{|a_n|}{2} \le \frac{|P(x)|}{|x|^n} \le \frac{3|a_n|}{2}.$

Do $x \neq 0$ nên $|x|^n > 0$ . Nhân tất cả các vế của bất đẳng thức với $|x|^n$ , ta được

$\frac{|a_n|}{2} |x|^n \le |P(x)| \le \frac{3|a_n|}{2} |x|^n$

với mọi số thực $x$ thỏa mãn $|x|\geq K$ .

Đặt $C_1 = \frac{|a_n|}{2}$ và $C_2 = \frac{3|a_n|}{2}$ . Vì $a_n \neq 0$ nên $C_1 > 0$ và $C_2 > 0$ . Ta thấy $C_1 |x|^n \le |P(x)| \le C_2 |x|^n$

với mọi $x$ thỏa mãn $|x| \ge K$ .

Điều này hoàn tất việc chứng minh bổ đề. $\Box$

Bổ đề 9. Cho $P(x)$ là một đa thức khác đa thức hằng với hệ số thực, có bậc chẵn và hệ số cao nhất dương. Khi đó tồn tại số nguyên dương $k$ và số nguyên dương $C$ sao cho

$P(-x-k) > P(x) > P(-x+k),\quad\forall x>C.$

Chứng minh. Giả sử đa thức có dạng

$P(x) = a_{2n} x^{2n} + a_{2n-1} x^{2n-1} + \dots + a_1 x + a_0,$

trong đó $n$ là số nguyên dương và $a_{2n} > 0$ .

Xét hiệu $H_1(x) = P(-x-k) - P(x)$ với $k$ là một số nguyên dương sẽ được chọn sau. Theo định lý nhị thức, ta có

$(-x-k)^{2n} = (x+k)^{2n} = x^{2n} + 2nk x^{2n-1} + \dots$

và

$(-x-k)^{2n-1} = -(x+k)^{2n-1} = -x^{2n-1} - (2n-1)k x^{2n-2} - \dots$

Suy ra

$P(-x-k) = a_{2n} x^{2n} + (2n k a_{2n} - a_{2n-1}) x^{2n-1} + R_1(x),$

với $R_1(x)$ là một đa thức có bậc không vượt quá $2n-2$ . Từ đó, ta có

$H_1(x) = \left[ a_{2n} x^{2n} + (2n k a_{2n} - a_{2n-1}) x^{2n-1} + R_1(x) \right] - \left[ a_{2n} x^{2n} + a_{2n-1} x^{2n-1} + \dots \right]$

$= 2(n k a_{2n} - a_{2n-1}) x^{2n-1} + S_1(x),$

trong đó $S_1(x)$ là đa thức có bậc không vượt quá $2n-2$ .

Hoàn toàn tương tự, xét hiệu $H_2(x) = P(x) - P(-x+k)$ . Theo định lý nhị thức, ta có

$(-x+k)^{2n} = (x-k)^{2n} = x^{2n} - 2nk x^{2n-1} + \dots$

và

$(-x+k)^{2n-1} = -(x-k)^{2n-1} = -x^{2n-1} + \dots$

Suy ra

$P(-x+k) = a_{2n} x^{2n} - (2n k a_{2n} + a_{2n-1}) x^{2n-1} + R_2(x),$

với $R_2(x)$ là một đa thức có bậc không vượt quá $2n-2$ . Từ đó ta có

$H_2(x) = \left[ a_{2n} x^{2n} + a_{2n-1} x^{2n-1} + \dots \right] - \left[ a_{2n} x^{2n} - (2n k a_{2n} + a_{2n-1}) x^{2n-1} + R_2(x) \right]$

$= 2(n k a_{2n} + a_{2n-1}) x^{2n-1} + S_2(x),$

với $S_2(x)$ là đa thức có bậc không vượt quá $2n-2$ .

Đến đây ta chọn $k > \left| \frac{a_{2n-1}}{n a_{2n}} \right|$ . Với $k$ được chọn như vậy, $H_1(x)$ và $H_2(x)$ đều là các đa thức có bậc lẻ $2n-1$ , hệ số của $x^{2n-1}$ ở cả hai đa thức đều là số dương. Theo tính chất giới hạn của hàm đa thức, tồn tại các số thực dương $C_1, C_2$ sao cho $H_1(x) > 0$ với mọi $x > C_1$ và $H_2(x) > 0$ với mọi $x > C_2$ .

Chọn số nguyên dương $C = \lfloor \max\{C_1, C_2\} \rfloor + 1$ . Khi đó, với mọi số thực $x > C$ , ta có đồng thời $H_1(x) > 0$ và $H_2(x) > 0$ , tức là