Pell 方程


二次整数

对于二次有理数 ,此处要求 是不含平方因子的整数。当以下情形成立时:

  • 是整数,
  • 是整数,或者 同时是半整数,

此时称该二次有理数 是二次整数。二次整数与首一整系数二次方程的解构成对应关系。

如果二次整数 的范数 ,则它的倒数也是二次整数,恰好是它的共轭或者共轭的相反数。此时称它为整环 单位数,简称单位数。

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

我们用 Dirichlet 逼近定理来逼近二次根式 。即有无穷个有理数(显然为正有理数)满足:

于是,下面的范数就有:

这是对范数拆出的两项进行估值。这也直观地说明只要有理数与 越接近,范数越小。

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

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

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

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

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

定理:记 。如果有 ,则 一定是 的渐进分数。

证明:分情况讨论。

时,根据 ,有 。并且有

此时根据勒让德判别法, 的渐进分数。

时,原始方程 可以变形为 。变回上一种情况。于是 的渐进分数。由倒数定理, 的渐进分数。

定理:

式中的 也是拉格朗日连分数定理中的 分母。

证明:根据

消去 可以得到

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

分别乘以 ,再相减,得到

证毕。

定理:当且仅当 ,其中 是正整数, 是最短循环周期时,有

证明:

已经知道

是纯循环连分数。并且有

因此 从第 项起余项相同,第 项起分母相同。后续的 完全一致。

因为 ,并且有纯循环的周期性,所以

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

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

定理:如果 都是 的一组整数解,那么

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

Pell 方程

我们给出两个不定方程:,若 为完全平方数,则第一个方程只有解 ,第二个方程无解。

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

,它的循环连分数周期为 ,渐近分数为 ,则:

  • 为偶数时,第一个方程的全体正解为 ,第二个方程无解。
  • 为奇数时,第一个方程的全体正解为 ,第二个方程的全体正解为

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

  • 为偶数时,第一个方程的全体解为 ,第二个方程无解。
  • 为奇数时,第一个方程的全体正解为 ,第二个方程的全体正解为

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

定理:记 Pell 方程 使得 最小的一组正整数解为基本解 ,则方程的全部正整数解为

证明:

假如有一组正整数解 不出现在上述序列中。因为 ,所以必然有

两边同时乘 ,也就是除以 ,有

并且 也是一组整数解。有

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

定理:对于具有奇数位循环节的 ,记最小的一组满足 的正整数解为 ,则满足 的所有解由

给出。并且 满足 满足

证明完全同上。

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

定理:如果 连分数循环节长度为奇数,并且 存在唯一的平方和表示 ,则两个方程 至少有一个有解。

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

证明:

根据伽罗瓦连分数定理,对称的余项 循环部分恰好相反,因此互为倒数负共轭。

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

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

由于得到余项的前面的操作为取倒数,即负共轭,再前面为取整,下标 的余项 分母应当与下标 这项相同,即

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

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

定理:如果 存在唯一的平方和表示 ,并且 ,则方程 无解。

例如对于 ,于是 无解。

证明:

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

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

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

如果想直接求解 形式时的基本单位数,改令 ,并规定这里的连分数第零项为半整数,重复上述操作,并将结果乘 (提出二分之一)。

例如当 的时候, 的半整数连分数表示为:

于是解得基本单位数

但是 的时候, 的半整数连分数表示为:

于是解得基本单位数 。它不属于半整数形式。

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

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

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

如果基本解(或基本单位数) 是对应的二次方程 的解,则有递推:

事实上,

斐波那契数列(的一半)与卢卡斯数列(的一半)恰好组合成了基本单位数 的全体幂,即使引入负下标也成立。这是它们的很多性质的来源。

贡献者:@Tifa@Menci@Great-designer@夜轮_NachtgeistW

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组