跳转至

Pell 方程

二次整数

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

  • \(a\) 与 \(b\) 是整数，\(D \equiv 2 \pmod 4\) 或 \(D \equiv 3 \pmod 4\)。
  • \(a\) 与 \(b\) 是整数，或者 \(a\) 与 \(b\) 同时是半整数，\(D \equiv 1 \pmod 4\)。

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

如果二次整数 \(a+b\sqrt{D}\) 的范数 \(a^2-Db^2\) 为 \(1\) 或 \(-1\)，则它的倒数也是二次整数，恰好是它的共轭或者共轭的相反数。此时称它为整环 \(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\)，即这个新渐进分数也是单位数。由于第 \(-1\) 个渐进分数规定为 \(\frac{1}{0}\)，对应的二次整数范数为 \(1\)，那么只要计算每个循环节处前一个渐进分数即可。

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

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

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

定理：记 \(x^2−Dy^2=s\)。如果有 \(|s|<\sqrt{D}\)，则 \(\frac{x}{y}\) 一定是 \(\sqrt{D}\) 的渐进分数。

证明：分情况讨论。

当 \(s>0\) 时，根据 \(x^2−Dy^2>0\)，有 \(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}\) 的渐进分数。

当 \(s<0\) 时，原始方程 \(x^2−Dy^2=s\) 可以变形为 \(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\) 分母。

证明：根据

\[ 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}} \]

消去 \(r\) 可以得到

\[ 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\)、\(q_k\)，再相减，得到

\[ {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} \]

证毕。

定理：当且仅当 \(k=nL\)，其中 \(n\) 是正整数，\(L\) 是最短循环周期时，有 \(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}\) 从第 \(1\) 项起余项相同，第 \(0\) 项起分母相同。后续的 \(Q_k\) 完全一致。

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

纯循环连分数的余项也纯循环。当 \(Q_k=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 \]

根据 \(L\) 为最短周期，有 \(k=nL\)。证毕。

定理：如果 \((x_1, y_1)\) 和 \((x_2, y_2)\) 都是 \(x^2-Dy^2=1\) 的一组整数解，那么

\[ X=x_1x_2+y_1y_2D \]
\[ Y=x_1y_2+x_2y_1 \]

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

\[ 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\)，若 \(D\) 为完全平方数，则第一个方程只有解 \((\pm1,0)\)，第二个方程无解。

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

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

  • 当 \(l\) 为偶数时，第一个方程的全体正解为 \(x=p_{jl-1},y=q_{jl-1},j=1,2,3,\cdots\)，第二个方程无解。
  • 当 \(l\) 为奇数时，第一个方程的全体正解为 \(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\)。

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

  • 当 \(l\) 为偶数时，第一个方程的全体解为 \(x+y\sqrt{D}=\pm(p_{l-1}\pm q_{l-1}\sqrt{D})^{j},j=0,1,2,\cdots\)，第二个方程无解。
  • 当 \(l\) 为奇数时，第一个方程的全体正解为 \(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^2-Dy^2=1\) 使得 \(x+y\sqrt{D}\) 最小的一组正整数解为基本解 \((x_1, y_1)\)，则方程的全部正整数解为

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

证明：

假如有一组正整数解 \((X, Y)\) 不出现在上述序列中。因为 \(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} \]

并且 \((S, T)\) 也是一组整数解。有

\[ 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 \]

因此 \((S, T)\) 是一组正整数解。这与 \((x_1, y_1)\) 的选取矛盾。证毕。

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

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

给出。并且 \((x_{2n}, y_{2n})\) 满足 \(x^2-Dy^2=1\)，\((x_{2n-1}, y_{2n-1})\) 满足 \(x^2-Dy^2=-1\)。

证明完全同上。

方程 \(x^2-Dy^2=1\) 必然有解，而方程 \(x^2-Dy^2=-1\) 不一定有解，有解等价于连分数循环节长度为奇数。

定理：如果 \(\sqrt{D}\) 连分数循环节长度为奇数，并且 \(D\) 存在唯一的平方和表示 \(D=r^2+s^2\)，则两个方程 \(x^2-Dy^2=r\)、\(x^2-Dy^2=s\) 至少有一个有解。

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

证明：

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

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

\[ \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 \]

因为 \(D\) 的平方和表示是唯一的，所以下标 \(v\) 必然有 \(P_v=r\)、\(Q_v=s\)，或者 \(P_v=s\)、\(Q_v=r\)。

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

由于连分数的结论有 \(x^2-Dy^2=(-1)^vQ_v\) 的解为相应渐进分数，因此上述两个方程必然存在一个解，为下标 \(v\) 或 \(v-1\) 的渐进分数。证毕。

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

定理：如果 \(D\) 存在唯一的平方和表示 \(D=r^2+s^2\)，并且 \(r, s\equiv\pm 3 \pmod 8\)，则方程 \(x^2-Dy^2=-1\) 无解。

例如对于 \(34\) 有 \(34=3^2+5^2\)，于是 \(x^2-34y^2=-1\) 无解。

证明：

如果方程 \(x^2-Dy^2=-1\) 有解，则两个方程 \(x^2-Dy^2=r\)、\(x^2-Dy^2=s\) 至少有一个有解。模 \(8\) 就得到了矛盾。证毕。

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

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

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

例如当 \(D\) 为 \(5\) 的时候，\(\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}\)。

但是 \(D\) 为 \(17\) 的时候，\(\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}\)。它不属于半整数形式。

在 \(1\) 到 \(100\) 中，\(5\)，\(13\)，\(29\)，\(53\)，\(61\) 和 \(85\) 的基本单位数属于这种分母中含 \(2\) 的半整数形式，而 \(17\)，\(37\)，\(41\)，\(65\)，\(73\)，\(89\) 和 \(97\) 的基本单位数属于非半整数形式。

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

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

如果基本解（或基本单位数）\(a+b\sqrt{D}\) 是对应的二次方程 \(x^2+px+q=0\) 的解，则有递推：

\[ \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}\) 的全体幂，即使引入负下标也成立。这是它们的很多性质的来源。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用