Pell方程

原理

若 \(D\) 不为完全平方数，形如 \[ x^2-Dy^2=1 \] 的方程称为为佩尔方程。

如果 \((x_1,y_1)\), \((x_2,y_2)\) 都为 \(x^2-Dy^2=1\) 的一组整数解，那么 \[ \begin{aligned} X&=x_1x_2+Dy_1y_2\\\\ Y&=x_1y_2+x_2y_1 \end{aligned} \] 也是方程的一组整数解。这可以直接代回原方程来验证。

推广：对于方程 \[ x^2-Dy^2=k \] 我们考虑与其对应的方程： \[ x^2-Dy^2=1 \] 解得该方程的解 \((r,s)\)，那么原方程的解 \((p,q)\) 形式如下： \[ (pr\pm Dqs,ps\pm qr) \]

应用

求满足 \[ \sqrt{5n^2+4}=k \]

的所有正整数解。

\[ \sqrt{5n^2+4}=k \]

对应佩尔方程 \[ x^2-5y^2=4 \] 我们要求上式中的 \(y\)。我们观察到 \[ x^2-5y^2=1 \] 的最小正整数解为 \((9,4)\)。

于是该方程中所有的解满足： \[ (x+\sqrt5y)(x-\sqrt5y)=(9^2-5\times 4^2)^n=(9+4\sqrt5)^n(9-4\sqrt5)^n=1\\ \]

\[ x_n=9x_{n-1}\pm20y_{n-1}\\\\ y_n=4x_{n-1}\pm9y_{n-1} \]

于是 \[ x_n=\dfrac{(9+4\sqrt5)^n+(9-4\sqrt5)^n}{2}\\\\ y_n=\dfrac{(9+4\sqrt5)^n-(9-4\sqrt5)^n}{2\sqrt{5}} \] 取 \(r_n=x_n,s_n=y_n\)

原方程的最小正整数解为 \((3,1)\)

于是原方程的解满足 \[ x_n=3r_n\pm 5s_n\\\\ y_n=3s_n\pm r_n \] 于是我们有 \[ y_n=3\dfrac{(9+4\sqrt5)^n+(9-4\sqrt5)^n}{2}+\dfrac{(9+4\sqrt5)^n-(9-4\sqrt5)^n}{2\sqrt{5}} \]

不想化简这个式子，但这大概是猜不出这道题最简单的解法的情况下最好的做法了。

不过可以观察得到，序列 \(y_n\) 为 \(\{1,3,8,21,...\}\)，对比斐波那契数列 \(\{1,1,2,3,5,8,13, 21\}\)，发现 \(y_n\) 就是斐波那契数列的偶数项，这题就做完了。