Pell Equation

二次整数

对于二次有理数 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-dy^{2}=1 和 x-dy^{2}=-1 ，若 d 为完全平方数，则第一个方程只有解 (\pm1,0) ，第二个方程无解。若 d 不为完全平方数，设 \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 。

这就是典型的循环连分数渐进分数与二次有理数乘法的对应关系。

对于 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 的解，则有递推：

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

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

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments