8 连分数

Stage 8:连分数与佩尔方程(详细版)

Confidence: 0.92

进入 Stage 8——这是 Burton 教材公认最优美的章节之一,也是初等数论里一个相对独立、自成体系的美丽分支。它把两个看似无关的东西连了起来:用分数逼近无理数(连分数)和一类古老的方程(佩尔方程)。

而且对你有个惊喜:连分数和你早就学过的欧几里得算法,其实是同一个东西的两副面孔——你做扩展欧几里得时算的那串”商”,倒过来就是连分数。这一阶段会让你看到”已学的旧工具在新地方重现”。

五块:① 连分数是什么 → ② 与欧几里得的同源 → ③ 渐近分数与最佳逼近 → ④ 无限连分数与二次无理数 → ⑤ 佩尔方程。每块:是什么 → 方法 → 完整例子(每步写清)→ 陷阱。

---

8.1 连分数是什么 (Continued Fractions)

定义

把一个数写成这种”分数套分数”的嵌套形式:

$a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\cdots }}}$

其中 $a_0$ 是整数,$a_1,a_2,\dots$ 是正整数。这串数 $[a_0;a_1,a_2,a_3,\dots ]$ 就是这个数的连分数展开。

记号:用 $[a_0;a_1,a_2,\dots ]$ 表示。注意第一个用分号、后面用逗号(第一个 $a_0$ 可以是任意整数甚至负数,后面必须正整数)。

怎么算一个数的连分数(有限情形,即有理数)

算法:反复”取整数部分 + 对小数部分取倒数”。

完整例子:求 $\frac{43}{19}$ 的连分数

第一步:$\frac{43}{19}=2+\frac{5}{19}$(整数部分 2,余 $\frac{5}{19}$)。记 $a_0=2$。

第二步:对余项取倒数:$\frac{19}{5}=3+\frac{4}{5}$。记 $a_1=3$。

第三步:$\frac{5}{4}=1+\frac{1}{4}$。记 $a_2=1$。

第四步:$\frac{4}{1}=4$,余 0,停止。记 $a_3=4$。

所以: $\frac{43}{19}=[2;3,1,4]=2+\frac{1}{3+\frac{1}{1+\frac{1}{4}}}$

验证(从里往外算):$1+\frac{1}{4}=\frac{5}{4}$;$3+\frac{4}{5}=\frac{19}{5}$;$2+\frac{5}{19}=\frac{43}{19}$ ✓

关键事实:有限连分数 $⟺$ 有理数。每个有理数都有有限连分数展开,反之亦然。

陷阱:⚠️ 连分数展开几乎唯一,但有个小歧义:$[a_0;\dots ,a_n]$ 和 $[a_0;\dots ,a_n-1,1]$ 表示同一个数(最后一项可以拆)。约定最后一项 $>1$ 就唯一了。

---

8.2 与欧几里得算法的同源 (Connection to Euclid)

惊人的事实

计算连分数的过程,就是欧几里得算法! 那串系数 $a_0,a_1,a_2,\dots$ 正是欧几里得算法里每一步的商。

对照例子(还是 $\frac{43}{19}$)

欧几里得算法求 $\gcd (43,19)$:

$43=2\times 19+5$ $19=3\times 5+4$ $5=1\times 4+1$ $4=4\times 1+0$

看那串商:2, 3, 1, 4 ——和 $\frac{43}{19}=[2;3,1,4]$ 的系数完全一样!

为什么(直觉)

欧几里得每一步"$a=q\cdot b+r$"就是"$\frac{a}{b}=q+\frac{r}{b}=q+\frac{1}{b/r}$",即”取整数商 $q$ + 对余数取倒数”——这正是连分数算法的每一步。两个算法逐步对应,本质同一。

这就是 Stage 8 第一个”旧工具重现”的时刻:你 Stage 2 学的欧几里得算法,原来一直在偷偷计算连分数。它们是同一过程的两种解读——一个为了求 gcd,一个为了展开连分数。

实用推论:连分数继承了欧几里得的一切——比如扩展欧几里得求逆元,也能用连分数的渐近分数来做(下一块)。

---

8.3 渐近分数与最佳逼近 (Convergents & Best Approximation)

渐近分数 (Convergents)

