广义 Pell 方程的有限范数轨道

无穷大解为什么可以退回一小段 ​

由数域范数理路数域范数Number field norm · Field norm over the rationals将数域元素的乘法视作有理线性算子，以行列式定义范数并用于整数环中的因子约束。的乘法性，乘以范数一单位保持 $N$。乘法的坐标形式是

逆变换为 $(x,y)\mapsto (ux-Dvy,-vx+uy)$，二者都保持整数格点。因而这不是在实数双曲线上随意缩放，而是在允许的整数解之间可逆移动。

给定 $\alpha >0$，由于 $\epsilon >1$，存在唯一整数 $k$，使

取 $\beta =\alpha {\epsilon }^{-k}$，便落入指定半开区间，且仍有整数坐标与范数 $N$。若两个种子相差 ${\epsilon }^j$，较大者至少是较小者的 $\epsilon$ 倍，会跨过区间右端；因此只能 $j=0$。这是“找全”和“不重复”来自同一个缩减区间的原因。

当原 $\alpha <0$ 时先整体取负。因为 $N\ne 0$，$\alpha$ 不会等于零，故正负分流也唯一。这里允许的只是整体负号；单独改变一个坐标相当于共轭后再改号，可能进入另一条种子轨道。

从一个实数区间推导整数搜索界 ​

共轭满足 ${\beta }^{\prime }=N/\beta$，于是

若 $N>0$，当 $\beta \ge \sqrt{N}$ 时有 $X>0,Y\ge 0$。函数 $\beta -N/\beta$ 严格递增，所以区间上界给出

反过来，对任一 $Y\ge 0$，取满足方程的正 $X=\sqrt{D{Y}^2+N}$，则 $\beta =X+Y\sqrt{D}$ 随 $Y$ 严格增加；$Y=0$ 对应下端，$Y=v\sqrt{N}$ 对应上端。因此这个界不仅必要，也足够。

若 $N=-M<0$，则

后者在 $\beta \ge \sqrt{M}$ 上严格递增，故

给定非负 $X$ 和正 $Y$ 满足方程，$\beta \ge \sqrt{M}$；同样的单调性说明该严格界也足以保证 $\beta$ 未跨过上端。把两种界分别平方，正好得到形式陈述中的纯整数检查。

D=13、N=4：三个种子，而不是一个 ​

取 $\epsilon =649+180\sqrt{13}$。正右端的搜索范围为

逐个检查 $13Y^2+4$ 的整数平方根，在 $Y=0,\dots ,359$ 中只有三次成功：

因此全部解为

三条正实值轨道互不相同，因为三个种子已各自在同一个半开基本区间。完整有限平方检查是可复算证书；“试了三个小解”本身没有这样的穷尽性。

右端点为 $2\epsilon =1298+360\sqrt{13}$。它也是解，但已由第一个种子乘一次单位得到。若错误地把搜索界写成 $Y\le 360$，便会重复收入同一条轨道。

单独把 $Y$ 改号也未必留在原轨道。例如

这说明共轭将第二条正实值轨道送到第三条，而不是只改变同一轨道内的指数。

负右端允许种子的X为零 ​

对 $D=2,N=-2$，正Pell基本单位为 $3+2\sqrt{2}$。搜索界为 $2Y^2<9\cdot 2$，即 $Y=1,2$；检查 $2Y^2-2$，只有 $Y=1$ 给出平方零。唯一种子是 $\sqrt{2}$，全部解为

若把非负平方根条件错写成正平方根，就会丢掉这条方程的唯一种子。种子允许 $X=0$，不代表原数 $\beta =\sqrt{2}$ 为零。

有限种子也可能一个都没有 ​

对 $D=2,N=3$，仍用 $\epsilon =3+2\sqrt{2}$，只需检查 $Y^2<12$，即 $Y=0,1,2,3$。相应 $2Y^2+3$ 为 $3,5,11,21$，全不是平方。因此 $x^2-2y^2=3$ 没有整数解。这里已经排除任意大的坐标，因为所有解若存在都应缩减到这四个候选之一。

若 $N=0$，非平方 $D$ 使唯一整数解为 $(0,0)$，应在此算法之前处理。若 $D$ 是平方，则方程改为两个整数因子的乘积等于 $N$，也不是本页的无限单位轨道问题。

认证一个大解属于哪一族 ​

对 $N>0$，若 $x>0$，则 $x+y\sqrt{D}>0$，且是否低于 $\sqrt{N}$ 正好由 $y<0$ 决定；在 $y\ge 0$ 时，是否达到上端由 $y^2\ge v^{2}N$ 决定。因此可以用整数逆矩阵不断缩减，不必先计算对数或近似平方根。

负右端先使 $y>0$，这等价于令 $\alpha >0$。此时 $x<0$ 表示低于下端，需乘一次或多次 $\epsilon$；$x\ge 0$ 后，用 $D{y}^2\ge u^2|N|$ 判断是否还应除以 $\epsilon$。每一步同时记录指数，最终核对有限种子列表，再用整数乘法恢复原解。

种子枚举只需保存输出列表；候选个数约为正右端的 $v\sqrt{N}$，或负右端的 $u\sqrt{|N|/D}$。这是一个保证停止的算法，未必是高效算法：基本Pell单位本身可能极大，整数平方根检查和后续坐标输出也有位长成本。可使用更窄、以 $\sqrt{\epsilon }$ 为中心的约化区间改善搜索，但需要另行处理符号和端点，本页不把那种不同约定混进当前证书。

保持方程还要保持整数坐标环 ​

负Pell单位理路负 Pell 方程与周期奇偶性Negative Pell equation · Negative Pell solvability criterion · 负Pell方程以平方根连分数的周期长度奇偶性完整判定负Pell可解性，证明全部解的奇次幂结构，并用D=34区分模同余条件与整数方程。的范数为负一，乘它会将右端 $N$ 改成 $-N$，不能作为当前纤维内的一步。完整整数环中的单位还可能带半整数坐标，未必保持整个 $\mathbb{Z}[\sqrt{D}]$。

D=13的例子尤其容易混淆：令 $\theta =(3+\sqrt{13})/2$，则三个种子分别为 $2,2{\theta }^2,2{\theta }^4$，而 $\epsilon ={\theta }^6$。这不使本页的三条轨道合为一条，因为本页只用整数Pell单位的幂作用。若另允许 ${\theta }^2$，必须另证它保持所选解集合，并承认轨道划分已经改变。群、作用集合及保持的范数三者都应写清。