Pell 方程

内容基本来源于 OI-wiki

定义与结构

（广义）Pell 方程指关于 的不定方程

当 或为完全平方数时是平凡的，我们不予考虑，同时，解 也是平凡的，接下来的讨论中忽略该解。而狭义的 Pell 方程专指 或 的特殊情况。

对于一个二次整数 （它是一个二次方程的根），定义其范数为它与它的共轭的积，记为

所以，广义 Pell 方程大致相当于在求解范数为 的二次整数，但并不等价，因为二次整数形如 ，当 时， 可以同时为半整数。

范数具有一些性质，这对 Pell 方程的求解至关重要。

Brahmagupta 恒等式

证明显然。这说明了什么？这说明二次整数的范数保持乘法，也即

利用这个性质，假如我们知道了 的一组解和 的一组解，我们就能立刻写出 的一组解。正因 Pell 方程的解和二次整数的紧密联系，我们将解 直接写成 的形式。

同时，由于 Pell 方程表示的是一个双曲线的方程，所以我们只需要找到第一象限的所有解即可。

在下文中，我们只探讨狭义 Pell 方程的求解，文章开头的链接中给出了广义 Pell 方程的求解方式，但这里暂时不作延申。

狭义 Pell 方程的求解

由上文可知，如果存在一个解 ，那么所有 都将是 Pell 方程的解（范数的积性），我们先声称存在一个基本解（使 最小的 ），下面证明它的 次幂 可以得到所有解。

不妨设第一象限中存在一个另外的解 ，两侧同时乘 得到

这与 最小矛盾！

下面，我们给出 Pell 方程基本解的构造性证明。

PQa 算法

PQa 算法可以得出特定的二次无理数的连分数展开。设整数 满足 ， 且不是完全平方数，且 ，那么二次无理数

的连分数展开 可以由如下递推求得：

进而， 的第 个渐进分数的分子和分母 和 由如下递推给出：

其中 ，，，

证明可以参见 OI-wiki，也可以看 ProjectEuler板刷记录 中的Problem 64。

记 ，下面我们利用 PQa 算法解决 Pell 方程。

定理. 设 ，则整数对 满足

且它们的最大公因数 整除