⚡ 佩尔负型方程
探索形如 x²-dy²=-1 的二次不定方程，揭示其与连分数、代数数论的深刻联系。本页提供从基础定义到高级应用的全面指南，帮助读者掌握求解技巧并理解其在现代密码学中的潜在价值。
佩尔方程（Pell's Equation）通常指形如 x²-dy²=1 的方程，其中 d 是一个非平方正整数。然而，数学界同样高度重视其“负型”变体：
佩尔负型方程是指形如：
x² - d y² = -1
其中 x 和 y 是未知整数，d 是一个给定的非平方正整数（d > 0 且 d 不是完全平方数）。
与正型方程不同，负型方程并非对所有非平方 d 都有解。这种“存在性”的不确定性使得它成为数论中一个迷人且富有挑战性的研究对象。
判断佩尔负型方程是否有整数解，是解决该类问题的第一步。这一判定直接依赖于 √d 的连分数展开性质。
设 √d 的简单连分数展开为：
[a₀; a₁, a₂, ..., aₗ]
其中 l 是周期长度。则：
例1：d=2
√2 = [1; 2, 2, 2, ...] = [1; ̅2]
周期 l=1（奇数），故 x²-2y²=-1 有解。
最小解为 (1, 1)，因为 1² - 2(1)² = -1。
例2：d=3
√3 = [1; 1, 2, 1, 2, ...] = [1; ̅1, 2]
周期 l=2（偶数），故 x²-3y²=-1 无解。
当判定方程有解后，如何找到其最小正整数解？最经典且有效的方法是连分数法。
首先，将 √d 展开为无限循环连分数。这可以通过以下算法完成：
此过程产生的序列 a₀, a₁, a₂, ... 即为连分数的部分商。
设周期长度为 l（已知为奇数）。我们需要计算第 l-1 个渐近分数 p/q。
渐近分数 pₖ/qₖ 可通过以下递推公式计算：
pₖ = aₖpₖ₋₁ + pₖ₋₂
qₖ = aₖqₖ₋₁ + qₖ₋₂
初始条件：
计算到 k = l-1 时，得到的 p 和 q 即为方程的最小正整数解。
验证： 将求得的 (p, q) 代入 x²-dy²=-1，确认等式成立。
通解公式： 若 (x₁, y₁) 是负型方程的最小正整数解，则所有正整数解可由正型方程 X²-dY²=1 的基本解 (u, v) 生成：
xₙ + yₙ√d = (x₁ + y₁√d)(u + v√d)ⁿ
其中 n = 0, 1, 2, ...。注意，负型方程的解集是正型方程解集的一个子集，且两者通过代数结构紧密相连。
虽然未明确提出“佩尔方程”概念，但其著作《算术》中研究了形如 x²-y²=z 的方程，为后世奠定了丢番图分析的基础。
尽管历史归属存在争议，但欧拉将该类方程命名为“佩尔方程”。佩尔与费马之间的通信涉及了此类方程的求解问题。
欧拉系统性地研究了 x²-dy²=±1 的解，并建立了其与连分数的联系。他证明了若正型方程有解，则负型方程可能有解，并给出了判定条件。
随着库默尔、戴德金等人发展代数数论，佩尔方程被置于理想类群和-unit 群的框架下重新审视，揭示了其更深层的代数结构。
佩尔负型方程不仅是纯数学的玩具，其在现代科技中也有意想不到的应用。以下是网友们常关心的周边知识：
虽然 RSA 基于大数分解，但基于二次域的理想类群问题的密码方案与佩尔方程的求解难度有关。某些后量子密码协议利用二次曲线的算术性质，其中佩尔方程的解是构造密钥的基础。
佩尔方程的解提供了 √d 的最佳有理逼近。这在计算机图形学中用于生成近似直线或圆弧的像素点，以及在信号处理中设计滤波器时减少舍入误差。
在程序生成地形或随机数生成器中，佩尔方程可用于生成具有特定统计特性的序列。例如，某些复古游戏中的碰撞检测算法利用了二次不定方程的性质。
| 特性 | 佩尔正型方程 (x²-dy²=1) | 佩尔负型方程 (x²-dy²=-1) |
|---|---|---|
| 解的存在性 | 对所有非平方 d 恒有解 | 仅当 √d 周期为奇数时有解 |
| 最小解来源 | 第 l 个渐近分数 (l为周期) | 第 l-1 个渐近分数 |
| 解集结构 | 由基本解生成所有正解 | 由最小解与正型基本解组合生成 |
| 代数意义 | 对应范数为 1 的 unit | 对应范数为 -1 的 unit |
佩尔负型方程 x²-dy²=-1 有整数解的充要条件是：连分数展开式 √d 的周期长度 l 为奇数。如果周期长度 l 为偶数，则该方程无整数解。
主要方法是使用连分数法。首先计算 √d 的连分数展开，直到找到周期。如果周期长度为奇数，取第 l-1 个渐近分数 p/q，则 (p, q) 即为方程的最小正整数解。
若佩尔负型方程 x²-dy²=-1 有解，则其所有解均可由正型方程 x²-dy²=1 的基本解通过代数运算导出。具体地，若 (x₁, y₁) 是负型方程的最小解，则正型方程的基本解为 (x₁²+dy₁², 2x₁y₁)。
因为 √3 的连分数展开为 [1; ̅1, 2]，周期长度 l=2 为偶数。根据判定定理，当周期为偶数时，佩尔负型方程无整数解。
除了密码学，佩尔方程在代数数论中用于计算类数和单位群，在几何学中用于研究双曲平面的等距变换，以及在计算机科学中用于伪随机数生成和图形算法。