6.1 Phương trình Pell
Ta xét phương trình:
\[x^2 - dy^2 = 1 \quad (6.1)\]Chú ý rằng nếu \((x_1, y_1)\) và \((x_2, y_2)\) là nghiệm của (6.1) thì:
\[1 = (x_1^2 - dy_1^2)(x_2^2 - dy_2^2) = (x_1x_2 + dy_1y_2)^2 - d(x_1y_2 + x_2y_1)^2\]Do đó với \(x_3 = x_1x_2 + dy_1y_2\) và \(y_3 = x_1y_2 + x_2y_1\) thì \((x_3, y_3)\) cũng là nghiệm của (6.1). Điều này cho phép ta định nghĩa một phép toán hai ngôi trên tập các nghiệm của phương trình (6.1) như sau:
\[(x_1, y_1) \times (x_2, y_2) := (x_1x_2 + dy_1y_2, x_1y_2 + x_2y_1)\]Dễ kiểm tra thấy \(\times\) có tính chất kết hợp, \((1, 0)\) là phần tử đơn vị và phần tử nghịch đảo của nghiệm \((x, y)\) là nghiệm \((x, -y)\). Do đó tập nghiệm của phương trình Pell (6.1) có cấu trúc của một nhóm giao hoán.
Kể từ bây giờ ta giả sử \(d > 0\) không phải là một số chính phương (điều này dẫn đến \(\sqrt{d}\) là một số vô tỉ bậc 2). Giả sử \((x, y)\) với \(x, y > 0\) là một nghiệm của (6.1). Khi đó:
\[\left| \frac{x}{y} - \sqrt{d} \right| = \frac{1}{y(x + y\sqrt{d})} < \frac{1}{2y^2}\]Theo tính chất của liên phân số, \(\frac{x}{y}\) phải nằm trong dãy các xấp xỉ \(r_n = \frac{p_n}{q_n}\) của \(\sqrt{d}\). Do đó để tìm nghiệm của (6.1), ta chỉ cần xét các xấp xỉ \(\frac{p_n}{q_n}\) được xây dựng từ khai triển liên phân số của \(\sqrt{d}\). Theo định lý của Lagrange, ta biết rằng khai triển liên phân số của \(\sqrt{d}\) là tuần hoàn. Gọi \(\ell\) là chu kỳ của khai triển, khi đó:
- Nếu \(\ell\) chẵn thì \((p_{\ell-1}, q_{\ell-1})\) là nghiệm của phương trình;
- Nếu \(\ell\) lẻ thì \((p_{2\ell-1}, q_{2\ell-1})\) là nghiệm của phương trình.
Từ nghiệm vừa tìm được, cùng với cấu trúc nhóm giao hoán của tập nghiệm, ta hoàn toàn có thể tìm được tất cả các nghiệm còn lại của phương trình.
6.2 Phương trình \(x^2 + dy^2 = n\)
Trong phần này chúng ta sẽ trình bày thuật toán Cornacchia dùng để tìm nghiệm nguyên của phương trình:
\[x^2 + dy^2 = n \quad (6.2)\]trong đó \(d, n\) là các số tự nhiên. Giả sử \((x, y)\) là nghiệm của phương trình khi đó dựa vào đánh giá bất đẳng thức ta có \(x^2 \le n\) và \(y^2 \le n\). Do đó với \(n\) cho trước phương trình chỉ có hữu hạn nghiệm \((x, y)\) và các nghiệm này thỏa mãn tính chất \(x, y \le \sqrt{n}\).
Thuật toán sau cho phép ta đi tìm nghiệm nguyên thủy (các nghiệm \((x, y)\) thỏa mãn tính chất \(\gcd(x, y) = 1\)) của phương trình trên:
- Bước 1: Giải phương trình đồng dư \(x^2 \equiv -d \pmod n\).
- Bước 2: Giả sử \(r_1 \le \frac{n}{2}\) là nghiệm của phương trình đồng dư trên. Sử dụng thuật toán Euclid để tìm:\[\begin{cases} r_2 \equiv n \pmod{r_1} \\ r_3 \equiv r_1 \pmod{r_2} \\ r_{i+2} \equiv r_i \pmod{r_{i+1}} \quad \forall i \ge 1 \end{cases}\]
Cụ thể hơn \(r_2\) chính là phần dư của phép chia Euclid của \(n\) cho \(r_1\), \(r_3\) chính là phần dư của phép chia Euclid của \(r_1\) cho \(r_2\), với mọi \(i \ge 1\) thì \(r_{i+2}\) chính là phần dư của phép chia Euclid của \(r_i\) cho \(r_{i+1}\). Chúng ta sẽ dừng lại khi tìm được \(r_k^2 < n \le r_{k-1}^2\).