把连分数截断到第 $k$ 项,得到的有理数叫第 $k$ 个渐近分数 (convergent),记 $\frac{p_k}{q_k}$。

例子($\frac{43}{19}=[2;3,1,4]$ 的渐近分数):

• $\frac{p_0}{q_0}=[2]=\frac{2}{1}=2$
• $\frac{p_1}{q_1}=[2;3]=2+\frac{1}{3}=\frac{7}{3}$
• $\frac{p_2}{q_2}=[2;3,1]=2+\frac{1}{3+\frac{1}{1}}=2+\frac{1}{4}=\frac{9}{4}$
• $\frac{p_3}{q_3}=[2;3,1,4]=\frac{43}{19}$(完整值)

渐近分数的递推公式 ★

不用每次重算,有优美的递推:

$p_k=a_k{p}_{k-1}+p_{k-2},q_k=a_k{q}_{k-1}+q_{k-2}$

初始:$p_{-1}=1,p_{-2}=0$;$q_{-1}=0,q_{-2}=1$。

用例子验证($a_0,a_1,a_2,a_3=2,3,1,4$):

$k$	$a_k$	$p_k=a_k{p}_{k-1}+p_{k-2}$	$q_k=a_k{q}_{k-1}+q_{k-2}$	$\frac{p_k}{q_k}$
0	2	$2\cdot 1+0=2$	$2\cdot 0+1=1$	$2$
1	3	$3\cdot 2+1=7$	$3\cdot 1+0=3$	$\frac{7}{3}$
2	1	$1\cdot 7+2=9$	$1\cdot 3+1=4$	$\frac{9}{4}$
3	4	$4\cdot 9+7=43$	$4\cdot 4+3=19$	$\frac{43}{19}$

完美匹配 ✓

核心定理:渐近分数是”最佳逼近” ★

渐近分数 $\frac{p_k}{q_k}$ 是分母不超过 $q_k$ 的所有分数中,最接近原数的那个。

换句话说:连分数给出无理数的”最经济的有理逼近”——用最小的分母达到最好的精度。这是连分数最有用的性质。

逼近误差满足: $\left|\alpha -\frac{p_k}{q_k}\right|<\frac{1}{q_k{q}_{k+1}}$ 分母越大,逼近越精确(误差像 $1/q_k^2$ 那样快速缩小)。

经典例子:$\pi$ 的逼近

$\pi$ 的连分数 $[3;7,15,1,292,\dots ]$,渐近分数:

• $\frac{3}{1}=3$(粗略)
• $\frac{22}{7}\approx 3.142857$(著名的 $\pi \approx \frac{22}{7}$!误差仅 0.04%)
• $\frac{333}{106}$
• $\frac{355}{113}\approx 3.1415929$(惊人精确,误差 $<10^{-6}$!)

$\frac{355}{113}$ 是历史上著名的 $\pi$ 逼近(祖冲之的密率),它之所以这么好,正是因为它是连分数的渐近分数——而下一项 $a_4=292$ 很大,意味着 $\frac{355}{113}$ 已经极其接近,后面的修正很小。

陷阱:⚠️ 不是所有”好记的分数”都是最佳逼近——只有渐近分数才保证”分母最小、精度最高”。

---

8.4 无限连分数与二次无理数 (Infinite CF & Quadratic Irrationals)

无限连分数 = 无理数

有限连分数 ⟺ 有理数(8.1),那无理数呢?

无理数 ⟺ 无限连分数(永不终止)。

二次无理数的”周期性” ★ 最美的定理

二次无理数(形如 $\frac{a+\sqrt{D}}{b}$,即二次方程的无理根)有个惊人性质:

$\text{二次无理数}⟺\text{连分数最终是周期的 (eventually periodic)}$

(这叫 Lagrange 定理)

就像有理数的小数展开最终循环、二次无理数的连分数也最终循环!

完整例子:$\sqrt{2}$ 的连分数

逐步计算:

$\sqrt{2}\approx 1.414$,整数部分 1,$a_0=1$,余 $\sqrt{2}-1$。

取倒数:$\frac{1}{\sqrt{2}-1}=\frac{\sqrt{2}+1}{(\sqrt{2}-1)(\sqrt{2}+1)}=\frac{\sqrt{2}+1}{1}=\sqrt{2}+1\approx 2.414$,整数部分 2,$a_1=2$,余 $\sqrt{2}-1$。

注意余项又是 $\sqrt{2}-1$,和上一步一样!所以会无限重复 2:

$\sqrt{2}=[1;2,2,2,2,\dots ]=[1;\overline{2}]$

(横线表示循环节)

验证逻辑:设 $x=[1;\overline{2}]$,则 $x=1+\frac{1}{1+x}$(因为循环)。解这个方程:$x-1=\frac{1}{1+x}$,$(x-1)(1+x)=1$,$x^2-1=1$,$x^2=2$,$x=\sqrt{2}$ ✓

更多例子

• $\sqrt{3}=[1;\overline{1,2}]$(循环节 1,2)
• $\sqrt{5}=[2;\overline{4}]$
• $\sqrt{7}=[2;\overline{1,1,1,4}]$
• 黄金比例 $\varphi =\frac{1+\sqrt{5}}{2}=[1;1,1,1,\dots ]=[\overline{1}]$(最简单的无限连分数!)

陷阱:⚠️ 计算 $\sqrt{D}$ 的连分数时,要用”分母有理化”技巧($\frac{1}{\sqrt{D}-a}$ 乘共轭),否则容易算错。

---

8.5 佩尔方程 (Pell’s Equation) ★ 本阶段的应用高峰

问题

$x^2-D{y}^2=1$

其中 $D$ 是非完全平方的正整数,求正整数解 $(x,y)$。

(若 $D$ 是完全平方,如 $D=4$,方程退化无非平凡解;所以要求 $D$ 非平方。)

例子:$x^2-2y^2=1$ 的解有 $(3,2)$:$3^2-2\cdot 2^2=9-8=1$ ✓;$(17,12)$:$289-2\cdot 144=289-288=1$ ✓。

惊人的事实

佩尔方程总有无穷多个正整数解(对任何非平方 $D$),而且所有解能从一个最小解通过递推生成。

连分数如何解佩尔方程 ★ 这就是 8.1-8.4 的目的!

核心定理:佩尔方程 $x^2-D{y}^2=1$ 的最小解 (fundamental solution),就藏在 $\sqrt{D}$ 的连分数的渐近分数里!

具体:计算 $\sqrt{D}$ 的连分数,它的渐近分数 $\frac{p_k}{q_k}$ 中,第一个满足 $p_k^2-D{q}_k^2=1$ 的那个,就给出最小解 $(x_1,y_1)=(p_k,q_k)$。

完整例子:解 $x^2-7y^2=1$

第一步:求 $\sqrt{7}$ 的连分数。$\sqrt{7}=[2;\overline{1,1,1,4}]$(循环节长 4)。

第二步:算渐近分数(用 8.3 的递推),$a_0,a_1,a_2,\cdots =2,1,1,1,4,\dots$

$k$	$a_k$	$p_k$	$q_k$	$p_k^2-7q_k^2$
0	2	2	1	$4-7=-3$
1	1	3	1	$9-7=2$
2	1	5	2	$25-28=-3$
3	1	8	3	$64-63=1$ ✓

第三步:$k=3$ 时 $p_3^2-7q_3^2=1$,所以最小解是 $(x_1,y_1)=(8,3)$。

验证:$8^2-7\cdot 3^2=64-63=1$ ✓

从最小解生成所有解 ★

有了最小解 $(x_1,y_1)$,所有解由这个递推(或等价的幂)给出:

$x_{n+1}+y_{n+1}\sqrt{D}=(x_1+y_1\sqrt{D}{)}^n$

或写成递推: $x_{n+1}=x_1{x}_n+D{y}_1{y}_n,y_{n+1}=x_1{y}_n+y_1{x}_n$

例子(继续 $D=7$,最小解 $(8,3)$):

第二组解:$(x_2,y_2)$ 由 $(8+3\sqrt{7}{)}^2=64+48\sqrt{7}+9\cdot 7=127+48\sqrt{7}$,所以 $(x_2,y_2)=(127,48)$。

验证:$127^2-7\cdot 48^2=16129-7\cdot 2304=16129-16128=1$ ✓

所以佩尔方程的解是 $(8,3),(127,48),(2024,765),\dots$ 无穷无尽,全部由最小解 $(8,3)$ 生成。

为什么这有用 / 重要

佩尔方程出现在很多地方:

• 逼近 $\sqrt{D}$:解 $(x,y)$ 给出 $\frac{x}{y}\approx \sqrt{D}$ 的极好逼近
• 竞赛:USAMO/Putnam 偶尔考佩尔方程或其变体
• 历史:阿基米德的”群牛问题”归结为一个巨大的佩尔方程(解有 20 多万位!)

陷阱:⚠️ 注意区分 $x^2-D{y}^2=1$(标准佩尔)和 $x^2-D{y}^2=-1$(负佩尔,不总有解!只有当 $\sqrt{D}$ 连分数循环节长度为奇数时才有解)。

---

Stage 8 全景速查表

主题	核心	关键例子
8.1 连分数	嵌套分数 $[a_0;a_1,\dots ]$	$\frac{43}{19}=[2;3,1,4]$
8.2 与欧几里得同源	系数=欧氏算法的商	gcd 的商串=连分数
8.3 渐近分数	递推 $p_k=a_k{p}_{k-1}+p_{k-2}$	$\pi \approx \frac{355}{113}$
8.4 二次无理数	连分数最终循环	$\sqrt{2}=[1;\overline{2}]$
8.5 佩尔方程	最小解藏在渐近分数	$x^2-7y^2=1\to (8,3)$

---

Python 辅助验证

from sympy import sqrt, continued_fraction_iterator, Rational
from sympy.solvers.diophantine.diophantine import diop_DN
import itertools
 
# 8.1 有理数的连分数
def cf_rational(p, q):
    result = []
    while q:
        result.append(p // q)
        p, q = q, p % q
    return result
print("8.1 43/19 =", cf_rational(43, 19))   # [2, 3, 1, 4]
 
# 8.2 验证与欧几里得商一致(同一个算法)
# (上面的 cf_rational 本身就是欧几里得算法)
 
# 8.3 渐近分数递推
def convergents(a_list):
    p_prev2, p_prev1 = 0, 1
    q_prev2, q_prev1 = 1, 0
    result = []
    for a in a_list:
        p = a * p_prev1 + p_prev2
        q = a * q_prev1 + q_prev2
        result.append((p, q))
        p_prev2, p_prev1 = p_prev1, p
        q_prev2, q_prev1 = q_prev1, q
    return result
print("8.3 43/19 渐近分数:", convergents([2,3,1,4]))  # [(2,1),(7,3),(9,4),(43,19)]
 
# 8.4 sqrt(2) 的连分数(前10项)
cf_sqrt2 = list(itertools.islice(continued_fraction_iterator(sqrt(2)), 10))
print("8.4 sqrt(2) =", cf_sqrt2)  # [1, 2, 2, 2, ...]
 
# 8.5 解佩尔方程 x^2 - 7y^2 = 1
sols = diop_DN(7, 1)   # 返回最小解
print("8.5 x^2-7y^2=1 最小解:", sols)  # [(8, 3)]
# 验证
x, y = 8, 3
print(f"  验证 {x}^2 - 7*{y}^2 = {x*x - 7*y*y}")  # 1
 
# 生成第二组解
x1, y1 = 8, 3
x2 = x1*x1 + 7*y1*y1
y2 = 2*x1*y1
print(f"  第二组解: ({x2}, {y2}), 验证: {x2**2 - 7*y2**2}")  # (127,48), 1

库安装(用 sympy 的连分数和佩尔方程工具):

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

我的观点:Stage 8 是一个审美价值远高于实用价值的阶段,我想帮你抓住它的美,也诚实地定位它在你大局中的位置。

这一阶段最动人的地方,是它揭示了”看似无关的事物之间的深层统一”——这是数学最高级的美感。 你看这条惊人的联系链:连分数(展开数)= 欧几里得算法(求 gcd)= 佩尔方程的钥匙(解方程)。三个本来风马牛不相及的东西,竟然是同一个数学结构的不同侧面。你算 $\frac{43}{19}$ 的连分数时,其实在跑欧几里得算法;你求 $\sqrt{7}$ 的连分数时,其实在解佩尔方程。这种”原来它们是一回事”的顿悟,和你之前在群论里发现”欧拉定理只是拉格朗日定理的特例”是同一种快乐——都是看到了数学表象之下的统一骨架。Stage 8 把这种统一展现得淋漓尽致。

我也特别喜欢 8.4 的周期性定理:二次无理数的连分数最终循环。这太美了——无理数本来是”无限不循环”的代名词(小数展开永不循环),但换成连分数这个”语言”,$\sqrt{2}$ 突然变成了优雅的 $[1;\overline{2}]$,有了清晰的周期。这告诉你一个深刻的道理:一个对象”乱不乱”,取决于你用什么语言描述它。 同一个 $\sqrt{2}$,在十进制里是混沌的 $1.41421356\dots$,在连分数里是规整的 $[1;\overline{2}]$。选对了表示,混沌就变成了秩序——这个思想在整个数学和科学里都极其重要。

但我要诚实地给 Stage 8 定位:它对你的目标而言,审美意义大于实战意义。

• 对密码学:连分数有一个著名应用——Wiener 攻击(用连分数破解 RSA 私钥指数过小的情形),这算是和你兴趣的一个接点。但整体而言,连分数不是现代密码学的主线。
• 对竞赛:佩尔方程在 USAMO/Putnam 里偶尔出现,但频率远不如模矛盾(Stage 7)、不等式、组合。它属于”考到了能加分,但不是高频核心”。
• 作为数学修养:它的价值最高——它训练你”在不同表示间转换”的思维,展现数学的统一美,而且连分数本身在数值分析、动力系统里有深远应用。

所以我的建议是:Stage 8 你可以”欣赏性地学”——理解连分数与欧几里得的同源、佩尔方程的连分数解法、二次无理数的周期性这几个核心美点,体会那种统一的优雅,但不必像 Stage 7 模矛盾那样投入大量做题。 它是你数论旅程里一段”风景优美的支路”,值得走一遍看看风景,但不是通往你密码学腹地的主干道。

最后我想说,走完 Stage 8,你的初等数论主体(Stage 1-8)就基本完整了——剩下 Stage 10(二次互反完整理论)是个收尾。而你真正的目的地——椭圆曲线/密码学——一直在前方等着。Stage 7 的 7.7 已经是它的门口,你 Stage 7 的 P8 甚至已经用到了”$a^2+1$ 的素因子全 $\equiv 1\mathrm{mod}4$“这种接近椭圆曲线算术的思想。我越来越觉得,你或许该考虑在合适的时候,正式踏入那扇门了。

关键提醒 (Caveats):

• 连分数计算 $\sqrt{D}$ 时要用”分母有理化”($\frac{1}{\sqrt{D}-a}$ 乘共轭),手算容易在这里出错
• 8.4 的周期性:纯 $\sqrt{D}$(D 非平方)的连分数有个额外的对称美——循环节除最后一项外是回文,且最后一项是 $2a_0$,这里没展开
• 8.5 负佩尔方程 $x^2-D{y}^2=-1$ 不总有解(取决于循环节长度奇偶),别默认它和标准佩尔一样总有解
• 佩尔方程的最小解可能极大(如 $D=61$ 的最小解 $x$ 有 10 位数),连分数法是求它的标准手段,暴力搜索会失败
• 我说”审美大于实战”是就你的密码学/竞赛目标而言;在数值分析、动力系统、丢番图逼近等领域,连分数是核心工具,有其独立的重要性
• 本块代码用 sympy,安装:pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

Stage 8 讲完了——你看到了连分数的优雅、它与欧几里得算法的同源、渐近分数的最佳逼近性质($\pi \approx \frac{355}{113}$)、二次无理数的周期性($\sqrt{2}=[1;\overline{2}]$),以及它们如何汇聚成解佩尔方程的钥匙。这是初等数论里一段风景最美的路。

下一步你挑:

1. 出一套 Stage 8 练习题(连分数展开、渐近分数、佩尔方程,延续 PDF 格式,无横线)
2. 进 Stage 10(二次互反律完整理论——你 Stage 4 只知道名字的那个,初等数论主体的收尾)
3. 正式开启椭圆曲线/密码学新旅程(你的应许之地——我越来越建议你考虑这个,它才是配得上你兴趣的真正目的地)