PHƯƠNG PHÁP GEN TRONG GIẢI PHƯƠNG TRÌNH NGHIỆM NGUYÊN
Trong Sinh học ta định nghĩa gen hay di tố là một đoạn DNA mang một chức năng nhất định trong quá trình truyền thông tin di truyền. Tương tự như vậy, trong Toán học, phương pháp gen trong giải phương trình nghiệm nguyên chủ yếu là cho ta cấu trúc nghiệm của nó. Nếu từ một nghiệm của phương trình đã cho, ta xây dựng quy tắc nghiệm của nó. Phương trình Pell và phương trình Markov chính là hai ví dụ điển hình cho phương pháp này.
I. Phương trình Pell:
1. Phương trình Pell loại I:
Phương trình Pell loại I là phương trình nghiệm nguyên có dạng: $$x^2-dy^2=1,\,d\in\mathbb{Z}\;\;\;\;\;\;\;\;\;\;\;(1)$$
Tính chất:
1. Nếu $d$ là số chính phương thì phương trình $(1)$ vô nghiệm.
2. Nếu $d$ là số nguyên âm thì phương trình $(1)$ không có nghiệm nguyên dương.
3. Phương trình Pell loại I có nghiệm nguyên dương khi và chỉ khi $d$ là số nguyên dương và không chính phương.
$*$ Công thức nghiệm của phương trình Pell loại I:
Ta xét trong trường hợp phương trình Pell loại I nhận các nghiệm nguyên dương (tức là $x, y\in\mathbb{Z^+}$). Gọi $(a, b)$ là hai cặp nghiệm bé nhất của phương trình Pell loại I. Khi đó công thức nghiệm của phương trình này được xác định bởi công thức tổng quát của dãy $(x_n), (y_n)$: $$\begin{cases}x_n=\dfrac{(a+b\sqrt{d})^n+(a-b\sqrt{d})^n}{2}\\y_n=\dfrac{(a+b\sqrt{d})^n-(a-b\sqrt{d})^n}{2\sqrt{d}}\end{cases}$$ hay theo công thức truy hồi: $$\begin{cases}x_0=1, y_0=0\\x_1=a, y_1=b\\x_{n+2}=2ax_{n+1}-x_n\\y_{n+2}=2ay_{n+1}-y_n\end{cases}$$
2. Phương trình Pell loại II:
Phương trình Pell loại II là phương trình nghiệm nguyên có dạng: $$x^2-dy^2=-1, d\in\mathbb{Z}\;\;\;\;\;\;\;\;\;\;\;\;\;(2)$$
Tính chất:
1. Nếu $d$ là số chính phương thì $(2)$ vô nghiệm.
2. Nếu $d$ có ước nguyên tố dạng $4k+3$ thì $(2)$ vô nghiệm.
3. Nếu $d$ là số nguyên tố thì $(2)$ có nghiệm khi và chỉ khi $d\neq 4k+3$
4. (Điều kiện có nghiệm của Phương trình Pell loại II) Gọi $(a, b)$ là nghiệm nhỏ nhất của $(2)$. Khi đó, $(2)$ có nghiệm khi và chỉ khi hệ: $$\begin{cases}a=x^2+dy^2\\b=2xy\end{cases}$$ có nghiệm nguyên dương.
$*$ Công thức nghiệm của phương trình Pell loại II:
Xét phương trình Pell loại I liên kết với phương trình $(2)$: $x^2-dy^2=1, d\in\mathbb{Z}$. Gọi $(a, b)$ là nghiệm nhỏ nhất phương trình này. Xét hệ: $$\begin{cases}a=x^2+dy^2\\b=2xy\end{cases}$$ Giả sử hệ này có nghiệm duy nhất và ta gọi $(u, v)$ là nghiệm duy nhất của nó. Khi đó dãy số $(x_n), (y_n)$ sau sẽ vét sạch hết nghiệm của phương trình Pell loại II: $$\begin{cases}x_0=u, y_0=v\\x_1=u^3+duv^2, y_1=dv^3+3u^2v\\x_{n+2}=2ax_{n+1}-y_n\\y_{n+2}=2ay_{n+1}-y_n\end{cases}$$
3. Phương trình Pell với tham số $n$:
Phương trình Pell tham số $n$ có dạng: $$x^2-dy^2=n, d,n\in\mathbb{Z}\,\,\,\,\,\,\,\,\,\,\,\,(3)$$
Tính chất:
1. Phương trình $(3)$ hoặc vô nghiệm hoặc vô số nghiệm.
2. Giả sử $(3)$ có nghiệm và gọi $x_0,y_0)$ là nghiệm nguyên dương nhỏ nhất của nó. Gọi $(a, b)$ là nghiệm nguyên dương nhỏ nhất của phương trình Pell loại I tương ứng: $x^2-dy^2=1, d\in\mathbb{Z}$. Khi đó, ta có: $$y_0^2\le\max\left\{nb^2;-\dfrac{na^2}{d}\right\}$$
3. Giả sử $(3)$ có nghiệm là $(\alpha_1,\beta_1); (\alpha_2, \beta_2);...;(\alpha_m, \beta_m)$ thỏa mãn: $$\beta_i^2\le\max\left\{nb^2,-\dfrac{na^2}{d}\right\}$$ Xét $m$ dãy sau: $$\begin{cases}x_{0,i}=\alpha_i, y_{0,i}=\beta_i\\x_{n+1, i}=ax_{n,i}+day_{n,i}\\y_{n+1,i}=bx_{n,i}+ay_{n,i}\end{cases}$$ Với $(a, b)$ là nghiệm bé nhất của phương trình Pell loại I tương ứng $x^2-dy^2=1$. Đồng thời khi đó các dãy $(x_{n,i}), (y_{n,i})$ sẽ vét hết tất cả các nghiệm của phương trình Pell tham số $n$.
Phương trình Pell là một công cụ rất mạnh trong việc giải quyết các phương trình nghiệm nguyên cũng như số học nói chung. Ta tìm hiểu các ví dụ sau:
II. Bài tập ví dụ:
Bài toán 1: Tìm tất cả các số nguyên dương $x>2$ sao cho tam giác có độ dài ba cạnh là $x-1, x, x+1$ thì diện tích của nó cũng là một số nguyên.
Lời giải:
Giả sử $x$ là giá trị thỏa mãn bài toán. Ta có nửa chu vi tam giác đó là: $\dfrac{x+1+x+x-1}{2}=\dfrac{3}{2}x$. Gọi $y$ là diện tích tam giác đó. Áp dụng công thức Heron, ta có: $$y=\sqrt{\dfrac{3}{2}x\left(\dfrac{3}{2}x-x-1\right)\left(\dfrac{3}{2}x-x\right)\left(\dfrac{3}{2}x-x+1\right)}=\dfrac{1}{4}x\sqrt{3(x^2-4)}\\\Leftrightarrow 16y^2=3x^2(x^2-4)$$ Do $16\;\vdots\; 2\Rightarrow x^2(x^2-4)\;\vdots\; 2\Rightarrow x\;\vdots \;2$. Đặt $x=2k,k\in\mathbb{N^*}$. Theo đó: $$6y^2=3,4k^2(4k^2-4)\\\Leftrightarrow y^2=3k^2(k^2-1)\Rightarrow y=k\sqrt{3(k^2-1)}$$ Chú ý rằng: $k,y\in\mathbb{Z^+}\Rightarrow \sqrt{3(k^2-1)}\in\mathbb{Z^+}$. Do đó tồn tại $l\in\mathbb{Z^+}$ sao cho: $$3(k^2-1)=l^2$$ Rõ ràng $l^2\;\vdots \; 3\Rightarrow l=3m,m\in\mathbb{Z^+}$. Khi đó phương trình trở thành $$k^2-3m^2=1$$ Đây chính là phương trình Pell loại I và công thức nghiệm của nó được xác định bởi: $$\begin{cases}k_0=1, m_0=0\\k_1=2, m_1=1\\k_{n+2}=6k_{n+1}-k_n,\forall n=0,1,2,...\\m_{n+2}=6m_{n+1}-m_n,\forall n=0,1,2,..\end{cases}$$ Suy ra: $$\begin{cases}x_0=2,y_0=1\\x_1=4,y_1=2\\x_{n+2}=4x_{n+1}-x_{n},n=0,1,2,...\\y_{n+2}=4y_{n+1}-y_n,n=0,1,2,...\end{cases}$$ Vậy tất cả giá trị của $x$ thỏa mãn bài toán được xác định bởi dãy: $$\begin{cases}x_0=2, x_1=4\\x_{n+2}=4x_{n+1}-x_n. n=0,1,2...\end{cases}$$.
Bài toán 2: Tìm tất cả các số nguyên dương $n$ sao cho trung bình cộng của $n$ số chính phương đầu tiên là một số chính phương.
Lời giải:
Bằng qui nạp ta chứng minh được rằng: Với mọi Số nguyên dương $n$, ta luôn có: $$1^2+2^2+3^2+ ...+n^2=\dfrac{n(n+1)(2n+1)}{6}$$ Suy ra: $$\dfrac{1^2+2^2+3^2+...+n^2}{n}=\dfrac{(n+1)(2n+1)}{6}$$ Theo đó, ta cần tìm $n, y\in\mathbb{Z^+}$ sao cho: $$\begin{aligned}&\;\;\;\;\dfrac{(n+1)(2n+1)}{6}=y^2\\&\Leftrightarrow n^2+3n+1=6y^2\\&\Leftrightarrow 16n^2+24n+4=48y^2\\&\Leftrightarrow (4n+3)^2-48y^2=1\end{aligned}$$ Đặt $x=4n+3$, thế thì ta thu được: $$x^2-48y^2=1$$ Đây chính là phương trình Pell loại I. Bằng phép thử tuần tự, ta tìm được $(7,1)$ là nghiệm nhỏ nhất của nó. Theo đó, công thức nghiệm của phương trình Pell này là: $$\begin{cases}x_0=1, y_0=0\\x_1=7, y_1=1\\x_{k+2}=14x_{k+1}-x_k, k=0,1,2,...\\y_{k+2}=14y_{k+1}-y_k,k=0,1,2,...\end{cases}$$ Bằng qui nạp, ta chứng minh được rằng: $$\begin{cases}x_{2k}\equiv 1\pmod{4}\\x_{2k+1}\equiv 3\pmod{4}\end{cases}$$ Ngoài ra: $$\begin{aligned}x_{2k+3}=14x_{2k+2}-x_{2k+1}&=14(14x_{2k+1}-x_{2k})-x_{2k+1}\\&=196x_{2k+1}-14x_{2k}-x_{2k+1}\\&=195x_{2k+1}+x_{2k+1}-14x_{2k}-x_{2k+1}\\&=194x_{2k+1}-x_{2k-1}\end{aligned}$$ Đồng thời, vì $x=4n+3$ nên $n=\dfrac{x-3}{4}\in\mathbb{Z^+}$, theo đó: $n_k=\dfrac{x_{2k+1}-3}{4}\Rightarrow n_0=1, n_1=337, n_{k+1}=194n_k-n_{k-1}+144$. Vậy, tất cả giá trị $n$ thỏa mãn bài toán là: $$\begin{cases}n_0=1, n_1=337\\n_{k+1}=194n_k-n_{k-1}+144, k=0,1,2,...\end{cases}$$
Bài toán 3: Tìm cặp số nguyên tố $p, q$ thỏa mãn: $p^2-2q^2=1$
Lời giải:
Xét phương trình Pell loại I: $$x^2-2y^2=1$$ Bằng phép thử tuần tự, ta nhận thấy $(3, 2)$ là nghiệm nhỏ nhất của phương trình này đồng thời đây cũng là cặp số nhỏ nhất thỏa mãn bài toán. Theo đó, công thức nghiệm của phương trình Pell này được xác định bởi: $$\begin{cases}x_n=\dfrac{(3+2\sqrt{2})^n+(3-2\sqrt{2})^n}{2}\\y_n=\dfrac{(3+2\sqrt{2})^n-(3-2\sqrt{2})^n}{2\sqrt{2}}\end{cases}$$ Suy ra: $$\begin{aligned}x_n+y_n &=\dfrac{(3+2\sqrt{2})^n+(3-2\sqrt{2})^n}{2}+\dfrac{(3+2\sqrt{2})^n-(3-2\sqrt{2})^n}{2\sqrt{2}}\\&=\dfrac{(\sqrt{2}+1)^{2n+1}+(\sqrt{2}-1)^{2n+1}}{2\sqrt{2}}\end{aligned}$$ Áp dụng công thức khai triển Newton, ta có: $$\begin{aligned}x_n+y_n&=\dfrac{(\sqrt{2}+1)^{2n+1}+(\sqrt{2}-1)^{2n+1}}{2\sqrt{2}}\\&=\dfrac{\sum^{2n+1}_{i=0}C^i_{2n+1}(\sqrt{2})^i+\sum^{2n+1}_{i=0}C^i_{2n+1}(\sqrt{2})^i(-1)^{2n+1-i}}{2\sqrt{2}}\\&=\dfrac{2\sqrt{2}\sum^{n}_{j=0}C^{2j+1}_{2n+1}2^j}{2\sqrt{2}}=\sum^{n}_{j=0}C^{2j+1}_{2n+1}2^j\\&=C^1_{2n+1}+\sum^{n}_{j=1}C^{2j+1}_{2n+1}2^j=1+\sum^n_{j=1}C^{2j+1}_{2n+1}2^j\equiv 1\pmod{2}\end{aligned}$$ Điều này chỉ xảy ra khi $p, q$ khác tính chẵn lẻ hay nói cách khác phương trình đã cho vô nghiệm nếu $\min\{p,q\}>2$. Vậy, $(3, 2)$ là nghiệm duy nhất của bài toán.
Bài toán 4: Tìm tất cả các số tự nhiên $n$ sao cho $2n+1$ và $3n+1$ đều là các số chính phương.
Lời giải:
Đặt $d=\gcd (2n+1, 3n+1)$, khi đó: $$\begin{cases}d\;|\;2n+1\\d\;|\;3n+1\end{cases}\Leftrightarrow \begin{cases} d\;|\;6n+3\\d\;|\;6n+2\end{cases}\Rightarrow d\;|\;1\Rightarrow d=1$$ Điều này cho thấy $2n+1, 3n+1$ đồng thời là các số chính phương khi và chỉ khi tồn tại $y\in\mathbb{Z^+}$ sao cho: $$\begin{aligned}&\;\;\;\;(2n+1)(3n+1)=y^2\\&\Leftrightarrow 6n^2+5n+1=y^2\\&\Leftrightarrow 144n^2+120n+24=24y^2\\&\Leftrightarrow (12n+5)^2-24y^2=1\end{aligned}$$ Đặt $x=12n+5$, phương trình trở thành: $$x^2-24y^2=1$$Đây chính là phương trình Pell loại I, vì $24$ không phải là số chính phương nên phương trình này chắc chắn có
nghiệm và công thức nghiệm của nó được cho bởi: $$\begin{cases} x_0=1, y_0=0\\x_1=5, y_1=1\\x_{k+2}=10x_{k+1}-x_k, k=0,1,2,...\\y_{k+2}=10y_{k+1}-y_k, k=0,1,2,...\end{cases}$$ Bằng qui nạp ta chứng minh được $x_{2k+1}\equiv 5\pmod{12}$, do đó: $$n_k=\dfrac{x_{2k+1}-5}{12}$$ Ngoài ra: $$\begin{aligned}x_{2k+3}&=10x_{2k+2}-x_{2k+1}\\&=10(10x_{2k+1}-x_{2k})-x_{2k+1}\\&=99x_{2k+1}-10x_{2k}\\&=98x_{2k+1}+(10x_{2k}-x_{2k-1})-10x_{2k}\\&=98x_{2k+1}-x_{2k-1}\end{aligned}$$ Suy ra: $n_{k+1}=98n_k-n_{k-1}+40$. Và theo đó tất cả giá trị $n$ thỏa mãn bài toán là: $$\begin{cases}n_0=0, n_1=40\\n_{k+}=98n_k-n_{k-1}+40, k=0,1,2,...\end{cases}$$
Nhận xét: Với cách làm tương tự như bài toán 4, ta có thể giải quyết được bài toán sau:
Bài toán (Việt Nam TST 2013):
1. Chứng minh rằng tồn tại vô hạn số nguyên dương $t$ sao cho $2012t+1$ và $2013t+1$ đều là các số chính phương.
2. Xét $m, n$ là các số nguyên dương sao cho $mn+1$ và $(m+1)n+1$ đều là các số chính phương. Chứng minh rằng $n$ chia hết cho $8(2m+1)$
Bài toán 5: Chứng minh rằng tồn tại vô hạn số nguyên dương $x, y, z$ sao cho: $$x^2+y^3=z^4$$
Lời giải:
Bổ đề: Tồn tại vô hạn số nguyên dương $n, k$ sao cho: $$\dfrac{n(n+1)}{2}=k^2$$
Chứng minh bổ đề:
Biến đổi phương trình $(1)$ về dạng tương đương: $$(2n+1)^2-8k^2=1$$ Đặt $m=2n+1$, phương trình $(1)$ trở thành $m^2-8k^2=1$. Đây chính là phương trình Pell loại I và công thức nghiệm của nó được cho bởi: $$\begin{cases}m_0=1, k_0=0\\m_1=3, k_1=2\\m_{l+2}=6m_{l+1}-m_l\\k_{l+2}=6k_{l+1}-k_l\end{cases}$$ Ngoài ra, ta thấy $m_l\equiv 1\pmod{2}$ nên giá trị $n$ thỏa mãn bổ đề được cho bởi: $$\begin{cases}n_0=0, n_1=1\\n_{l+2}=6n_{l+1}-n_l+2,l=0,1,2,...\end{cases}$$ Dãy số này chứng tỏ khẳng định của bổ đề là đúng. Bổ đề được chứng minh.
Trở lại bài toán, Bằng qui nạp ta dễ dàng kiểm tra được rằng với mọi $n$ nguyên dương, ta luôn có: $$\begin{aligned}&\;\;\;\;1^3+2^3+3^3+...+n^3=\left[\dfrac{n(n+1)}{2}\right]^2\\&\Leftrightarrow [1^3+2^3+3^3+...+(n-1)^3]+n^3=\left[\dfrac{n(n+1)}{2}\right]^2\\&\Leftrightarrow \left[\dfrac{(n-1)n}{2}\right]^2+n^3=\left[\dfrac{n(n+1)}{2}\right]^2\end{aligned}$$ Từ đây, áp dụng bổ đề trên, ta chọn $$\begin{cases}x=\dfrac{n(n+1)}{2}\\y=n\\z^2=\dfrac{n(n+1)}{2}\end{cases}$$ Rõ ràng đây chính là ba bộ số thỏa mãn bài toán. Từ đó suy ra đpcm.
Bài toán 6: Chứng minh rằng tồn tại vô hạn số nguyên dương $x, y$ sao cho: $$\dfrac{x+1}{y}+\dfrac{y+3}{x}=6$$
Lời giải:
Phương trình đã cho tương đương với: $$x^2+(1-6y)x+y(y+3)=0$$ Xem đây như một phương trình bậc hai ẩn $x$ tham số $y$, ta có: $$\Delta =(1-6y)^2-4y(y+3)=32y^2-24y+1$$ Bây giờ ta nhận thấy rằng phương trình đã cho có vô hạn nghiệm nguyên dương khi và chỉ khi tồn tại vô hạn số nguyên dương $y,k$ thỏa mãn: $$\begin{aligned}&\;\;\;32y^2-24y+1=k^2\\&\Leftrightarrow 64y^2-48y+2=2k^2\\&\Leftrightarrow (8y-3)^2-2k^2=7\end{aligned}$$ Đặt $m=8y-3$, phương trình trở thành: $$m^2-2k^2=7\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(*)$$ Xét phương trình Pell loại I: $m^2-2k^2=1$, dễ thấy phương trình Pell này nhận nghiệm nhỏ nhất là $(3, 2)$, bằng phép thử tuần tự ta tìm được $(3, 1)$ là nghiệm cơ sở của $(*)$. Theo đó, ta xét dãy $(x_n), (y_n)$: $$\begin{cases}x_0=3, y_0=2\\x_{n+1}=3x_n+4y_n, n=1,2,3,...\\y_{n+1}=2x_n+3y_n,n=1,2,3,...\end{cases}$$ Đồng thời: $$x_{n+1}^2-2y_{n+1}^2=(3x_n+4y_n)^2-2(2x_n+3y_n)^2=x_n^2-2y_n^2=...=x_1^2-2y_1^2=7$$ Điều này chứng tỏ phương trình $m^2-2k^2=7$ có vô hạn nghiệm nguyên dương. Ngoài ra ta còn nhận thấy $x_{2k}\equiv 3\pmod{8}$, thật vậy chú ý rằng: $$\begin{aligned}x_{n+1}&=3x_n+4y_n\\&=9x_{n-1}+12y_{n-1}+4y_n\\&=9x_{n-1}+8y_{n-1}+4(y_n+y_{n-1})\\&=9x_{n-1}+8y_{n-1}+8(x_{n-1}+2x_{n-1})\equiv x_{n-1}\pmod{8}\end{aligned}$$ Như vậy, $$ x_{2k}\equiv x_{2k-2}\equiv ...\equiv x_2\equiv x_0\equiv 3\pmod{8}$$ Điều này cho thấy tồn tại vô hạn $y,k\in\mathbb{Z^+}$ sao cho: $$(8y-3)^2-2k^2=7$$ Từ đó dễ dàng suy ra đpcm.
Tài liệu tham khảo:
[1] Phương trình nghiệm nguyên - Phan Huy Khải.
[2] Phương trình Diophant - Trần Nam Dũng
[3] Lời giải và bình luận TST 2013.
