Pell 方程

引入

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

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

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

解的结构

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

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

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

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

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

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

\begin{aligned} N\left(x_1+y_1\sqrt{D}\right)N\left(x_2+y_2\sqrt{D}\right) &= N\left((x_1+y_1\sqrt{D})(x_2+y_2\sqrt{D})\right) \\ &= N\left((x_1x_2+Dy_1y_2)+(x_1y_2+x_2y_1)\sqrt{D}\right). \end{aligned}

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

Pell 方程

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

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

定理

设 Pell 方程的基本解是。那么，它的全部解就是

\{(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_k+y_k\sqrt{D}< x+y\sqrt{D}< x_{k+1}+y_{k+1}\sqrt{D}.

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

1< (x+y\sqrt{D})(x_k-y_k\sqrt{D})=(xx_k-Dyy_k)+(x_ky-xy_k)\sqrt{D} < x_1+y_1\sqrt{D}.

根据前文提到的单调性，这个不等式就说明是位于和之间的整点。这与的选取矛盾。

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

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

定理

Pell 方程总是存在除了 $(\pm 1,0)$ 之外的整数解。

证明

首先，Dirichlet 定理表明存在无数对正整数使得

\left|\dfrac{x}{y}-\sqrt{D}\right| \le \dfrac{1}{y^2}

成立，它们都满足不等式

|x^2-Dy^2|=y^2\left|\dfrac{x}{y}-\sqrt{D}\right|\left|\dfrac{x}{y}+\sqrt{D}\right| \le \dfrac{1}{y^2}+2\sqrt{D}<1+2\sqrt{D}.

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

\dfrac{x_1+y_1\sqrt{D}}{x_2+y_2\sqrt{D}}=\dfrac{x_1x_2-Dy_1y_2}{m}+\dfrac{x_2y_1-x_1y_2}{m}\sqrt{D}.

因为根据同余关系有

\begin{aligned} x_1x_2-Dy_1y_2 &\equiv x_0^2-Dy_0^2 = m \equiv 0 \pmod{|m|},\\ x_2y_1-x_1y_2 &\equiv x_0y_0-x_0y_0 = 0 \pmod{|m|}, \end{aligned}

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

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

广义 Pell 方程

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

N\mid (x_1x_2-Dy_1y_2),\ N\mid (x_2y_1-x_1y_2).

因为 Pell 方程的解相对容易求出，一个自然的想法是在上述的每个等价类中各求出一个解。只要知道这些解，就可以利用相应的 Pell 方程的解得到所要求的广义 Pell 方程的全部解。在广义 Pell 方程的解的等价类中，由于对称性，每个等价类都存在纵坐标非负但是尽可能小的解：如果这样的解唯一，它就称为该等价类的基本解；否则，该等价类必然有两个非负且最小的解，而且它们关于轴对称，此时选择的那个作为基本解。由此，求解广义 Pell 方程，就相当于求解它的基本解集。设它对应的 Pell 方程的基本解是，则广义 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 方程的一个解和 Pell 方程的基本解得到同一个等价类中的全部解的方法，除了利用解的复合之外，还可以利用如下递推关系

x_{k} = 2rx_{k-1} - x_{k-2},\ y_{k} = 2ry_{k-1} - y_{k-2},

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

求解方法

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

PQa 算法

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

设整数满足 $Q_0\neq 0$ ，且不是完全平方数，以及 $P_0^2\equiv D\pmod{Q_0}$ 。那么，二次无理数

\omega=\dfrac{P_0+\sqrt{D}}{Q_0}

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

a_k = \left\lfloor\dfrac{P_k+\sqrt{D}}{Q_k}\right\rfloor,\ P_{k+1} = a_kQ_k - P_k,\ Q_{k+1} = \dfrac{D-P_{k+1}^2}{Q_k}.

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

A_k = a_kA_{k-1} + A_{k-2},\ B_k = a_kB_{k-1} + B_{k-2}

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

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

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

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

定理

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

G_{k-1}^2-DB_{k-1}^2=(-1)^{k}Q_0Q_{k},

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

证明

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

\omega = [a_0,a_1,\cdots,a_{k-1},\omega_k] = \dfrac{\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$ 代入上式，就得到

\dfrac{P_0+\sqrt{D}}{Q_0} = \dfrac{(P_k+\sqrt{D})A_{k-1}+Q_kA_{k-2}}{(P_k+\sqrt{D})B_{k-1}+Q_kB_{k-2}}.

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

\begin{aligned} G_{k-1} &= P_kB_{k-1} + Q_kB_{k-2},\\ DB_{k-1} &= P_kG_{k-1} + Q_kG_{k-2}. \end{aligned}

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

\begin{aligned} G_{k-1}^2-DB_{k-1}^2 &= (B_{k-2}G_{k-1}-B_{k-1}G_{k-2})Q_k \\ &= (A_{k-1}B_{k-2}-B_{k-1}A_{k-2})Q_0Q_k \\ &= (-1)^kQ_0Q_k. \end{aligned}

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

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

(Q_0A_{k-1}-P_0B_{k-1})^2 - DB_{k-1}^2 = (-1)^kQ_0Q_k.

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

Q_0A_{k-1}^2 +\left(\dfrac{P_0^2-D}{Q_0}B_{k-1}- 2P_0A_{k-1}\right)B_{k-1} = (-1)^kQ_k.

故而， $\gcd(G_{k-1},B_{k-1}) = \gcd(Q_0A_{k-1},B_{k-1})$ 整除。

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

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

Pell 方程

要解决 Pell 方程，只需要对运行 PQa 算法，直到出现，此时 $(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$ ，且起始位置是第项（下标从开始）。而且，它的第 $\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 方程的所有正整数解对应的分数都出现在 $\sqrt{D}$ 的渐近分数中，这就保证了必定是 PQa 算法过程中的某个；第二，除了循环节末尾，不会再出现其他位置有，因为和的递推关系保证了它们的大小随着下标增加而增加，所以最小的正整数解（即基础解）必然出现在刚刚指明的位置。这两点理由可以分别从如下的两条定理得出：

定理

设方程有正整数解，如果 $|N|<\sqrt{D}$ ，那么 $\dfrac{x}{y}$ 一定等于 $\sqrt{D}$ 的渐近分数。

证明

当时，因为，所以 $x>y\sqrt{D}$ 。故而，有

\left|\dfrac{x}{y}-\sqrt{D}\right| = \dfrac{N}{y(x+y\sqrt{D})}<\dfrac{N}{2y^2\sqrt{D}}<\dfrac{1}{2y^2}.

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

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

定理

在对运行上述 PQa 算法的过程中，必然推出 $\ell\mid k$ 。

证明

在 $\sqrt{D}$ 的连分数展开中，除了第个余项，所有其他余项都是纯循环连分数。设。根据 Galois 的结论，必然有余项 $\omega_k=P_k+\sqrt{D}>1$ ，且它的共轭 $-1<P_k-\sqrt{D}<0$ ，这说明 $P_k=\lfloor\sqrt{D}\rfloor$ 。因此，余项 $\omega_k$ 就等于 $\omega_\ell$ 。但是，余项的重复意味着连分数的循环，如果不是 $\ell$ 的整数倍，就与 $\ell$ 是最小正周期相矛盾。所以，必然有 $\ell\mid k$ 。

综合本节的讨论可知，只要对 $\sqrt{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 方程的基本解计算。

示例

求解方程。

对运行 PQa 算法结果如下：（标红部分为第一个循环节）

$\color{red}{1}$
$\color{red}{2}$
$\color{red}{1}$
$\color{red}{6}$

循环节长度 $\ell=4$ 为偶数。方程的最小正整数解为。
求解方程。

对运行 PQa 算法结果如下：（标红部分为第一个循环节）

$\color{red}{2}$
$\color{red}{2}$
$\color{red}{12}$

循环节长度 $\ell=3$ 为奇数。方程的最小正整数解为。它也可以通过计算得出：
$(32+5\sqrt{41})^2=2049+320\sqrt{41}.$

负 Pell 方程

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

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

定理

设方程有解，且基本解是。那么， $x^2-Dy^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+y\sqrt{D}>1$ 的情形。但是由于 $x^2-Dy^2=\pm 1$ 是两段双曲线，所以 $x+y\sqrt{D}$ 无法和建立一一对应。为了处理这种困难，首先证明上述的是的基本解。

显然，是的解。如果设是的基本解，那么必然有 $1<z+w\sqrt{D}\le x_2+y_2\sqrt{D}$ 。如果右侧的不等式不含有等号，那么将不等式同除以 $x_1+y_1\sqrt{D}$ 就得到 $-x_1+y_1\sqrt{D}<(z+w\sqrt{D})(-x_1+y_1\sqrt{D})<x_1+y_1\sqrt{D}$ 。将该不等式的中间项的表达式展开就能得到 $x'+y'\sqrt{D}$ 的形式，它的范数是且也是整数解。将该不等式取倒数，就发现 $-x'+y'\sqrt{D}$ 同样落入 $-x_1+y_1\sqrt{D}$ 和 $x_1+y_1\sqrt{D}$ 之间。二次整数 $\pm x'+y'\sqrt{D}$ 互为倒数，必然有一个大于。但是和 $x_1+y_1\sqrt{D}$ 不应该再出现别的范数为的二次整数，这与 $x_1+y_1\sqrt{D}$ 的最小性矛盾。所以，必然成立 $x_2+y_2\sqrt{D}=z+w\sqrt{D}$ ，即是方程的基本解。

基于此，如果出现方程 $x^2-Dy^2=\pm 1$ 的解不对应某个 $(x_1+y_1\sqrt{D})^k$ ，那么必然存在使得 $(x_1+y_1\sqrt{D})^{2k}<x+y\sqrt{D}<(x_1+y_1\sqrt{D})^{2k+2}$ ，消去因子 $(x_1+y_1)^{2k+1}$ ，就说明存在位于 $-x_1+y_1\sqrt{D}$ 和 $x_1+y_1\sqrt{D}$ 之间的范数为 $\pm 1$ 的二次整数 $x'+y'\sqrt{D}\neq 1$ 。重复上一段利用倒数的论证可知，这与 $x_1+y_1\sqrt{D}$ 的最小性矛盾。因而原命题得证。

因为 $(A_{\ell-1},B_{\ell-1})$ 是负 Pell 方程的最小正整数解，而 $x^2-Dy^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}.

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

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

定理

方程有解，则不能整除且不含有型的素因子。反过来，如果或是型的素数，那么方程必然有解。

证明

首先，负 Pell 方程有解，就意味着是的二次剩余，因而也是的任意一个因子的二次剩余，故而 $d\neq 4$ 且不是型素数。反过来，方程的解有非平凡解。剩下的就是是型素数的情形。

设是型素数，要证明方程有解。思路是通过 Pell 方程的基本解入手，构造出的解 $(\alpha,\beta)$ 。如果是偶数，将两侧对取模，就得到 $v^2\equiv -1\pmod 4$ ，但是并不是模的二次剩余。这个矛盾说明是奇数。考察等式。因为是奇数，所以 $\gcd(u+1,u-1)=\gcd(u+1,2)=2$ 。根据这一事实，将的因子分给和，必然一个是 $2\alpha^2$ ，另一个是 $2D\beta^2$ ，其中， $\alpha$ 和 $\beta$ 是互素的正整数而且 $v=2\alpha\beta$ 。将 $u=\alpha^2+D\beta^2$ 和 $v=2\alpha\beta$ 代入就得到 $\alpha^2-D\beta^2=\pm 1$ 。因为是 Pell 方程的基本解而且 $(\alpha,\beta)$ 是比更小的正整数对，这个等式右侧不能是，故而只能是。这就证明存在解 $(\alpha,\beta)$ 。

如果是合数，那么不含有型素因子且没有平方因子也不能保证方程有解，例如就没有解。

示例

利用上面的示例中的计算结果可知，方程无解，且方程的最小正整数解为。

范数为 ±4 的情形

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

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

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

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

如果循环节长度 $\ell$ 是偶数，所有这些都是方程的解；否则，当是奇数时，是方程的解，而当是偶数时，是方程的解。

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

定理

设方程 $x^2-Dy^2=\pm 4$ 有正整数解。如果 $D\equiv 1\pmod 4$ ，那么， $\dfrac{(x+y)/2}{y}$ 一定是 $\dfrac{1+\sqrt{D}}{2}$ 的渐近分数。

证明

首先注意到，此时必然奇偶性相同，所以是整数。如果是方程的解，那么 $x>y\sqrt{D}>2y$ ，所以，

\left|\dfrac{(x+y)/2}{y}-\dfrac{1+\sqrt{D}}{2}\right| = \dfrac{2}{y(x+y\sqrt{D})}<\dfrac{1}{2y^2}.

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

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

定理

设是正整数但不是完全平方数。二次无理数 $\omega=\dfrac{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}$ 对任何 $1<k<\ell$ 都成立。

证明

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

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

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

\dfrac{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 + \dfrac{1}{\dfrac{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}$ 对所有 $1<k<\ell$ 都成立，因而要证明的展开式也成立。

定理

设 $D\equiv 1\pmod 4$ 。在对运行上述 PQa 算法的过程中，必然推出 $\ell\mid k$ 。

证明

在 $\dfrac{1+\sqrt{D}}{2}$ 的连分数展开中，除了第个余项，所有其他余项都是纯循环连分数。设。根据 Galois 的结论，必然有余项 $\omega_k=\dfrac{P_k+\sqrt{D}}{2}$ 的共轭 $-1<\dfrac{P_k-\sqrt{D}}{2}<0$ ，亦即 $\sqrt{D}-2<P_k<\sqrt{D}$ 。因为 PQa 算法中总有 $Q_k\mid P_k^2-D$ （见算法正确性证明），所以一定是奇数，这就说明取值唯一，即 $P_k=P_0+2(\lfloor\omega\rfloor-1)$ ，也就是说余项 $\omega_k=\omega\ell$ 。但是，余项的重复意味着连分数的循环，如果不是 $\ell$ 的整数倍，就与 $\ell$ 是最小正周期相矛盾。所以，必然有 $\ell\mid k$ 。

定理

设方程 $x^2-Dy^2=\pm 4$ 的最小正整数解为。那么，它的全部解就是

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

证明

根据对称性，只需要考虑正整数解即可。此处需要证明的只有集合中的实数对确实是方程 $x^2-Dy^2=\pm 4$ 的整数解。剩下的事情只需要复述对方程 $x^2-Dy^2=\pm 1$ 的解的结构的证明即可。

实际上要证明的是，对于方程 $x^2-Dy^2=\pm 4$ 的任何整数解和，如下定义的正实数对仍然是整数解：

\dfrac{x_3+y_3\sqrt{D}}{2} = \dfrac{x_1+y_1\sqrt{D}}{2}\dfrac{x_2+y_2\sqrt{D}}{2}.

展开右侧，比较有理项和无理项的系数可知

x_3=\dfrac{x_1x_2+Dy_1y_2}{2},\ y_3=\dfrac{x_1y_2+x_2y_1}{2}.

因为对有 $x_i\equiv x_i^2\equiv Dy_i^2\equiv Dy_i\pmod 2$ ，所以

\begin{aligned} 2x_3 &= x_1x_2+Dy_1y_2 \equiv D^2y_1y_2+Dy_1y_2=D(D+1)y_1y_2 \equiv 0 \pmod 2,\\ 2y_3 &= x_1y_2+x_2y_1 \equiv Dy_1y_2+Dy_2y_1 = 2Dy_1y_2 \equiv 0 \pmod 2. \end{aligned}

这说明和都是整数。再利用范数保持乘法的性质可知，是 $x^2-Dy^2=\pm 4$ 的解。

综合这些事实，重复前文几节的论述，就可以说明用于解决方程 $x^2-Dy^2=\pm 4$ 的上述算法的正确性。这些结果说明，方程 $x^2-Dy^2=\pm 4$ 具有和方程 $x^2-Dy^2=\pm 1$ 类似的简单的解的结构：它的所有解都可以通过其最小正整数解表示出来，而无需求解其它方程。

其实，方程 $x^2-Dy^2=\pm 1$ 的所有解都可以在方程 $x^2-Dy^2=\pm 4$ 的解中找到，因而从这个角度看，方程 $x^2-Dy^2=\pm 4$ 更为基础。显然，是方程 $x^2-Dy^2=\pm 1$ 的解，当且仅当是方程 $x^2-Dy^2=\pm 4$ 的解。前文的分析指出，当 $D\equiv 2,3\pmod 4$ 时，方程 $x^2-Dy^2=\pm 4$ 的所有解都一定同为偶数，因而对应于 $x^2-Dy^2=\pm 1$ 的解。

当 $D\equiv 0\pmod 4$ 时，方程 $x^2-Dy^2=\pm 4$ 的解中，一定是偶数，但是可能是奇数。如果在方程 $x^2-Dy^2=\pm 4$ 的最小正整数解中，是偶数，那么在所有解中也一定是偶数，此时这些整数解和方程 $x^2-Dy^2=\pm 1$ 的整数解一一对应；但是，如果在最小整数解中，是奇数，那么的奇偶性将和一致，交替变化，因而只有当是偶数时，才对应于方程 $x^2-Dy^2=\pm 1$ 的解。如果 $x^2-Dy^2=\pm 4$ 的最小正整数解中是奇数而且 $x_1+y_1\sqrt{D}$ 的范数是，那么，对于这样的，有解，但是无解。

当 $D\equiv 1\pmod 4$ 时，方程 $x^2-Dy^2=\pm 4$ 的解可能同时是奇数，也可能同时是偶数。如果最小正整数解已经同时是偶数，那么它的所有整数解也一定同时是偶数，所以总是对应于方程 $x^2-Dy^2=\pm 1$ 的整数解。如果最小正整数解同时是奇数，那么有如下结论：

定理

设方程 $x^2-Dy^2=\pm 4$ 的最小正整数解是。如果和同时是奇数，那么， $D\equiv 5\pmod 8$ ，且该方程的整数解同时是偶数，当且仅当

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

证明

等式 $x_1^2-Dy_1^2=\pm 4$ 的两边同时对取模，得到 $D\equiv 5\pmod 8$ 。要证明第二个结论，首先证明都是偶数，因为

\dfrac{x_3+y_3\sqrt{D}}{2} = \left(\dfrac{x_1+y_1\sqrt{D}}{2}\right)^{3} = \dfrac{x_1^3+3Dxy_1^2}{8}+\dfrac{3x_1^2y_1+Dy_1^3}{8}\sqrt{D},

所以，只需要证明右侧是整数。因为奇数的平方模余，所以，有

\begin{aligned} &x_1^3+3Dxy_1 = x_1(x_1^2+3Dy_1) \equiv x_1(1+3\times 5\times 1) = 16x_1 = 0 \pmod 8,\\ &3x_1^2y_1+Dy_1^3 = y_1(3x_1^2+Dy_1^2) \equiv y_1(3\times 1+5\times 1) = 8y_1 = 0 \pmod 8. \end{aligned}

这就说明了都是偶数。进而，对于所有 $k\in\mathbf Z$ ，都有

\dfrac{x+y\sqrt{D}}{2} = \pm\left(\dfrac{x_1+y_1\sqrt{D}}{2}\right)^{3k} = \pm\left(\dfrac{x_3+y_3\sqrt{D}}{2}\right)^k \in \mathbf Z,

所以此时的都是偶数。反过来，对于，总有

\pm\left(\dfrac{x_1+y_1\sqrt{D}}{2}\right)^{3k+r} = \pm\left(\dfrac{x_3+y_3\sqrt{D}}{2}\right)^k\left(\dfrac{x_r+y_r\sqrt{D}}{2}\right).

要证明相应的不是整数，只需要证明该式不是整数，也就是右侧的乘积中第二项不是整数。这在时，就是已知条件；在时，因为

\dfrac{x_2+y_2\sqrt{D}}{2} = \left(\dfrac{x_1+y_1\sqrt{D}}{2}\right)^2 = \dfrac{x_1^2+Dy_1^2}{4} + \dfrac{x_1y_1}{2}\sqrt{D},

而且 $x_1^2+Dy_1^2\equiv 1+1\times 1=2\pmod 4$ ， $x_1y_1\equiv 1\pmod 2$ ，所以该式也不是整数。这就证明了，只有幂次是的倍数的时候，相应的解才都属偶数。

也就是说，方程 $x^2-Dy^2=\pm 4$ 的每三个解中就有一个同时是偶数，它对应着 $x^2-Dy^2=\pm 1$ 的整数解。这也说明，对于 $D\equiv 1\pmod 4$ ，方程有解，当且仅当方程有解。

到目前为止的讨论，已经足够计算实二次整数环的基本单位数。设是正整数且不含平方因子。对于 $D\equiv 2,3\pmod 4$ 的情形，只需要求出 $x^2-Dy^2=\pm 1$ 的最小正整数解；而对于 $D\equiv 1\pmod 4$ 的情形，只需要求出 $x^2-Dy^2=\pm 4$ 的最小正整数解。当得到最小正整数解时，对于 $D\equiv 2,3\pmod 4$ ，基本单位数就是 $\pm x\pm y\sqrt{D}$ ；对于 $D\equiv 1\pmod 4$ ，基本单位数就是 $\dfrac{\pm x\pm y\sqrt{D}}{2}$ 。

示例

求解方程 $x^2-14y^2=\pm 4$ 。

利用前文的示例中的计算可知，方程的最小正整数解为，方程无解。
求解方程 $x^2-41y^2=\pm 4$ 。

对运行 PQa 算法结果如下：（标红部分为第一个循环节）

$\color{red}{1}$
$\color{red}{2}$
$\color{red}{2}$
$\color{red}{1}$
$\color{red}{5}$

循环节长度 $\ell=5$ 为奇数。方程的最小正整数解为，方程的最小正整数解为。它们之间有如下关系：
$\dfrac{4098+640\sqrt{41}}{2} = \left(\dfrac{64+10\sqrt{41}}{2}\right)^2.$
当然，因为 $D\equiv 1\pmod 8$ ，根据前文结论，此时方程 $x^2-41y^2=\pm 4$ 的最小正整数解一定都是偶数，且总是方程 $x^2-41y^2=\pm 1$ 的最小正整数解的倍，所以也可以直接利用前文的示例得出。
求解方程 $x^2-13y^2=\pm 4$ 。

对运行 PQa 算法结果如下：（标红部分为第一个循环节）

$\color{red}{3}$

循环节长度 $\ell=1$ 为奇数。方程的最小正整数解为，方程的最小正整数解为。

因为该方程的最小正整数解都是奇数，所以可以利用第三个循环节末尾处的数对得到相应的（负）Pell 方程 $x^2-13y^2=\pm 1$ 的最小正整数解。它也可以通过直接计算得到：
$\dfrac{36+10\sqrt{13}}{2}=\left(\dfrac{3+\sqrt{13}}{2}\right)^3.$
而且，这是负 Pell 方程的解。相应的 Pell 方程的最小正整数解是。
求解方程 $x^2-52y^2=\pm 4$ 。

因为方程 $x^2-13y^2=\pm 1$ 的最小正整数解分别是和，所以方程 $x^2-52y^2=\pm 4$ 的最小正整数解分别是和。

一般情形

最后，讨论广义 Pell 方程的解法。

对于 $|N|<\sqrt{D}$ 的情形有一个简单的解法。前文的结论说明方程的解一定满足 $\dfrac{x}{y}$ 等于 $\sqrt{D}$ 的某个渐近分数。而且，根据前文讨论的解的结构可知，每个基础解都满足 $x+y\sqrt{D}$ 小于等于相应的 Pell 方程的基础解 $x_1+y_1\sqrt{D}$ 。利用 PQa 算法中分母序列的单调性可知，广义 Pell 方程的这些基础解一定出现在相应的 Pell 方程的基础解出现之前。由此，只需要对运行 PQa 算法，直到 $Q_{\ell'}=1$ 且 $\ell'$ 为偶数时为止，过程中对出现的每个检验是否存在整数使得

A_k^2-DB_k^2 = (-1)^{k+1}Q_{k+1} = N/f^2

成立，如果成立，则记录 $(fA_{k},fB_{k})$ 是一个最小正整数解。这个过程记录的所有就是方程的全部最小正整数解。利用 $(A_{\ell'-1},B_{\ell'-1})$ ，即相应的 Pell 方程的基本解，就可以根据求出的这些最小正整数解，生成广义 Pell 方程的所有解。注意，取决于循环节长度 $\ell$ 是偶数还是奇数，上述的 $\ell'$ 可能是 $\ell$ 或是 $2\ell$ 。

对于更为一般的的情形，上述方法不再适用。首先，枚举的所有平方因子，设，并枚举同余方程 $z^2\equiv D\pmod{|m|}$ 的所有满足 $-|m|/2<z \le |m|/2$ 的解。然后，对运行 PQa 算法，直到 $Q_k=\pm 1$ 或已经结束了一个循环节。在第二种情形，那么与该组相关的方程的解并不存在。在第一种情形，需要进一步判断与否。如果符号一致，那么 $(fG_{k-1},fB_{k-1})$ 就是方程的解。否则，它是方程的解，而且当且仅当相应的负 Pell 方程的解存在时，才可以通过复合它与相应的负 Pell 方程的基本解来得到方程的解。当完成对所有组的遍历之后，就可以得到方程在每个解的等价类中各恰好一个解，且该解为该等价类中的基本解或最小正整数解。利用它们和相应的 Pell 方程的基本解，可以生成该方程的所有整数解。这一算法称为 Lagrange–Matthews–Mollin 算法。

该算法的正确性由如下定理保证：

定理

设方程有整数解且 $x\ge 0, y>0,\gcd(x,y)=1$ 。令，则 $\gcd(Q_0,y)=1$ 。设是同余方程 $x\equiv -P_0y\pmod{Q_0}$ 的解且 $-Q_0/2<P_0\le Q_0/2$ ，并设整数使得成立。那么， $P_0^2\equiv D\pmod{Q_0}$ ， $\dfrac{X}{y}$ 是 $\omega=\dfrac{P_0+\sqrt{D}}{Q_0}$ 的一个渐近分数 $\dfrac{A_{k-1}}{B_{k-1}}$ ，且 $Q_k=(-1)^k\dfrac{N}{|N|}$ 。

证明

利用 $x\equiv -P_0y\pmod{Q_0}$ 和 $x^2-Dy^2=N\equiv 0\pmod{Q_0}$ ，显然有 $P_0^2\equiv D\pmod{Q_0}$ 。因而，

P_0x+Dy\equiv -P_0^2y+Dy = (D-P_0^2)y\equiv 0\pmod{Q_0}.

由此，可以考察整系数矩阵

\begin{pmatrix}P & R \\ Q & S\end{pmatrix} = \begin{pmatrix}X & \dfrac{P_0x+Dy}{Q_0} \\ y & x\end{pmatrix}.

它的行列式

PS-QR = \dfrac{x(x+P_0y)-y(P_0x+Dy)}{Q_0} = \dfrac{x^2-Dy^2}{Q_0} = \pm 1.

而且，设 $\zeta =\sqrt{D} > 1$ ，就有

\dfrac{P\zeta+R}{Q\zeta+S} = \dfrac{(x+P_0y)\sqrt{D}+(P_0x+Dy)}{(x+y\sqrt{D})Q_0} = \dfrac{P_0+\sqrt{D}}{Q_0} = \omega.

下面要证明 $\dfrac{P}{Q}$ 是 $\omega$ 的一个渐近分数。不妨设 $\dfrac{P}{Q}$ 有连分数展开

\dfrac{P}{Q} = [a_0,a_1,\cdots,a_k]

且 $PS-QR = (-1)^{k-1}$ 。如果设 $\dfrac{p_k}{q_k}$ 是它的第个渐近分数，那么，且根据渐近分数的差分公式可知， $p_kq_{k-1}-q_kp_{k-1}=(-1)^{k-1}$ 。这说明

p_k(S-q_{k-1}) = q_k(R-p_{k-1}).

分情况讨论：

如果，那么容易验证，因而 $\omega=P+\zeta^{-1}=[P,\zeta]$ ，故而 $\dfrac{P}{Q}=P$ 是 $\omega$ 的第个渐近分数；
如果，那么且 $P-R=\pm 1$ 。此时，
- 如果，那么 $\omega=R+\dfrac{1}{1+\zeta^{-1}}=[R,1,\zeta]$ ，故而 $\dfrac{P}{Q}=\dfrac{R+1}{1}=[R,1]$ 是 $\omega$ 的第个渐近分数；
- 如果，那么 $\omega=R-1+\dfrac{1}{1+\zeta}=[R-1,\zeta-1]$ ，故而 $\dfrac{P}{Q}=R-1$ 是 $\omega$ 的第个渐近分数；
如果 $Q\neq S>0$ ，那么由于 $Q=q_k\mid(S-q_{k-1})$ ，总存在整数 $\kappa$ 使得 $S=\kappa q_k+q_{k-1}$ 和 $R=\kappa p_k+p_{k-1}$ 成立。因为 $q_k\ge q_{k-1}$ 且，所以 $\kappa\ge 0$ 。因而， $\omega=\dfrac{(\kappa+\zeta)p_k+p_{k-1}}{(\kappa+\zeta)q_k+q_{k-1}}=[a_0,a_1,\cdots,a_k,\kappa+\zeta]$ ，故而 $\dfrac{P}{Q}$ 是它的第个渐近分数。

综上所述，总有 $\dfrac{X}{y}$ 是 $\omega=\dfrac{P_0+\sqrt{D}}{Q_0}$ 的渐近分数，并按照 PQa 算法中的记号记作 $\dfrac{A_{k-1}}{B_{k-1}}$ 。因为 $A_{k-1}^2-DB_{k-1}^2=(-1)^kQ_0Q_k$ ，所以 $Q_k=(-1)^k\dfrac{N}{|N|}$ 。

该定理保证了方程的所有正解都存在于相应的二次无理数的渐近分数中。因为利用 PQa 算法计算渐近分数时，只要进入循环节，就一定能保证渐近分数总是正的。所以，只要枚举所有定理条件所允许的二次无理数，计算它的渐近分数直到一个循环节内，就能够找到一个解。因为在同一个二次无理数的渐近分数中出现的两个解，一定是等价的，所以只要得到第一个满足的解，就可以停止继续后面的计算。与前面的所有算法都不同的是，此处满足条件的可能出现在尚未进入循环节时。

示例

求解方程。

因为，所以对运行 PQa 算法结果如下：（标红部分为第一个循环节）

$\color{red}1$
$\color{red}1$
$\color{red}7$
$\color{red}1$
$\color{red}5$
$\color{red}2$
$\color{red}1$
$\color{red}1$
$\color{red}1$
$\color{red}1$
$\color{red}2$
$\color{red}5$
$\color{red}1$
$\color{red}7$
$\color{red}1$
$\color{red}1$
$\color{red}{24}$

循环节长度 $\ell=17$ 为奇数，所以需要考察两个循环节内 $G_{k-1}^2-157B_{k-1}^2$ 与相差一个平方因子的情形，即的情形。它们对应的解就是下表中的：

$fG_{k-1}$ $fB_{k-1}$

全体就是方程的解集的所有等价类中的最小正整数解。要通过这些解得到全部解，可以利用相应的 Pell 方程的基本解。比如说，可以将它们转化为该等价类中的基本解，相应的解也一并列于上表中。
求解方程。

这次利用 Lagrange–Matthews–Mollin 算法求解。首先，枚举的平方因子:
- 时，有，同余方程 $P^2\equiv 157\pmod{12}$ 有解 $z=\pm 1,\pm 5$ ；
- 时，有，同余方程 $P^2\equiv 157\pmod{3}$ 有解 $z=\pm 1$ 。
对于所有可能的组合运行初始参数为的 PQa 算法，并找到首个的位置，对应的 $(fG_{k-1},fB_{k-1})$ 就是一组解。结果如下表所示：

$fG_{k-1}$ $fB_{k-1}$

这就是前文列举的所有等价类中的最小正整数解，可以利用 Pell 方程的基本解将它们转化为基本解。
求解方程 $x^2-79y^2=\pm 101$ 。

仍然使用 Lagrange–Matthews–Mollin 算法求解。因为是素数，所以一定有。此时，，相应的同余方程 $P^2\equiv 79\pmod{101}$ 有解 $P=\pm 33$ 。

对运行 PQa 算法结果如下：（标红部分为第一个循环节）

$\color{red}2$
$\color{red}3$
$\color{red}5$
$\color{red}1$
$\color{red}1$
$\color{red}1$

循环节长度 $\ell=6$ 为偶数。直到一个循环节结束，都不存在 $Q_k=\pm 1$ ，因而，该情形无解。相应地，对于运行 PQa 算法也可以观察到类似的情况。因此，该方程无解。

习题

参考文献与注释

当是完全平方数时，直接做因式分解可知， $(x+y\sqrt{D})(x-y\sqrt{D})=N$ ，因此所有解可以通过遍历的因数得知。特别地，当时，方程只有解 $(\pm 1,0)$ ；当且 $D\neq 1$ 时，方程没有解。 ↩
有些中文文献也称它为第二型 Pell 方程。 ↩
即形如 $n+\dfrac12$ 且 $n\in\mathbf Z$ 的有理数。 ↩
注意，Pell 方程中基本解的定义与实二次整数环中的基本单位数的定义并不一致。首先，部分实二次整数环中的基本单位数 $x+y\sqrt{D}$ 中的是半整数，因而并非 Pell 方程的解。其次，同一个实二次整数环的基本单位数有四个，但是基本解只有一个，因为基本解要求都是正数。 ↩
一个较为实用的判断方法和工具在这里及其参考文献。使得方程有解的正整数的列表是 OEIS A031396。 ↩

本页面最近更新：2025/2/8 14:17:56，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：c-forrest, Enter-tainer, Great-designer, Menci, NachtgeistW, StudyingFather, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用



			$\color{red}{1}$
			$\color{red}{2}$
			$\color{red}{1}$
			$\color{red}{6}$



			$\color{red}1$
			$\color{red}1$
			$\color{red}7$
			$\color{red}1$
			$\color{red}5$
			$\color{red}2$
			$\color{red}1$
			$\color{red}1$
			$\color{red}1$
			$\color{red}1$
			$\color{red}2$
			$\color{red}5$
			$\color{red}1$
			$\color{red}7$
			$\color{red}1$
			$\color{red}1$
			$\color{red}{24}$





			$\color{red}2$
			$\color{red}3$
			$\color{red}5$
			$\color{red}1$
			$\color{red}1$
			$\color{red}1$



			$\color{red}{3}$

		$fG_{k-1}$	$fB_{k-1}$

				$fG_{k-1}$	$fB_{k-1}$