Pell 方程

二次整数

对于二次有理数 $a+b\sqrt{D}$ ，此处要求是不含平方因子的整数。当以下情形成立时：

与是整数， $D \equiv 2 \pmod 4$ 或 $D \equiv 3 \pmod 4$ 。
与是整数，或者与同时是半整数， $D \equiv 1 \pmod 4$ 。

此时称该二次有理数 $a+b\sqrt{D}$ 是二次整数。二次整数与首一整系数二次方程的解构成对应关系。

如果二次整数 $a+b\sqrt{D}$ 的范数为或，则它的倒数也是二次整数，恰好是它的共轭或者共轭的相反数。此时称它为整环 $Z(\sqrt{D})$ 的 单位数，简称单位数。

可以证明，存在 基本单位数，使得全体单位数都可以表示成为基本单位数的幂（或幂的相反数）。它也就是对应 Pell 方程的 基本解，通解可以表示为基本解的幂（或幂的相反数）。

我们用 Dirichlet 逼近定理来逼近二次根式 $\sqrt{D}$ 。即有无穷个有理数（显然为正有理数）满足：

\left|\frac{x}{y}-\sqrt{D}\right|\leqslant\frac{1}{y^2}

于是，下面的范数就有：

\left|N(x+y\sqrt{D})\right|=|x-y\sqrt{D}||x+y\sqrt{D}|\leqslant\frac{1}{y}(\frac{1}{y}+2y\sqrt{D})\leqslant2\sqrt{D}+1

这是对范数拆出的两项进行估值。这也直观地说明只要有理数与 $\sqrt{D}$ 越接近，范数越小。

因此，范数较小的二次整数有无限个，进而采用一些手段，就可以推出范数为 $\pm 1$ 的单位数存在，也存在无限个。

进而可以发现，对于所有 $\sqrt{D}$ 的渐进分数，配上系数之后得到的二次整数的范数都落在非常小的区间。由于 $\sqrt{D}$ 的渐进分数是余数循环的，只要其中出现使得范数为 $\pm 1$ 的渐进分数，经过一个循环之后新的渐进分数凑成的二次整数也应当满足范数为 $\pm 1$ ，即这个新渐进分数也是单位数。由于第个渐进分数规定为 $\frac{1}{0}$ ，对应的二次整数范数为，那么只要计算每个循环节处前一个渐进分数即可。

根据上逼近与下逼近的结论，第奇数个渐进分数得到的范数为负，偶数个为正。即是否存在范数为的二次整数取决于循环连分数的循环节长度是否为奇数。

最后还有一个结论，每经过一个循环，相当于旧的二次整数乘上了一个单位数，得到新的二次整数。因此上面得到的单位数是基本单位数。这样，就提供了一种 Pell 方程通解的直接计算方法。

连分数过渡到 Pell 方程的一些定理

定理：记。如果有 $|s|<\sqrt{D}$ ，则 $\frac{x}{y}$ 一定是 $\sqrt{D}$ 的渐进分数。

证明：分情况讨论。

当时，根据，有 $x>y\sqrt{D}$ 。并且有

\left|\frac{x}{y}-\sqrt{D}\right|=\frac{s}{y(x+y\sqrt{D})}<\frac{s}{2y^2\sqrt{D}}<\frac{1}{2y^2}

此时根据勒让德判别法， $\frac{x}{y}$ 是 $\sqrt{D}$ 的渐进分数。

当时，原始方程可以变形为 $y^2−\frac{1}{D}x^2=-\frac{s}{D}$ 。变回上一种情况。于是 $\frac{y}{x}$ 是 $\frac{1}{\sqrt{D}}$ 的渐进分数。由倒数定理， $\frac{x}{y}$ 是 $\sqrt{D}$ 的渐进分数。

定理：

{p_k}^2-D{q_k}^2={(-1)}^{k+1}Q_{k+1}

式中的 $Q_{k+1}$ 也是拉格朗日连分数定理中的分母。

证明：根据

r_{k+1}=\frac{P_{k+1}+\sqrt{D}}{Q_{k+1}}

\sqrt{D}=\frac{r_{k+1}p_k+p_{k-1}}{r_{k+1}q_k+q_{k-1}}

消去可以得到

p_k P_{k+1}+p_{k-1}Q_{k+1}+p_k\sqrt{D}=q_k D+(q_k P_{k+1}+q_{k-1}Q_{k+1})\sqrt{D}

根据有理项和无理项对应相等，有

p_k=q_k P_{k+1}+q_{k-1}Q_{k+1}

q_k D=p_k P_{k+1}+p_{k-1}Q_{k+1}

分别乘以、，再相减，得到

{p_k}^2−D{q_k}^2=(p_kq_{k−1}−p_{k−1}q_k)Q_{k+1}={(−1)}^{k−1}Q_{k+1}={(−1)}^{k+1}Q_{k+1}

证毕。

定理：当且仅当，其中是正整数，是最短循环周期时，有。

证明：

已经知道

\Delta+\sqrt{D}

是纯循环连分数。并且有

r_1(\sqrt{D})=r_1(\Delta+\sqrt{D})

Q_0(\sqrt{D})=Q_0(\Delta+\sqrt{D})=1

因此 $\sqrt{D}$ 和 $\Delta+\sqrt{D}$ 从第项起余项相同，第项起分母相同。后续的完全一致。

因为，并且有纯循环的周期性，所以 $Q_{nL}=1$ 。

纯循环连分数的余项也纯循环。当时，有

r_k=P_k+\sqrt{D}>1

-1<P_k-\sqrt{D}<0

P_k<\sqrt{D}<P_k+1

P_k=\lfloor\sqrt{D}\rfloor=\Delta

r_k=\Delta+\sqrt{D}=r_0

根据为最短周期，有。证毕。

定理：如果和都是的一组整数解，那么

也是方程的一组整数解。这是因为

X+Y\sqrt{D}=(x_1+y_1\sqrt{D})(x_2+y_2\sqrt{D})

Pell 方程

我们给出两个不定方程： $x^2-Dy^{2}=1$ 和 $x^2-Dy^{2}=-1$ ，若为完全平方数，则第一个方程只有解 $(\pm1,0)$ ，第二个方程无解。

若不为完全平方数，称形如此类的方程为 Pell 方程。根据相应的二次整环不同，一般研究的 Pell 方程分为、、、四类。

设 $\xi_{0}=\sqrt{D}$ ，它的循环连分数周期为，渐近分数为 $\frac{p_{n}}{q_{n}}$ ，则：

当为偶数时，第一个方程的全体正解为 $x=p_{jl-1},y=q_{jl-1},j=1,2,3,\cdots$ ，第二个方程无解。
当为奇数时，第一个方程的全体正解为 $x=p_{jl-1},y=q_{jl-1},j=2,4,6,\cdots$ ，第二个方程的全体正解为 $x=p_{jl-1},y=q_{jl-1},j=1,3,5,\cdots$ 。

还有另一种更加简单的表示方法：

当为偶数时，第一个方程的全体解为 $x+y\sqrt{D}=\pm(p_{l-1}\pm q_{l-1}\sqrt{D})^{j},j=0,1,2,\cdots$ ，第二个方程无解。
当为奇数时，第一个方程的全体正解为 $x+y\sqrt{D}=\pm(p_{l-1}\pm q_{l-1}\sqrt{D})^{j},j=0,2,4,\cdots$ ，第二个方程的全体正解为 $x+y\sqrt{D}=\pm(p_{l-1}\pm q_{l-1}\sqrt{D})^{j},j=1,3,5,\cdots$ 。

这是循环连分数渐进分数与二次有理数乘法的对应关系。该结论由下面的定理给出。

定理：记 Pell 方程使得 $x+y\sqrt{D}$ 最小的一组正整数解为基本解，则方程的全部正整数解为

x_n+y_n\sqrt{D}=(x_1+y_1\sqrt{D})^n

证明：

假如有一组正整数解不出现在上述序列中。因为 $x_1+y_1\sqrt{D}>1$ ，所以必然有

(x_1+y_1\sqrt{D})^n<X+Y\sqrt{D}<(x_1+y_1\sqrt{D})^{n+1}

两边同时乘 $x_n-y_n\sqrt{D}$ ，也就是除以 $(x_1+y_1\sqrt{D})^n$ ，有

1<S+T\sqrt{D}<x_1+y_1\sqrt{D}

并且也是一组整数解。有

0<S-T\sqrt{D}=\frac{1}{S+T\sqrt{D}}<1

2S=S+T\sqrt{D}+S-T\sqrt{D}>0

2T\sqrt{D}=S+T\sqrt{D}-(S-T\sqrt{D})>0

因此是一组正整数解。这与的选取矛盾。证毕。

定理：对于具有奇数位循环节的 $\sqrt{D}$ ，记最小的一组满足的正整数解为，则满足 $x^2-Dy^2=\pm 1$ 的所有解由

x_n+y_n\sqrt{D}=(x_1+y_1\sqrt{D})^n

