动机
方程 看来像一个没有停止准则的搜索。逐一测试较大的 有时很快找到解,但 的第一组正解已是 。完整理论须解释解为何存在、搜索为何能找到,以及一个解怎样生成其余所有解。
表达式 把问题连起来。乘法保持范数 ,共轭则把根号项变号。连分数给出无限多个逼近,其非零整数范数却留在有界集合内。重复论证于是产生范数一的元素;离散性再给出最小正单位,把乘法化为完整分类。
全章设 是非平方整数,未必无平方因子。所用先备定理为上一章已证的收敛、误差界及 Legendre 判据,不假设所有二次无理数连分数的周期定理。
定义
定义 7.4.1
(本章的二次整数、共轭与范数)
令 ,乘法取通常实数乘法。因 无理,表示唯一。定义 ,以及 。共轭保持加法与乘法,故 。
的单位是在 内有乘法逆元的元素。这恰好等价于范数为 或 :必要性由整数范数相乘得出,充分性由 得出。正单位指作为实数大于零。本章不宣称此环一定是该二次域的全体代数整数环。
正 Pell 方程要求范数一,负 Pell 方程要求范数负一。正解是 。单位还包括 及共轭,所以全体单位的结构比正解列表包含更多信息。
定理
定理 7.4.2
(存在性与最小生成单位)
对每个非平方整数 , 都有 的解。在两种范数的所有大于一单位中,有最小者 。每个正单位唯一写成 ,其中 ;全体单位为 。
若 ,便不存在负一范数单位,范数一正解恰为 的系数,。若 ,范数一正解为 的系数,;负一范数正解为 的系数,。
概念视角几何
单位是双曲线上的一条轨道
设 是大于一的最小范数一单位。乘以 在系数对上的作用是
这是行列式为 的整数矩阵,其逆(乘以 )也是整数矩阵。它保持 以及每条曲线 。定理是说: 在 分支上的整点恰好构成这个矩阵的一条轨道,即 的轨道。
定理 7.4.3
(每个正 Pell 解都来自渐近分数)
若 且 ,则 是 的既约渐近分数。因此逐个测试渐近分数的范数是否为一,必会终止,并先找到最小的大于一范数一单位;若测试两种符号,先找到的便是 。这是终止与分类定理,并无宣称多项式时间复杂度。
证明思路
有界范数产生真正单位
证明
(重复的范数与剩余类对给出单位)
令 为 的渐近分数。分母趋向无限,误差小于 。对充分大的 ,有 且 。所以非零整数
满足
非零性来自无理性。可取值的整数有限,所以无限多对有相同范数 。再取无限子序列,使 模 也相同。正实数 无界,可选其中 。
把商的分母有理化,得
两个分子都被 整除:模 ,第一个同余 ,第二个同余零。所以商在 内,范数一,且大于一。记为 ;其共轭是正数 ,因此
商已在 内,故这些系数是整数,存在性得证。仅有范数重复还不保证商整系数;剩余类对也重复,才补上这一步。
先用离散性,再用幂作除法
证明
(先求最小单位,再用幂作除法)
对单位 ,其共轭绝对值为 ,所以整数系数满足 、。可行整数对有限。存在性已给一个大于一单位,在不超过它的有限个单位中取最小者 。
给定正单位 ,选唯一整数 使 。因 的幂向上无界、向下趋零,这个整数存在。于是 是位于 的正单位,由最小性只能是一。因此 。不同幂有不同实数值;每个负单位则是某正单位的负值。
由范数乘法性,,立即得到所述奇偶区分。若两种范数的单位 ,代入 的系数式便知 ;零与一之间的单位则必有一个负系数:范数为一时 为负,范数为负一时 为负,例如 。所以定理指定的幂范围恰好列尽正解。
证明透视
两个作用不同的有限性论证
存在性利用范数与剩余类只有有限选择,制造整系数的商。分类则利用有界实数区间内只有有限整数系数对,取得最小生成单位。两者都不能只由几个已见解推出。一旦最小者存在,除以它的幂便排除相邻幂之间还藏着其他单位。
连分数为何先找到最小解
证明
(Legendre 判据与解的次序)
正解的 若有公因数,其平方须整除一,所以分数既约。有理化给出
范数一时 ;范数负一时,由 (因为 )得 ,所以分母的括号仍大于二。Legendre 判据遂证明它是渐近分数。
在两种符号的正解中, 增大会使 严格增大。若 ,则 ,连最小可能的 也大于最大可能的 。固定正 时两种范数不能同时出现,因为非负整数平方不能相差二。渐近分数的分母除最初可能同为一外严格递增,而这最初两个也不能同为 Pell 解。因此第一个测到的解,正是指定范数类中的最小单位;存在性保证范数一测试最终成功。
平方根尾项的精确有限状态计算
尾项可用整数运算产生,无须四舍五入的平方根。设 。若 ,定义
把 取倒数并有理化,便得下一尾项。归纳保持 整数、、 及 。由 得整除性保持。正的分数部分给出 ,而 及 给出下界。因此 是正整数且至多为 。取整公式精确,因把 改为 只把整数分子减少严格介于零、一之间的量,除以正整数后不会越过下一整数。
整数状态 只有有限个,下一状态又由当前状态唯一决定,所以某状态重现后,往后全部重复。这证明本类平方根展开最终周期性;并未证明所有最终周期实连分数的完整刻画,也没有用周期长度奇偶规则判定负方程。
例题
例题 7.4.4
(平方根二与负范数生成单位)
的首个渐近分数 范数为 ,已是两符号中的第一个正解,故 。其平方 是最小的大于一范数一单位。 的全部正解为 的系数,,首三组是 。负范数正解来自 的奇数次幂,首几组为 。指数奇偶性来自范数同态。
例题 7.4.5
(有局部障碍的负方程)
的首几个渐近分数是 ,范数为 ,故 范数一。另一方面,负方程 模三要求 ,但平方剩余只有零与一,故不可能。全部范数一正解是 的正整数次幂,首几组为 。局部不可能性与整体单位分类互相吻合。
例题 7.4.6
(十三的首个正范数解为何很大)
精确尾项计算给出 。到六之前的渐近分数是 ,范数为 。所以两符号中最小的大于一单位是 ,最小范数一单位是其平方:
验算为 。过早停止的直接搜索会漏掉它。这里由逼近判据及排序证明保证最小性;单独展示等式只能保证它是一组解。
反例模式
渐近分数未必解任何一个 Pell 方程
的渐近分数 范数是 。每个正 Pell 解都是渐近分数,但逆命题不成立;误差判据只确定解出现的位置,仍须测试整数范数。此外不能把非平方参数定理用于平方 :此时 迫使范数一方程的 。
常见错误
常见错误
(环是 ,小于一的单位有负系数)
本章的环明确是 ;改用完整代数整数环,单位生成元可能改变。对 ,较大的环含有 ,其范数为 ,而 才是本章所得的生成元。正实数单位若小于一,也可以有负系数, 就是例子。
常见错误
(最小单位不一定范数为一)
两种范数共用的最小生成单位,未必解正 Pell 方程;范数为负一时须取平方。例如 时, 的范数是 ,最小的范数一单位是 。
常见错误
(仅有相同范数不能给出整系数商)
范数重复不足以保证整系数商,还须匹配剩余类。对 ,渐近分数 与 的范数都是 ,因为 。它们模 的剩余类对分别是 与 ,而事实上
同理,有限部分商串也不能单靠外观证明周期,须有精确重复状态;搜索已证会终止,不代表对很大的 已证计算很快。
小结
小逼近误差使渐近分数的整数范数有界。范数与剩余类同时重复,便产生正的范数一单位;离散性再给出最小生成元及全部幂分类。Legendre 判据把每个正 Pell 解放进渐近分数序列,令精确搜索同时具备终止性与完备性。
练习
快速检查
(对 ,求两种范数中最小的大于一单位,以及范数一的最小者,并写出两个 Pell 方程的全部正解。)
精确计算第一尾项 。
解答 · 答案
第一尾项为 ,整数部分四,分数部分与原输入相同,故 。首个 范数负一,所以 ,。范数一正解为 的系数,;负一正解为 的系数,。单位定理排除其他解。
快速检查
(若 是最小的大于一范数一单位,推导生成全部范数一正解的整数递推。对 从 计算下一步。)
把 乘以 ,再比较系数。
解答 · 答案
把 乘以 ,得到 、,起始为 。幂分类证明列尽。 的下一组为 。
快速检查
(证明 的全体整数解由 ,,表示。交代负 及额外负号怎样影响 。)
由分类 及范数的奇偶出发。
解答 · 答案
若 ,取 ;否则取 。由奇偶计算,全体范数一单位恰为 。 时系数皆正; 时共轭给出 ,其中 。乘负一则同时反转两系数符号。 给 ,所以全部整数符号情形都已交代,没有添入不存在的 正解。
快速检查
(直接证明 不可能,再用 找最小范数一正单位。以精确尾项证明此重复展开。)
对负方程在模 下考虑。
解答 · 答案
模三要求 ,不可能。 第一尾项是 ,整数部分二;下一个是 ,整数部分四;其后回到第一尾项。首两个渐近分数为范数负二的 ,及范数一的 。所以最小大于一单位是 ,范数一正解为其正整数次幂;局部障碍也独立排除了负范数单位。