Pell 方程

前置知识：连分数、二次域

引入

本文讨论（广义）Pell 方程的求解。广义 Pell 方程是指关于 $x$ 和 $y$ 的不定方程

$$x^2-D{y}^2=N,$$

其中，$D$ 是正整数且不是完全平方数¹，$N$ 是非零整数。狭义的 Pell 方程特指 $N=1$ 或 $N=\pm 1$ 的特殊情形，有时也包括 $N=\pm 4$ 的情形。广义 Pell 方程与在实二次整数环内寻找范数为 $N$ 的二次整数紧密相关，而常常称作（狭义）Pell 方程的这些情形可以看作是寻找实二次整数环内的单位数。

当本文提及 Pell 方程时，特指 $N=1$ 的情形。相应地，$N=-1$ 的情形称为负 Pell 方程²（negative Pell's equation）。

解的结构

广义 Pell 方程的整数解 $(x,y)$ 和二次整数 $x+y\sqrt{D}$ 联系密切，因此文献中 Pell 方程的解常常写作 $x+y\sqrt{D}$ 的形式。因为二次整数的范数

$$N(x+y\sqrt{D})=x^2-D{y}^2,$$

所以，广义 Pell 方程大致相当于在求解范数为 $N$ 的二次整数。但是，两者确实有细微的区别。当 $x$ 和 $y$ 都是整数时，$x+y\sqrt{D}$ 一定是二次整数；反过来，二次整数未必要求 $x$ 和 $y$ 都是整数——在 $D\equiv 1(\mathrm{mod}4)$ 的情形，$x$ 和 $y$ 还可以同时是半整数³。

这个区别在求解基本单位数时格外重要。因为二次整环中的单位数是指范数为 $\pm 1$ 的二次整数。对于 $D\equiv 2,3(\mathrm{mod}4)$，要找到这样的单位数，只需要求解广义 Pell 方程在 $N=\pm 1$ 的情形即可；但是对于 $D\equiv 1(\mathrm{mod}4)$，还需要考虑 $N=\pm 4$ 的情形。下文 会讨论单位数的求解方法。

要理解广义 Pell 方程解的结构，需要从 Brahmagupta 恒等式 入手：

$$(x_1^2-D{y}_1^2)(x_2^2-D{y}_2^2)=(x_1{x}_2+D{y}_1{y}_2{)}^2-D(x_1{y}_2+x_2{y}_1{)}^2.$$

它相当于二次整数的范数保持乘法，即

利用这一恒等式，可以利用方程 $x^2-D{y}^2=N_1$ 和方程 $x^2-D{y}^2=N_2$ 的整数解复合出方程 $x^2-D{y}^2=N_1{N}_2$ 的整数解。当然，从二次整数的角度看，解的复合就是二次整数的乘法，这就体现了将 Pell 方程的解记作二次整数形式的方便之处。特别地，取 $N_1=N$ 和 $N_2=1$ 就可以发现，如果已知 $x^2-D{y}^2=N$ 的一组解和相应的 Pell 方程 $x^2-D{y}^2=1$ 的全体解，就可以得到 $x^2-D{y}^2=N$ 更多的解。当然，这种方法未必能够生成全部的解。但是，这至少说明理解 Pell 方程的解的结构对理解广义 Pell 方程的解的结构有重要作用。

Pell 方程

方程 $x^2-D{y}^2=1$ 的几何意义是实轴在 $x$ 轴、虚轴在 $y$ 轴的双曲线。双曲线上的每个点都唯一对应了 $x+y\sqrt{D}$ 的一个非零取值：双曲线的左支对应着 $x+y\sqrt{D}$ 的负值，右支则对应正值。而且，在每一支上，双曲线自下而上对应的 $x+y\sqrt{D}$ 的取值是严格递增的。二次整数的取值给 Pell 方程的解赋予了自然的顺序。