给出。并且 $(x_{2n}, y_{2n})$ 满足， $(x_{2n-1}, y_{2n-1})$ 满足。

证明完全同上。

方程必然有解，而方程不一定有解，有解等价于连分数循环节长度为奇数。

定理：如果 $\sqrt{D}$ 连分数循环节长度为奇数，并且存在唯一的平方和表示，则两个方程、至少有一个有解。

如果了解高斯整数的知识，只有当一个数所有的型素因子均成对，这个数才能进行平方和表示，此时平方和表示的个数就是这个数含有的型素因子数的个数。

证明：

根据伽罗瓦连分数定理，对称的余项和 $r_{l+1-k}$ 循环部分恰好相反，因此互为倒数负共轭。

因为循环节是奇数，连分数展开中对称部分最中间的余项与自己互为倒数负共轭。记对称部分最中间位置下标为。于是有

\left(\frac{P_v-\sqrt{D}}{Q_v}\right)=-\frac{1}{\left(\frac{P_v+\sqrt{D}}{Q_v}\right)}

D={P_v}^2+{Q_v}^2

因为的平方和表示是唯一的，所以下标必然有、，或者、。

由于得到余项的前面的操作为取倒数，即负共轭，再前面为取整，下标的余项 $\left\lfloor\frac{P_{v-1}+\sqrt{D}}{Q_{v-1}}\right\rfloor$ 分母应当与下标这项相同，即 $Q_v=Q_{v-1}$ 。

由于连分数的结论有的解为相应渐进分数，因此上述两个方程必然存在一个解，为下标或的渐进分数。证毕。

如果直接对方程两端取模，能够知道 $D\equiv 1 or 2 \pmod 8$ 。然而，这只是一个充分条件，而非必要条件。通过取模的方式确定什么时候方程有解，基本做不到。例如，可以给出一个无解的充分条件：

定理：如果存在唯一的平方和表示，并且 $r, s\equiv\pm 3 \pmod 8$ ，则方程无解。

例如对于有，于是无解。

证明：

如果方程有解，则两个方程、至少有一个有解。模就得到了矛盾。证毕。

对于为形式的时候，有可能相应基本单位数的系数是半整数。此时有结论：如果为形式时，相应基本单位数的系数是半整数，则基本单位数的三次方系数为整数。

此时，上述方法求出的基本解不是基本单位数，而是基本单位数的三次方。

如果想直接求解为形式时的基本单位数，改令 $\xi_{0}=\frac{\sqrt{D}}{2}$ ，并规定这里的连分数第零项为半整数，重复上述操作，并将结果乘（提出二分之一）。

例如当为的时候， $\frac{\sqrt{5}}{2}$ 的半整数连分数表示为：

\frac{\sqrt{5}}{2}=[\frac{1}{2},\overline{1}]

\frac{1}{2}=\frac{1}{2}\frac{1}{1}

于是解得基本单位数 $\frac{1}{2}+\frac{\sqrt{5}}{2}$ 。

但是为的时候， $\frac{\sqrt{17}}{2}$ 的半整数连分数表示为：

\frac{\sqrt{17}}{2}=[\frac{3}{2},\overline{1,1,3}]

\frac{3}{2}+\frac{1}{1+\frac{1}{1}}=\frac{3}{2}+\frac{1}{2}=\frac{1}{2}\frac{4}{1}

于是解得基本单位数 $4+\sqrt{17}$ 。它不属于半整数形式。

在到中，，，，，和的基本单位数属于这种分母中含的半整数形式，而，，，，，和的基本单位数属于非半整数形式。

如果快速求解第个解（或第个单位数），只需要求出基本解（或基本单位数），然后借助快速幂的想法去乘就可以了。注意乘一个二次有理数的时候，与的变化是一个递推关系。

如果要求从头开始连续若干个解（或连续若干个单位数），与的变化就是一个固定的递推关系，相邻三项一定满足特征方程，即基本解（或基本单位数）对应的二次三项式。即：

如果基本解（或基本单位数） $a+b\sqrt{D}$ 是对应的二次方程的解，则有递推：

\begin{aligned} a_n+pa_{n-1}+qa_{n-2}&=0\\ b_n+pb_{n-1}+qb_{n-2}&=0 \end{aligned}

事实上，斐波那契数列（的一半）与卢卡斯数列（的一半）恰好组合成了基本单位数 $\frac{1}{2}+\frac{1}{2}\sqrt{5}$ 的全体幂，即使引入负下标也成立。这是它们的很多性质的来源。

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