连分数

连分数把数逐层写成整数部分加倒数： $[a_{0}; a_{1}, a_{2}, \dots] = a_{0} + 1 / (a_{1} + 1 / (a_{2} + \dots))$ 。本文讨论简单连分数，其中 $a_{0}$ 为整数， $a_{k}$ 在 $k \geq 1$ 时为正整数。对正有理数，欧几里得算法会在有限步内结束，得到有限连分数；截断到不同层得到一串渐近分数，可用于寻找分母较小的近似值。

从欧几里得除法写出四层

对 $415 / 93$ ，依次除法为 $415 = 4 \cdot 93 + 43$ 、 $93 = 2 \cdot 43 + 7$ 、 $43 = 6 \cdot 7 + 1$ 、 $7 = 7 \cdot 1$ 。把每一步余数比倒过来代回，得到 $\frac{415}{93} = [4; 2, 6, 7] = 4 + \frac{1}{2 + \frac{1}{6 + \frac{1}{7}}} .$ 逐层截断为 $4, 9 / 2, 58 / 13, 415 / 93$ 。第三个近似 $58 / 13$ 与原数相差 $| 415 / 93 - 58 / 13 | = 1 / 1209 \approx 0.000827$ ，却只用分母 13。这里的近似误差可直接交叉相乘验算，不必只看小数显示。

分子分母的递推与相邻关系

设第 $k$ 个渐近分数为 $p_{k} / q_{k}$ ，取 $p_{- 2} = 0, p_{- 1} = 1, q_{- 2} = 1, q_{- 1} = 0$ ，递推 $\begin{matrix} p_{k} & = a_{k} p_{k - 1} + p_{k - 2}, \\ q_{k} & = a_{k} q_{k - 1} + q_{k - 2} . \end{matrix}$ 由初值可归纳证明 $p_{k} q_{k - 1} - p_{k - 1} q_{k} = (- 1)^{k - 1}$ ：把两项递推代入，含 $a_{k}$ 的部分互相消去，余下恰是前一层行列式的相反数。因此相邻渐近分数的差的绝对值是 $1 / (q_{k} q_{k - 1})$ 。分母增长时，相邻近似靠近；这个等式也说明相邻分数已约成最简分数。

无理数的连分数不会结束。 $\sqrt{2} = [1; 2, 2, 2, \dots]$ ：若尾部 $z = [2; 2, 2, \dots]$ ，则 $z = 2 + 1 / z$ ，正根为 $1 + \sqrt{2}$ ，故整个式子 $1 + 1 / z = \sqrt{2}$ 。无限展开的等号还需渐近分数收敛来支撑；后续正整数项使分母最终严格递增，相邻差趋零并交替夹住极限。对于有理数，末项若大于 1，还可把末项 $a$ 写成 $a - 1, 1$ ，因此最后一层表示并不唯一，通常约定末项大于 1。

参考资料与相关词条

MIT 18.781：连分数课程讲义。
相关：欧几里得算法、有理数的稠密性、同余。