双曲线同时关于 $x$ 轴和 $y$ 轴对称，因此讨论 Pell 方程的解只需要考虑在第一象限内的那一段即可，其余解可以通过对称性获得。这相当于只考虑 的解。如果方程除了 $(\pm 1,0)$ 之外还存在不平凡的解，那么一定在第一象限内存在 $x+y\sqrt{D}$ 取值最小的解 $(x_1,y_1)$，这也是第一象限内（不含坐标轴）横纵坐标都最小的整点，它称为 Pell 方程的基本解（fundamental solution）⁴。根据前文的讨论，满足 $x_k+y_k\sqrt{D}=(x_1+y_1\sqrt{D}{)}^k$ 的整数对 $(x_k,y_k)$ 都是 Pell 方程的解，而且都在第一象限。反过来，这也的确是 Pell 方程在第一象限内的全部解。再利用对称性，就可以得到如下结论：

定理

设 Pell 方程 $x^2-D{y}^2=1$ 的基本解是 $(x_1,y_1)$。那么，它的全部解就是

$$\{(x,y):x+y\sqrt{D}=\pm (x_1+y_1\sqrt{D}{)}^k,k\in \mathbf{Z}\}.$$

证明

首先证明第一象限中不存在其他解。不妨设存在其他解 $x+y\sqrt{D}$ 且对于某个 $k\ge 0$ 有

几何意义上，这相当于说整点 $(x,y)$ 落入了双曲线上 $(x_k,y_k)$ 和 $(x_{k+1},y_{k+1})$ 之间（不含端点）。将不等式同时乘以 $x_k-y_k\sqrt{D}=(x_k+y_k\sqrt{D}{)}^{-1}$ 就得到

根据前文提到的单调性，这个不等式就说明 $(x{x}_k-Dy{y}_k,x_{k}y-x{y}_k)$ 是位于 $(1,0)$ 和 $(x_1,y_1)$ 之间的整点。这与 $(x_1,y_1)$ 的选取矛盾。

将第一象限的解扩展到整个平面时，指数 $k$ 取相反数（即整体取倒数）就是关于 $x$ 轴对称，整体取相反数则是关于原点对称。再加上 $k=0$ 时的平凡解，就得到 Pell 方程的全部解。

前文的讨论只是假设了基本解的存在。现在要说明的是，Pell 方程总是存在非平凡的解。

证明

首先，Dirichlet 定理 表明存在无数对正整数 $(x,y)$ 使得

$$|\frac{x}{y}-\sqrt{D}|\le \frac{1}{y^2}$$

成立，它们都满足不等式

因而，必然存在整数 $m\in (-1-2\sqrt{D},1+2\sqrt{D})$ 使得有无数对 $(x,y)$ 都满足 $x^2-D{y}^2=m$。将这些 $(x,y)$ 根据对 $m$ 的余数分类，就知道对某一对整数 $(x_0,y_0)$，一定存在无数对 $(x,y)$ 使得 $x\equiv x_0(\mathrm{mod}m)$ 以及 $y\equiv y_0(\mathrm{mod}m)$ 成立。任取满足这些条件的两对互异的 $(x_1,y_1)$ 和 $(x_2,y_2)$，则

$$\frac{x_1+y_1\sqrt{D}}{x_2+y_2\sqrt{D}}=\frac{x_1{x}_2-D{y}_1{y}_2}{m}+\frac{x_2{y}_1-x_1{y}_2}{m}\sqrt{D}.$$

因为根据同余关系有

这说明上式右侧得到的是整数解。而且，因为 $(x_1,y_1)\ne (x_2,y_2)$，它并不平凡。这就说明 Pell 方程的确存在非平凡解。

当然，本节提供的是非构造性的证明，在下文讨论 Pell 方程的解法时，会直接利用连分数的渐近分数构造出 Pell 方程的解，因而提供了 Pell 方程存在非平凡解的另一种证明。另外，尽管本节得到的 Pell 方程解的结构与实二次整数环的单位数的结构是一致的，但是对于 $D\equiv 1(\mathrm{mod}4)$ 的情形，本节并没有完全解决相应的二次整数环的单位数的结构问题，下文将进一步讨论。

广义 Pell 方程

广义 Pell 方程 $x^2-D{y}^2=N$ 的图像同样是平面上的双曲线，同样以 $x$ 轴和 $y$ 轴为对称轴。前文已经指出，方程 $x^2-D{y}^2=N$ 的部分解可能只相差一个 Pell 方程解的因子，这意味着可以将方程 $x^2-D{y}^2=N$ 的解划分为等价类。对于方程 $x^2-D{y}^2=N$ 的两个解 $(x_1,y_1)$ 和 $(x_2,y_2)$，如果存在 Pell 方程的解 $(u,v)$ 使得 $x_2+y_2\sqrt{D}=(x_1+y_1\sqrt{D})(u+v\sqrt{D})$ 成立，那么称解 $(x_1,y_1)$ 和 $(x_2,y_2)$ 等价。两个解等价的充分必要条件是

$$N\mid (x_1{x}_2-D{y}_1{y}_2),N\mid (x_2{y}_1-x_1{y}_2).$$

因为 Pell 方程的解相对容易求出，一个自然的想法是在上述的每个等价类中各求出一个解。只要知道这些解，就可以利用相应的 Pell 方程的解得到所要求的广义 Pell 方程的全部解。在广义 Pell 方程的解的等价类中，由于对称性，每个等价类都存在纵坐标 $y$ 非负但是尽可能小的解：如果这样的解唯一，它就称为该等价类的基本解；否则，该等价类必然有两个 $y$ 非负且最小的解，而且它们关于 $y$ 轴对称，此时选择 的那个作为基本解。由此，求解广义 Pell 方程 $x^2-D{y}^2=N$，就相当于求解它的基本解集 $U$。设它对应的 Pell 方程的基本解是 $(r,s)$，则广义 Pell 方程的全部解的集合是

$$\{(x,y):x+y\sqrt{D}=\pm (r+s\sqrt{D}{)}^k(u+v\sqrt{D}),k\in \mathbf{Z},u+v\sqrt{D}\in U\}.$$

广义 Pell 方程的基本解必然是有限的。这是因为从上面的通解表达式可知，绝对值 $|u+v\sqrt{D}|$ 必然位于 $r-s\sqrt{D}$ 和 $r+s\sqrt{D}$ 之间。文末的参考文献中提供了关于基本解的坐标的范围的更严格的估计。当然，与 Pell 方程的情形不同，广义 Pell 方程可能没有解。

利用广义 Pell 方程的一个解 $(u,v)$ 和 Pell 方程的基本解 $(r,s)$ 得到同一个等价类中的全部解的方法，除了利用解的复合之外，还可以利用如下递推关系

$$x_k=2r{x}_{k-1}-x_{k-2},y_k=2r{y}_{k-1}-y_{k-2},$$

其中，$x_k+y_k\sqrt{D}=(r+s\sqrt{D}{)}^k(u+v\sqrt{D})$。这是因为 $x_n$ 和 $y_n$ 都可以对某一对实数 $(A,B)$ 写成 $A(r+s\sqrt{D}{)}^k+B(r-s\sqrt{D}{)}^k$ 的形式，而根据 Vieta 定理，$r\pm s\sqrt{D}$ 是方程 $x^2-2rx+1=0$ 的两个实根，进而 $x_n$ 和 $y_n$ 都满足上述的二阶常系数递推关系。相较于解的复合，该递推公式有更少的乘法次数。

求解方法

Pell 方程和广义 Pell 方程的求解都可以基于连分数进行。

PQa 算法

本文讨论的算法都基于 PQa 算法，它可以用于求出特定的二次无理数的连分数展开。

设整数 $P_0,Q_0,D$ 满足 $Q_0\ne 0$， 且不是完全平方数，以及 $P_0^2\equiv D(\mathrm{mod}{Q}_0)$。那么，二次无理数

$$\omega =\frac{P_0+\sqrt{D}}{Q_0}$$

的连分数展开 $[a_0,a_1,\cdots ]$ 可以通过如下 递推公式 求得：

$$a_k=\lfloor \frac{P_k+\sqrt{D}}{Q_k}\rfloor ,P_{k+1}=a_k{Q}_k-P_k,Q_{k+1}=\frac{D-P_{k+1}^2}{Q_k}.$$

