Appearance
连分数与丢番图逼近（Continued Fractions & Diophantine Approximation）
核心定位
连分数是无理数最"自然"的展开方式，相较于十进制小数，它更能反映数的算术本质。每个实数有唯一的简单连分数表示，无理数的连分数无限延展，二次无理数（如 $\sqrt{2}$、$\sqrt{3}$）的连分数呈现周期性。连分数是丢番图逼近的核心工具：其渐近分数给出最佳有理逼近。本笔记系统介绍连分数理论及其在佩尔方程、Thue 定理与超越数论中的应用，与 不定方程与丢番图方程、二次剩余与阶 形成完整的知识网络。
一、连分数的定义
1.1 简单连分数
简单连分数（Simple Continued Fraction）
每个实数 $\alpha$ 可唯一表示为： $$\alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}} = [a_0; a_1, a_2, a_3, \dots]$$ 其中 $a_0 \in \mathbb{Z}$，$a_i \in \mathbb{Z}_{>0}$（$i \ge 1$）。
构造算法：取 $a_0 = \lfloor \alpha \rfloor$，令 $\alpha_1 = 1/(\alpha - a_0)$，再取 $a_1 = \lfloor \alpha_1 \rfloor$，递归得 $a_n$。$\alpha$为有理数当且仅当连分数有限（在某$a_n$ 处终止）；$\alpha$ 为无理数当且仅当连分数无限。
例：$\sqrt{2}$ 的连分数
$\sqrt{2} = 1.4142\dots$
- $a_0 = 1$，$\alpha_1 = 1/(\sqrt{2} - 1) = \sqrt{2} + 1 \approx 2.4142$
- $a_1 = 2$，$\alpha_2 = 1/(\sqrt{2} + 1 - 2) = 1/(\sqrt{2} - 1) = \sqrt{2} + 1$
- 故 $a_n = 2$对所有$n \ge 1$，$\sqrt{2} = [1; \overline{2}]$（周期 $1$）
1.2 渐近分数
第 $n$ 个渐近分数
截断连分数到第 $n$项得到的有理数$p_n/q_n = [a_0; a_1, \dots, a_n]$称为第$n$ 个渐近分数。
递推公式： $$\begin{cases} p_{-1} = 1, & p_0 = a_0, & p_n = a_n p_{n-1} + p_{n-2} \newline q_{-1} = 0, & q_0 = 1, & q_n = a_n q_{n-1} + q_{n-2} \end{cases}$$
关键恒等式： $$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}$$
由此 $p_n$与$q_n$互素，渐近分数$p_n/q_n$ 是既约分数。
$\sqrt{2}$ 的前几个渐近分数
$\sqrt{2} = [1; 2, 2, 2, \dots]$。 | $n$|$a_n$|$p_n$|$q_n$|$p_n/q_n$| 误差$|p_n/q_n - \sqrt{2}|$ | |---|---|---|---|---|---| | $0$|$1$|$1$|$1$|$1$|$0.414$ | | $1$|$2$|$3$|$2$|$1.5$|$0.086$ | | $2$|$2$|$7$|$5$|$1.4$|$0.014$ | | $3$|$2$|$17$|$12$|$1.4167$|$0.0025$ | | $4$|$2$|$41$|$29$|$1.4138$|$0.00042$ | 注意 $(3, 2), (17, 12), (99, 70)$正是$x^2 - 2y^2 = \pm 1$ 的解。
二、连分数的基本性质
性质一：交错逼近
渐近分数交替地小于和大于 $\alpha$： $$\frac{p_0}{q_0} < \frac{p_2}{q_2} < \frac{p_4}{q_4} < \cdots < \alpha < \cdots < \frac{p_5}{q_5} < \frac{p_3}{q_3} < \frac{p_1}{q_1}$$
性质二：误差估计
$$\frac{1}{q_n(q_n + q_{n+1})} < \left|\alpha - \frac{p_n}{q_n}\right| < \frac{1}{q_n q_{n+1}}$$ 特别地，$\left|\alpha - p_n/q_n\right| < 1/q_n^2$。
性质三：单调递增的分母
$q_n$ 严格递增（$n \ge 1$），增长速度至少为 Fibonacci 数列：$q_n \ge F_n$，其中 $F_0 = 0, F_1 = 1, F_{n+1} = F_n + F_{n-1}$。
性质四：最佳逼近
若 $|\alpha - p/q| < |\alpha - p_n/q_n|$且$q \le q_n$，则 $p/q = p_n/q_n$。即渐近分数是最佳有理逼近：分母不超过 $q_n$的有理数中，渐近分数$p_n/q_n$最接近$\alpha$。
Hurwitz 定理：对任意无理数 $\alpha$，存在无穷多对 $(p, q)$ 使： $$\left|\alpha - \frac{p}{q}\right| < \frac{1}{\sqrt{5} q^2}$$ 常数 $\sqrt{5}$是最佳的（黄金比例$\varphi = (1+\sqrt{5})/2$ 时取等）。
三、二次无理数的连分数
Lagrange 定理
$\alpha$的连分数为周期的$\iff$ $\alpha$是二次无理数（即满足整系数二次方程$a\alpha^2 + b\alpha + c = 0$，$\Delta = b^2 - 4ac$ 非完全平方）。
纯周期连分数：$\alpha = [\overline{a_0; a_1, \dots, a_n}]$当且仅当$\alpha$是既约二次无理数，即$\alpha > 1$且其共轭$\alpha' \in (-1, 0)$。
Galois 定理
$\alpha = [\overline{a_0; a_1, \dots, a_{n-1}}]$为纯周期$\iff$ $\alpha$的共轭$\bar{\alpha} = -1/[\overline{a_{n-1}; a_{n-2}, \dots, a_0}]$。
3.1 $\sqrt{D}$ 的连分数
形式定理
对任意非完全平方的正整数 $D$，$\sqrt{D}$ 的连分数形如： $$\sqrt{D} = [a_0; \overline{a_1, a_2, \dots, a_{n-1}, 2a_0}]$$ 即周期以 $2a_0$结束（其中$a_0 = \lfloor \sqrt{D} \rfloor$）。
$\sqrt{D}$ 的连分数示例
- $\sqrt{2} = [1; \overline{2}]$，周期 $1$
- $\sqrt{3} = [1; \overline{1, 2}]$，周期 $2$
- $\sqrt{5} = [2; \overline{4}]$，周期 $1$
- $\sqrt{7} = [2; \overline{1, 1, 1, 4}]$，周期 $4$
- $\sqrt{13} = [3; \overline{1, 1, 1, 1, 6}]$，周期 $5$
- $\sqrt{19} = [4; \overline{2, 1, 3, 1, 2, 8}]$，周期 $6$
3.2 周期与佩尔方程
周期长度与 $x^2 - Dy^2 = -1$ 的可解性
设 $\sqrt{D}$的连分数周期为$r$，则：
- $r$ 为偶数时，$x^2 - Dy^2 = -1$ 无整数解
- $r$ 为奇数时，$x^2 - Dy^2 = -1$有整数解，最小正解为$p_{r-1}, q_{r-1}$
无论 $r$ 奇偶，$x^2 - Dy^2 = 1$的最小正解为$(p_{r-1}, q_{r-1})$（若 $r$偶）或$(p_{2r-1}, q_{2r-1})$（若 $r$ 奇）。
$\sqrt{13}$ 与佩尔方程
$\sqrt{13} = [3; \overline{1, 1, 1, 1, 6}]$，周期 $r = 5$（奇）。故 $x^2 - 13y^2 = -1$有解，最小解为第$r - 1 = 4$ 个渐近分数：$[3; 1, 1, 1, 1] = 18/5$。验证：$18^2 - 13 \cdot 5^2 = 324 - 325 = -1$ ✓。$x^2 - 13y^2 = 1$的最小解为第$2r - 1 = 9$个渐近分数，可算出$(649, 180)$，验证 $649^2 - 13 \cdot 180^2 = 421201 - 421200 = 1$ ✓。
四、连分数算法与有理逼近
4.1 最优逼近定理
第一类最佳逼近
渐近分数 $p_n/q_n$是分母$\le q_n$的有理数中最接近$\alpha$ 的。
第二类最佳逼近
若 $q < q_{n+1}$且$p/q \ne p_n/q_n$，则 $|q\alpha - p| > |q_n \alpha - p_n|$。
中间渐近分数（半渐近分数）
介于 $p_{n-1}/q_{n-1}$与$p_n/q_n$之间的"中间分数"$\frac{p_{n-2} + k p_{n-1}}{q_{n-2} + k q_{n-1}}$（$1 \le k < a_n$）也是较好的逼近，但不如 $p_n/q_n$ 最佳。
4.2 Legendre 定理
Legendre 定理
若 $|\alpha - p/q| < \dfrac{1}{2q^2}$，则 $p/q$必是$\alpha$ 的某个渐近分数。
逆否：非渐近分数的有理逼近 $p/q$满足$|\alpha - p/q| \ge 1/(2q^2)$。
用途
Legendre 定理给出了判断一个有理数是否为渐近分数的充分条件。在丢番图逼近的许多问题中（如 Thue 定理的证明），这是把"有理逼近"转化为"渐近分数"的关键步骤。
五、丢番图逼近的核心定理
5.1 Dirichlet 逼近定理
Dirichlet 逼近定理
对任意无理数 $\alpha$与正整数$N$，存在整数 $p, q$（$1 \le q \le N$）使： $$\left|\alpha - \frac{p}{q}\right| < \frac{1}{qN} \le \frac{1}{q^2}$$
证明（鸽巢原理）：考虑 $N + 1$个数$\lbrace 0\alpha\rbrace , \lbrace 1\alpha\rbrace , \dots, \lbrace N\alpha\rbrace $（其中 $\lbrace x\rbrace = x - \lfloor x \rfloor$为小数部分）放入$[0, 1)$的$N$个区间$[0, 1/N), [1/N, 2/N), \dots, [(N-1)/N, 1)$。由鸽巢原理，必有两个 $\lbrace i\alpha\rbrace , \lbrace j\alpha\rbrace $落入同一区间，差$< 1/N$。设 $|i - j| = q \le N$，$p = \lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor$，则 $|q\alpha - p| < 1/N$，即 $|\alpha - p/q| < 1/(qN)$。
推论：无穷逼近
对任意无理数 $\alpha$，存在无穷多对整数 $(p, q)$使$|\alpha - p/q| < 1/q^2$。
5.2 Liouville 定理与超越数
Liouville 定理
设 $\alpha$为$n$ 次代数数（$n \ge 2$）。则存在常数 $C(\alpha) > 0$使对任意有理数$p/q$： $$\left|\alpha - \frac{p}{q}\right| > \frac{C(\alpha)}{q^n}$$
证明思路：设 $\alpha$是$f(x) = a_n x^n + \cdots + a_0$ 的根，$f$ 不可约。$f(p/q) \ne 0$（否则 $f$ 有有理根，与不可约矛盾），$q^n f(p/q)$为非零整数，故$|q^n f(p/q)| \ge 1$。由中值定理 $|f(p/q)| = |f(p/q) - f(\alpha)| = |f'(\xi)| \cdot |p/q - \alpha|$，其中 $\xi$介于$p/q$与$\alpha$之间。取$C = 1/\max |f'|$在$[\alpha - 1, \alpha + 1]$ 上即得。
Liouville 数
若 $\alpha$满足：对任意$n$，存在无穷多 $p/q$使$|\alpha - p/q| < 1/q^n$，则 $\alpha$ 是超越数。
Liouville 数示例：$\sum_{k=1}^{\infty} 10^{-k!} = 0.110001000\dots$（在小数点后第 $k!$位取$1$）是 Liouville 数，于 1844 年成为第一个被证明的超越数。
5.3 Roth 定理（Fields 奖工作）
Roth 定理（1955）
设 $\alpha$为代数无理数。则对任意$\epsilon > 0$，存在 $C(\alpha, \epsilon) > 0$ 使： $$\left|\alpha - \frac{p}{q}\right| > \frac{C(\alpha, \epsilon)}{q^{2 + \epsilon}}$$ 对所有有理数 $p/q$ 成立。
意义：Roth 定理将 Liouville 的 $q^{-n}$改进为$q^{-2-\epsilon}$，是最优的（与 Dirichlet 的 $q^{-2}$仅差$\epsilon$）。Roth 因此获 1958 年 Fields 奖。
进一步发展
- Thue-Siegel-Roth 定理是丢番图逼近的巅峰结果
- Schmidt 子空间定理（1970）将 Roth 推广到多变量
- 这些定理的几何化是算术几何的核心内容
5.4 Thue 定理的证明思路
Thue 定理（再次陈述）
设 $F(x, y)$ 为齐次不可约整系数多项式，$\deg F \ge 3$。则对任意 $m \ne 0$，方程 $F(x, y) = m$ 仅有有限组整数解。
证明梗概：
- 设 $F(x, y) = a_0 x^n + a_1 x^{n-1} y + \cdots + a_n y^n$，记 $\alpha = x/y$的逼近误差为$|x/y - \alpha|$。
- 由 $F(x, y) = y^n F(x/y, 1) = m$得$|F(x/y, 1)| = |m|/|y|^n$。
- 由 $\alpha$是$F(\cdot, 1)$ 的根：$|F(x/y, 1)| \ge C |x/y - \alpha|$，故 $|x/y - \alpha| \le C'/|y|^n$。
- 由 Thue 的逼近结果（改进 Liouville）：$|x/y - \alpha| > C''/|y|^{n/2 + 1 + \epsilon}$。
- 结合两式：$|y|^{n - n/2 - 1 - \epsilon} < C$，即 $|y|^{n/2 - 1 - \epsilon}$有界，从而$|y|$ 有界，整数解有限。
六、等分布理论与 Weyl 判别
Weyl 等分布定理
序列 $\lbrace n\alpha\rbrace $（$n = 1, 2, \dots$，$\lbrace x\rbrace $为小数部分）在$[0, 1)$上等分布$\iff$ $\alpha$ 为无理数。
等分布：对任意 $[a, b) \subseteq [0, 1)$，$\lim_{N \to \infty} \frac{1}{N} \#\lbrace 1 \le n \le N : \lbrace n\alpha\rbrace \in [a, b)\rbrace = b - a$。
Weyl 判别：$\lbrace x_n\rbrace $等分布$\iff$对任意非零整数$h$，$\lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^{N} e^{2\pi i h x_n} = 0$。
应用
等分布定理说明无理数的"旋转"是均匀的。例如 $\lbrace n\sqrt{2}\rbrace $在$[0,1)$中等分布，这可以用来证明许多关于整数部分$[n\sqrt{2}]$ 的渐近公式。
七、典型例题
例 1：求连分数
求 $\dfrac{1071}{462}$ 的连分数展开。
解：辗转相除： $$1071 = 2 \cdot 462 + 147, \quad 462 = 3 \cdot 147 + 21, \quad 147 = 7 \cdot 21 + 0$$ 故 $1071/462 = [2; 3, 7] = 2 + \cfrac{1}{3 + \cfrac{1}{7}} = 2 + \cfrac{7}{22} = \dfrac{51}{22}$... 等等验算：$2 + 1/(3 + 1/7) = 2 + 7/22 = 51/22$，但 $51/22 \ne 1071/462 = 51/22$？$1071/462 = 51/22$，验 $51 \cdot 462 = 23562$，$22 \cdot 1071 = 23562$✓。故连分数$[2; 3, 7]$。
例 2：用渐近分数逼近 $\pi$
求 $\pi = 3.1415926535\dots$ 的前 4 个渐近分数。
解：
- $a_0 = 3$，$\alpha_1 = 1/0.14159\dots \approx 7.0625$，$a_1 = 7$
- $p_0/q_0 = 3/1$
- $p_1/q_1 = (7 \cdot 3 + 1)/(7 \cdot 1 + 0) = 22/7 \approx 3.142857$（经典逼近，误差约 $1.3 \times 10^{-3}$）
- $\alpha_2 = 1/0.0625 \approx 15.9966$，$a_2 = 15$，$p_2/q_2 = (15 \cdot 22 + 3)/(15 \cdot 7 + 1) = 333/106 \approx 3.1415094$（误差 $8.3 \times 10^{-5}$）
- $a_3 = 1$，$p_3/q_3 = (1 \cdot 333 + 22)/(1 \cdot 106 + 7) = 355/113 \approx 3.14159292$（误差 $2.7 \times 10^{-7}$，祖冲之的"密率"！）
例 3：求佩尔方程最小解
用连分数求 $x^2 - 19y^2 = 1$ 的最小正解。
解：$\sqrt{19} = [4; \overline{2, 1, 3, 1, 2, 8}]$，周期 $r = 6$（偶数）。最小解为第 $r - 1 = 5$ 个渐近分数：
- $p_0/q_0 = 4/1$
- $p_1/q_1 = 9/2$
- $p_2/q_2 = (1 \cdot 9 + 4)/(1 \cdot 2 + 1) = 13/3$
- $p_3/q_3 = (3 \cdot 13 + 9)/(3 \cdot 3 + 2) = 48/11$
- $p_4/q_4 = (1 \cdot 48 + 13)/(1 \cdot 11 + 3) = 61/14$
- $p_5/q_5 = (2 \cdot 61 + 48)/(2 \cdot 14 + 11) = 170/39$
验证：$170^2 - 19 \cdot 39^2 = 28900 - 28899 = 1$ ✓
例 4：逼近误差的精确估计
证明 $\left|\sqrt{2} - \dfrac{p}{q}\right| > \dfrac{1}{4q^2}$对所有有理数$p/q$ 成立。
证：由 $p^2 - 2q^2$ 为非零整数（$\sqrt{2}$无理），故$|p^2 - 2q^2| \ge 1$。而 $|p^2 - 2q^2| = |p - q\sqrt{2}| \cdot |p + q\sqrt{2}|$。若 $|p/q - \sqrt{2}| < 1/q$（即 $p/q$接近$\sqrt{2}$，否则显然成立），则 $|p + q\sqrt{2}| < 2q\sqrt{2} + 1 < 4q$（$q \ge 1$）。故 $|p/q - \sqrt{2}| = |p^2 - 2q^2| / (q |p + q\sqrt{2}|) \ge 1/(q \cdot 4q) = 1/(4q^2)$。
例 5：Markov 常数
求无理数 $\alpha$的 Markov 常数$M(\alpha) = \liminf_{q \to \infty} q \Vert{}q\alpha\Vert$（其中 $\Vert{}x\Vert$为到最近整数的距离），对$\alpha = \sqrt{2}$。
解：$\sqrt{2}$的渐近分数$p_n/q_n$满足$|q_n \sqrt{2} - p_n| = 1/(q_n \sqrt{2} + p_n) \to 1/(2\sqrt{2})$。由最佳逼近性，$M(\sqrt{2}) = 1/(2\sqrt{2}) = \sqrt{2}/4 \approx 0.3536$。 Hurwitz 给出 $M(\alpha) \le 1/\sqrt{5} \approx 0.4472$（黄金比例取等），$\sqrt{2}$ 是接近最优的"次坏"逼近。
例 6：Thue 定理应用
证明 $x^3 - 2y^3 = 1$ 仅有有限组整数解。
解：由 Thue 定理，$F(x, y) = x^3 - 2y^3$是$\deg F = 3$ 的不可约齐次多项式（$x^3 - 2$在$\mathbb{Q}$ 上不可约）。$m = 1 \ne 0$，故方程的整数解有限。具体解：$(x, y) = (1, 0), (-1, -1)$（验证 $(-1)^3 - 2(-1)^3 = -1 + 2 = 1$ ✓）以及有限几个其他解。
八、补充：超越数与代数数
代数数与超越数
- 代数数：满足整系数多项式方程的复数。所有有理数、$\sqrt{2}, i, \sqrt[3]{5}$ 等都是代数数。
- 超越数：非代数数的复数。典型例子：$e, \pi, \log 2, 2^{\sqrt{2}}$。
重要定理：
- Hermite-Lindemann（1882）：$e$与$\pi$都是超越数。Lindemann 证明$\pi$超越是基于$e^{i\pi} = -1$与"若$\alpha$非零代数数，则$e^\alpha$ 超越"。
- Gelfond-Schneider（1934）：若 $\alpha, \beta$ 为代数数，$\alpha \ne 0, 1$，$\beta$无理，则$\alpha^\beta$超越。如$2^{\sqrt{2}}$ 超越。
- Baker 定理（1966，Fields 奖）：代数数的对数的线性组合要么为零要么为超越数。这是 $p$-adic 分析与丢番图方程的核心工具。
用 Gelfond-Schneider 证明 $2^{\sqrt{2}}$ 超越
设 $\alpha = 2$（代数），$\beta = \sqrt{2}$（无理代数），由 Gelfond-Schneider 定理，$\alpha^\beta = 2^{\sqrt{2}}$ 超越。这是 Hilbert 第七问题的解答。
九、知识链接
- 不定方程与丢番图方程 — Thue 定理与 Mordell 方程的有限性证明依赖丢番图逼近
- 二次剩余与阶 — 二次无理数的连分数与二次剩余理论紧密相关
- 数论函数与欧拉定理 — 佩尔方程解的递推与欧拉函数有关
- 整除与同余基础 — 裴蜀定理与连分数算法（辗转相除法）同源
- 数论不等式与估计 — Markov 常数与 Hurwitz 定理属于数论估计的范畴
- 迭代与函数方程 — 连分数渐近分数的递推 $p_n=a_n p_{n-1}+p_{n-2}$ 是分式线性迭代
- 数列与递推方法 — 渐近分数列 $\lbrace p_n/q_n\rbrace $ 的二阶线性递推与特征根分析
- 矩阵与线性代数初步 — 渐近分数的矩阵表示 $\begin{pmatrix}p_n\newlineq_n\end{pmatrix}=\prod\begin{pmatrix}a_k&1\newline1&0\end{pmatrix}\begin{pmatrix}p_0\newlineq_0\end{pmatrix}$