ACM-ICPC数学 数论 Pell 方程详解
ACM-ICPC数学 数论 Pell 方程详解
Pell方程是一类重要的二次不定方程，在数论中有着广泛的应用，特别是在研究二次整环和单位数时。本文将详细介绍Pell方程的基本概念、性质以及求解方法，并讨论其在ACM-ICPC竞赛中的应用。
Pell方程的基本概念
定义
Pell方程是形如 $x^2 - Dy^2 = 1$ 或 $x^2 - Dy^2 = -1$ 的方程，其中 $D$ 是一个不含平方因子的正整数。
二次整数
对于二次有理数 $a + b\sqrt{D}$，如果 $a$ 和 $b$ 满足以下条件之一：
- $a$ 与 $b$ 是整数，且 $D \equiv 2 \pmod{4}$ 或 $D \equiv 3 \pmod{4}$。
- $a$ 与 $b$ 同时是半整数，且 $D \equiv 1 \pmod{4}$。
那么 $a + b\sqrt{D}$ 就是二次整数。二次整数与首一整系数二次方程的解构成对应关系。
单位数与基本单位数
单位数
如果二次整数 $a + b\sqrt{D}$ 的范数 $a^2 - Db^2$ 为 1 或 -1，则它的倒数也是二次整数，恰好是它的共轭或者共轭的相反数。此时称它为整环 $\mathbb{Z}[\sqrt{D}]$ 的单位数，简称单位数。
基本单位数
可以证明，存在基本单位数，使得全体单位数都可以表示成为基本单位数的幂（或幂的相反数）。它也就是对应 Pell 方程的基本解，通解可以表示为基本解的幂（或幂的相反数）。
求解 Pell 方程
Dirichlet 逼近定理
利用 Dirichlet 逼近定理，可以逼近二次根式 $\sqrt{D}$，即有无穷个有理数（显然为正有理数）满足：
$$
\left|\frac{x}{y} - \sqrt{D}\right| \leq \frac{1}{y^2}
$$
范数估值
根据上面的逼近关系，可以对范数进行估值：
$$
|N(x + y\sqrt{D})| = |x - y\sqrt{D}||x + y\sqrt{D}| \leq \frac{1}{y}\left(\frac{1}{y} + 2y\sqrt{D}\right) \leq 2\sqrt{D} + 1
$$
这说明只要有理数与 $\sqrt{D}$ 越接近，范数就越小。
基本解的存在
根据上述估值，可以证明范数为 $\pm1$ 的单位数存在，并且存在无限个。
利用渐进分数求解
对于所有 $D$ 的渐进分数，配上系数之后得到的二次整数的范数都落在非常小的区间。通过计算每个循环节处前一个渐进分数，可以找到使得范数为 $\pm1$ 的二次整数。
Pell 方程的求解方法
定理：范数为 $|s| < D$ 的渐进分数
若 $x^2 - Dy^2 = s$ 且 $|s| < D$，则 $\frac{x}{y}$ 一定是 $\sqrt{D}$ 的渐进分数。
定理：渐进分数与 $Q_k$ 的关系
$p_k^2 - Dq_k^2 = (-1)^{k+1}Q_{k+1}$
定理：$Q_k$ 的周期性
当且仅当 $k = nL$（其中 $n$ 是正整数，$L$ 是最短循环周期）时，有 $Q_k = 1$。
定理：解的组合
若 $(x_1, y_1)$ 和 $(x_2, y_2)$ 都是 $x^2 - Dy^2 = 1$ 的整数解，则：
$$
X = x_1x_2 + y_1y_2D
$$
$$
Y = x_1y_2 + x_2y_1
$$
也是方程的整数解。
具体例子与应用
例1：求解 Pell 方程 $x^2 - 2y^2 = 1$
表示 $\sqrt{2}$ 的循环连分数为 $[1;\overline{2}]$。通过分析其循环部分，可以找到 Pell 方程的基本解 $x = 3$，$y = 2$，通解为 $(3 + 2\sqrt{2})^n$ 的形式。
例2：求解 Pell 方程 $x^2 - 2y^2 = -1$
当 $D$ 的循环节长度为奇数时，方程 $x^2 - Dy^2 = -1$ 有解。
结论
Pell 方程在数论中具有重要地位，其解法涉及连分数、渐进分数和单位数等概念。通过理解这些基本原理和定理，可以高效地求解 Pell 方程，并在 ACM-ICPC 竞赛中解决相关问题。