进而，$\omega$ 的第 $k$ 个渐近分数的分子和分母 $A_k$ 和 $B_k$ 由如下 递推公式 给出：

$$A_k=a_k{A}_{k-1}+A_{k-2},B_k=a_k{B}_{k-1}+B_{k-2}$$

且 $A_{-1}=1$，$A_{-2}=0$，$B_{-1}=0$，$B_{-2}=1$。

这些公式的正确性已经在连分数一文中得到证明。那里也说明了，因为二次无理数是 循环连分数，所以，三元组 $(P_k,Q_k,a_k)$ 最终将进入循环，算法总可以在有限步内终止。不妨设循环节的最小长度是 $\ell$，且循环的最早的起始位置是 $k_0$，则二次无理数的连分数展开可以写作

$$\omega =[a_0,\cdots ,a_{k_0-1},\overline{a_{k_0},\cdots ,a_{k_0+\ell -1}}].$$

利用 PQa 算法解决 Pell 方程，需要建立如下结论：

定理

继续上述记号。设 $G_k=Q_0{A}_k-P_0{B}_k$，则整数对 $(G_{k-1},B_{k-1})$ 满足关系式

$$G_{k-1}^2-D{B}_{k-1}^2=(-1{)}^k{Q}_0{Q}_k,$$

且它们的最大公因数 $gcd(G_{k-1},B_{k-1})$ 整除 $Q_k$。

证明

设 $\omega$ 的连分数展开中，第 $k$ 个余项（完全商）为 ${\omega }_k$，即

$$\omega =[a_0,a_1,\cdots ,a_{k-1},{\omega }_k]=\frac{{\omega }_k{A}_{k-1}+A_{k-2}}{{\omega }_k{B}_{k-1}+B_{k-2}}.$$

将 $\omega =(P_0+\sqrt{D})/Q_0$ 和 ${\omega }_k=(P_k+\sqrt{D})/Q_k$ 代入上式，就得到

$$\frac{P_0+\sqrt{D}}{Q_0}=\frac{(P_k+\sqrt{D})A_{k-1}+Q_k{A}_{k-2}}{(P_k+\sqrt{D})B_{k-1}+Q_k{B}_{k-2}}.$$

消去左右两侧的分母并比较有理部分和无理部分的系数，再代入 $G_k$ 的表达式，就得到如下等式：

因此，将一式乘以 $G_{k-1}$ 减去二式乘以 $B_{k-1}$，就有

最后一步利用了渐近分数的 差分公式。这就证明了第一个结论。

为了证明第二个结论，将 $G_k$ 的表达式代入第一个结论，有

$$(Q_0{A}_{k-1}-P_0{B}_{k-1}{)}^2-D{B}_{k-1}^2=(-1{)}^k{Q}_0{Q}_k.$$

所以，利用 $Q_0\mid (P_0^2-D)$ 有

$$Q_0{A}_{k-1}^2+(\frac{P_0^2-D}{Q_0}{B}_{k-1}-2P_0{A}_{k-1})B_{k-1}=(-1{)}^k{Q}_k.$$

故而，$gcd(G_{k-1},B_{k-1})=gcd(Q_0{A}_{k-1},B_{k-1})$ 整除 $Q_k$。

这个结论提供了一种寻找方程 $x^2-D{y}^2=N$ 的解的方法。如果合理地选择 并选择 $P_0$ 为同余方程 $P_0^2\equiv D(\mathrm{mod}{Q}_0)$ 的解，那么通过对 $(P_0+\sqrt{D})/Q_0$ 执行 PQa 算法，直到找到 $(-1{)}^k{Q}_0{Q}_k=N$，此时 $(G_{k-1},B_{k-1})$ 就成为原方程的一组解。而且，如果 $Q_k=\pm 1$，那么这样得到的解一定是本原解，也就是说 $G_{k-1}$ 和 $B_{k-1}$ 一定是互素的。

这个思想是解决 Pell 方程和广义 Pell 方程的核心。理解了这一思想后，下面就着手处理算法的一些细节，并证明所有的解都可以通过该方式得到。

Pell 方程

