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


评论