要解决 Pell 方程 $x^2-D{y}^2=1$，只需要对 $(P_0,Q_0,D)=(0,1,D)$ 运行 PQa 算法，直到出现 $(-1{)}^k{Q}_k=1$，此时 $(A_{k-1},B_{k-1})$ 就是 Pell 方程的一组解（因为 $G_{k-1}$ 此时就是 $A_{k-1}$)。当然，对于 Pell 方程，对该过程可以进行更精确的描述。

首先，解一定出现在循环节的末尾处。上述过程相当于对 $\sqrt{D}$ 做连分数展开。对此，已经有 结论：

$$\sqrt{D}=[\lfloor \sqrt{D}\rfloor ,\overline{a_1,\cdots ,a_{\ell -1},2\lfloor \sqrt{D}\rfloor }].$$

此处，循环节长度为 $\ell$，且起始位置是第 $1$ 项（下标从 $0$ 开始）。而且，它的第 $\ell$ 项余项等于 $\lfloor \sqrt{D}\rfloor +\sqrt{D}$，这说明 $Q_{\ell }=1$。因此，如果 $\ell$ 是偶数，那么 $(A_{\ell -1},B_{\ell -1})$ 就是 Pell 方程的一组非平凡解；如果 $\ell$ 是奇数，那么 $(A_{2\ell -1},B_{2\ell -1})$ 就是 Pell 方程的一组非平凡解。

接下来要说明，刚刚得到的这组解一定是基础解。这个结论基于两点理由：第一，Pell 方程的所有正整数解 $(x,y)$ 对应的分数 $x/y$ 都出现在 $\sqrt{D}$ 的渐近分数中，这就保证了 $(x,y)$ 必定是 PQa 算法过程中的某个 $(A_k,B_k)$；第二，除了循环节末尾，不会再出现其他位置有 $Q_k=1$，因为 $A_k$ 和 $B_k$ 的递推关系保证了它们的大小随着下标增加而增加，所以最小的正整数解（即基础解）必然出现在刚刚指明的位置。这两点理由可以分别从如下的两条定理得出：

证明

当 时，因为 ，所以 。故而，有

根据 Legendre 判别法 可知，${\displaystyle \frac{x}{y}}$ 是 $\sqrt{D}$ 的渐近分数。

当 时， 不再成立。所以，转而考虑方程 $y^2-{\displaystyle \frac{1}{D}}{x}^2=-{\displaystyle \frac{N}{D}}$ 的解。因为 ，所以上面的论证依然成立。这说明 ${\displaystyle \frac{y}{x}}$ 是 ${\displaystyle \frac{1}{\sqrt{D}}}$ 的渐近分数。根据 倒数定理 可知，${\displaystyle \frac{x}{y}}$ 也是 $\sqrt{D}$ 的渐近分数。

综合本节的讨论可知，只要对 $\sqrt{D}$ 做连分数展开，亦即以 $(P_0,Q_0,D)=(0,1,D)$ 为起点做 PQa 算法，当首次得到 $Q_{\ell }=1$ 时，就到达了第一个循环节的末尾。此时，如果 $\ell$ 是偶数，那么 $(A_{\ell -1},B_{\ell -1})$ 就是 Pell 方程的基本解；否则，$(A_{2\ell -1},B_{2\ell -1})$ 是 Pell 方程的基本解。对于循环节长度 $\ell$ 为奇数的情形，并不需要继续 PQa 算法到两倍的循环节处，马上就会说明 $A_{2\ell -1}+B_{2\ell -1}\sqrt{D}=(A_{\ell -1}+B_{\ell -1}\sqrt{D}{)}^2$，因而可以直接从 $(A_{\ell -1},B_{\ell -1})$ 直接计算出 Pell 方程的基本解。Pell 方程所有其他解都可以通过 Pell 方程的基本解计算。

负 Pell 方程

根据上一节的讨论可知，负 Pell 方程的解也必然对应于 $\sqrt{D}$ 的渐近分数，而且只能出现在 $(-1{)}^k{Q}_k=-1$ 处。这只能出现在循环节的末尾。因此，负 Pell 方程有解，当且仅当循环节长度 $\ell$ 是奇数。当解存在时，$(A_{\ell -1},B_{\ell -1})$ 就是负 Pell 方程的基本解。它的求解方法和上一节是一致的。

利用前文对于 Pell 方程解的结构的证明相仿的思路，可以证明如下结论：

定理

设方程 $x^2-D{y}^2=-1$ 有解，且基本解是 $(x_1,y_1)$。那么，$x^2-D{y}^2=\pm 1$ 的所有整数解都属于集合

$$\{(x,y):x+y\sqrt{D}=\pm (x_1+y_1\sqrt{D}{)}^k,k\in \mathbf{Z}\}.$$

特别地，满足 $x_2+y_2\sqrt{D}=(x_1+y_1\sqrt{D}{)}^2$ 的整数解 $(x_2,y_2)$ 正是 $x^2-D{y}^2=1$ 的基本解。

因为 $(A_{\ell -1},B_{\ell -1})$ 是负 Pell 方程的最小正整数解，而 $x^2-D{y}^2=\pm 1$ 的所有正整数解都出现在集合

$$\{(x,y):x+y\sqrt{D}=(A_{\ell -1}+B_{\ell -1}\sqrt{D}{)}^k,k\in {\mathbf{N}}_{+}\}$$

中，又因为这些正整数解必然对应 $\sqrt{D}$ 的在循环节末尾（前一位）处的渐近分数，而且渐近分数的分子和分母是严格单调递增的，所以对所有 $k\in {\mathbf{N}}_{+}$ 总是有

$$(A_{\ell -1}+B_{\ell -1}\sqrt{D}{)}^k=A_{k\ell -1}+B_{k\ell -1}\sqrt{D}.$$

在所有这些正整数解中，$k$ 为奇数时就是负 Pell 方程的解，$k$ 为偶数时就是 Pell 方程的解，两者交替出现。

判断负 Pell 方程是否有解，需要计算 $\sqrt{D}$ 连分数展开的循环节的长度，这并不容易计算，因此希望能够找到更简单的判断方法。但是，目前并没有条件简明、容易计算的判断方法⁵。此处仅仅提供一个简单的结论。

如果 $D$ 是合数，那么不含有 $4k+3$ 型素因子且没有平方因子也不能保证方程 $x^2-D{y}^2=-1$ 有解，例如 $x^2-34y^2=-1$ 就没有解。

范数为 ±4 的情形

接下来讨论方程 $x^2-D{y}^2=\pm 4$ 的解。此时，解的性态取决于 的大小。

有些情形是容易的。如果 $D\equiv 0(\mathrm{mod}4)$，那么 $x$ 是偶数，因而 $(x/2,y)$ 是方程 $u^2-(D/4)v^2=\pm 1$ 的解。其余的情形，必然有 $x,y$ 同时是奇数或者同时是偶数。如果 $x,y$ 同时是奇数，方程两侧对 $4$ 取模就得到 $D\equiv 1(\mathrm{mod}4)$。所以，如果 $D\equiv 2,3(\mathrm{mod}4)$，那么 $x,y$ 只能同时是偶数，因而 $(x/2,y/2)$ 是方程 $u^2-D{v}^2=\pm 1$ 的解。因此，除了 $D\equiv 1(\mathrm{mod}4)$ 的情形，方程 $x^2-D{y}^2=\pm 4$ 的解都可以通过相应的（负）Pell 方程的解得到。

现在讨论 $D\equiv 1(\mathrm{mod}4)$ 的情形，它不能简单地转化为已经解决的情形。为了找到基本解，可以对 $(P_0,Q_0,D)=(1,2,D)$ 应用 PQa 算法，当首次得到 $Q_{\ell }=2$ 时，就到达了第一个循环节的末尾。如果循环节长度 $l$ 是偶数，那么 $(G_{\ell -1},B_{\ell -1})$ 就是方程 $x^2-D{y}^2=4$ 的基本解；否则，$(G_{\ell -1},B_{\ell -1})$ 就是方程 $x^2-D{y}^2=-4$ 的基本解。从 $(G_{\ell -1},B_{\ell -1})$ 出发，可以得到方程 $x^2-D{y}^2=\pm 4$ 的所有解：

$$\{(x,y):\frac{x+y\sqrt{D}}{2}=\pm {\left(\frac{G_{\ell -1}+B_{\ell -1}\sqrt{D}}{2}\right)}^k,k\in \mathbf{Z}\}.$$

如果循环节长度 $\ell$ 是偶数，所有这些都是方程 $x^2-D{y}^2=4$ 的解；否则，当 $k$ 是奇数时，$(x,y)$ 是方程 $x^2-D{y}^2=-4$ 的解，而当 $k$ 是偶数时，$(x,y)$ 是方程 $x^2-D{y}^2=4$ 的解。

这个算法的正确性依赖于如下事实：

证明

首先注意到，此时 $x,y$ 必然奇偶性相同，所以 $(x+y)/2$ 是整数。如果 $(x,y)$ 是方程 $x^2-D{y}^2=4$ 的解，那么 ，所以，

根据 Legendre 判别法 可知，${\displaystyle \frac{(x+y)/2}{y}}$ 是 ${\displaystyle \frac{1+\sqrt{D}}{2}}$ 的渐近分数。

如果 $(x,y)$ 是方程 $x^2-D{y}^2=-4$ 的解，那么要建立上述不等式，只需要证明 。这至少对于除了 $D=5,13$ 之外的情形都成立。对于 $D=5,13$ 的情形，将 $x=\sqrt{D{y}^2-4}$ 代入该不等式可知，它等价于 成立。除了 $(D,y)=(5,1)$ 之外，该不等式对于所有 $D=5,13$ 和正整数 $y$ 都成立。剩下的就是验证 $(D,y)=(5,1)$ 的情形，此时，方程 $x^2-5y^2=-4$ 的解是 $(x,y)=(1,1)$，需要验证的是 ${\displaystyle \frac{1}{1}}$ 是 ${\displaystyle \frac{1+\sqrt{5}}{2}}=[\bar{1}]$ 的渐近分数，而这是显然成立的。

定理

设 $D$ 是正整数但不是完全平方数。二次无理数 $\omega ={\displaystyle \frac{1+\sqrt{D}}{2}}$ 的连分数展开具有形式

$$\omega =[\lfloor \omega \rfloor ,\overline{a_1,\cdots ,a_{\ell -1},2\lfloor \omega \rfloor -1}],$$

其中，$\ell$ 为循环节长度，且 $a_k=a_{\ell -k}$ 对任何 都成立。

证明

因为 ，而且它的共轭等于 $\lfloor \omega \rfloor -\omega$，位于 $-1$ 和 $0$ 之间，所以根据 Galois 的结论 可知，$\lfloor \omega \rfloor -1+\omega$ 是纯循环连分数，可以写成

$$\lfloor \omega \rfloor -1+\omega =[\overline{2\lfloor \omega \rfloor -1,a_1,\cdots ,a_{\ell -1}}].$$

而 Galois 关于倒数负共轭的结论说明

$$\frac{1}{\omega -\lfloor \omega \rfloor }=[\overline{a_{\ell -1},\cdots ,a_1,2\lfloor \omega \rfloor -1}].$$

因此，根据连分数的定义，有

$$\lfloor \omega \rfloor -1+\omega =2\lfloor \omega \rfloor -1+\frac{1}{{\displaystyle \frac{1}{\omega -\lfloor \omega \rfloor }}}=[2\lfloor \omega \rfloor -1,\overline{a_{\ell -1},\cdots ,a_1,2\lfloor \omega \rfloor -1}].$$

连分数展开的唯一性就说明 $a_k=a_{\ell -k}$ 对所有 都成立，因而要证明的展开式也成立。

定理

设方程 $x^2-D{y}^2=\pm 4$ 的最小正整数解为 $(x_1,y_1)$。那么，它的全部解就是

$$\{(x,y):\frac{x+y\sqrt{D}}{2}=\pm {\left(\frac{x_1+y_1\sqrt{D}}{2}\right)}^k,k\in \mathbf{Z}\}.$$