连分数

连分数

连分数是一种记号。例如，长为 4 的连分数：

[a_0,a_1,a_2,a_3]=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3}}}

只是为了形式上简洁，才记成等号左边的样子。这里的四个变元可以任意取值。

连分数各变元的下标从 0 开始。

渐进分数

连分数中，从前面一直到第 k 个变元构成的连分数，是它的 第 k 渐进分数，记作 \frac{p_k}{q_k} 。

渐进分数分子和分母具有完全相同的递推关系：

p_k=a_kp_{k-1}+p_{k-2}
q_k=a_kq_{k-1}+q_{k-2}

这里和 Farey 数列的递推关系很像。

形式上记初项：

p_{-1}=1 \quad p_0=a_0
q_{-1}=0 \quad q_0=1

只是形式上成立。第 -1 项渐进分数是 1/0，没有实际意义。

证明

可以注意到， p_k 与 q_k 对于 a_k 和 b_k 都是线性函数。这是因为， a_k 和 b_k 都只出现了一次，无论如何通分也不会有另一个 a_k 或 b_k 乘上去。于是通过待定系数，即可解得这个递推关系。

反序定理

\frac{q_k}{q_{k-1}}=[a_k,a_{k-1},\ldots,a_1]

如果 a_0\neq 0 ：

\frac{p_k}{p_{k-1}}=[a_k,a_{k-1},\ldots,a_0]

如果 a_0=0 ：

\frac{p_k}{p_{k-1}}=[a_k,a_{k-1},\ldots,a_2]
证明

对递推关系稍加改造，有：

\frac{p_k}{p_{k-1}}=a_k+\frac{1}{\frac{p_{k-1}}{p_{k-2}}}
\frac{q_k}{q_{k-1}}=a_k+\frac{1}{\frac{q_{k-1}}{q_{k-2}}}

又利用初值，即可证明反序定理。

渐进分数的差分

计算相邻两项渐进分数的差，需要通分。通分后的分子代入递推关系：

p_{k+1}q_k-q_{k+1}p_k=\left(a_{k+1}p_k+p_{k-1}\right)q_k-\left(a_{k+1}q_k+q_{k-1}\right)p_k=-\left(p_kq_{k-1}-q_kp_{k-1}\right)

代入初值就有渐进分数的差分：

p_{k+1}q_k-q_{k+1}p_k=(-1)^k
\frac{p_{k+1}}{q_{k+1}}-\frac{p_k}{q_k}=\frac{(-1)^k}{q_{k+1}q_k}
注

可以观察到，式 p_{k+1}q_k-q_{k+1}p_k 特别像一个行列式，完全可以按“行列式”理解。

渐进分数的递推关系很像行列式的列变换。行列式一列加到另一列上不改变它的值，两列交换则反号。

根据递推式，如果连分数各项均为整数，则渐进分数分子分母总是互素。

对于有理数的简单连分数展开，常用渐进分数差分的等式，求解一次线性不定方程（参见 扩展欧几里得算法）：

p_{k+1}q_k-q_{k+1}p_k=(-1)^k
ax-by=1

因为 a 与 b 互素， \frac{a}{b} 就是最简的有理数，也就是它本身的最后一个渐进分数。那么，它的前一个渐进分数就是所求的解。

无限连分数

如果分式无限地写下去，有无限个变元，就得到无限连分数。无限连分数收敛等价于渐进分数收敛。

有定理：

无限连分数，如果各变元均大于等于 1 ，那么一定收敛。

因为只要各变元为正，无限连分数的偶渐进分数单调递增（都比它小），奇渐进分数单调递减（都比它大）。而在均大于等于 1 时，相邻（奇偶间）两个渐进分数之间距离可以给出估计式，趋于 0 ，因此收敛。

显然可以看到，连分数关于下标为偶数的变元单调递增，关于下标为奇数的变元单调递减。这无论它有限或无限都成立。

简单连分数

对于有限连分数，全体结尾为 1 的有限连分数和全体结尾不为 1 的有限连分数一一对应，即同一个连分数有两种表示：

[a_0,a_1,a_2,a_3]=[a_0,a_1,a_2,a_3-1,1]

简单连分数：连分数从第 1 项开始全都是正整数。如果有限，要求最后一项不为 1 。（第 0 项可以任意）

简单连分数的值，一定大于偶数的渐进分数，一定小于奇数的渐进分数。无限简单连分数一定收敛。

仿照一般分数的概念，第 0 项是 0 的连分数称为“真分数”。显然如果这之后的所有变元都大于等于 1 ，那么得到的真分数一定落在 0 到 1 之间。

连分数算法

如果要求 (0,1) 区间内某个数的简单连分数表示（第 0 项为 0 ），只需：

  • 取倒数，得到的数大于 1 。
  • 取整，得到的小数部分在 0 到 1 之间。
  • 对余数 r_k 重复上述操作。

这样就得到了相应的表示。

如果规定第 0 项是该数的取整，那么全体实数都有“唯一的简单连分数表示”。其中：

如果两个无限简单连分数的值相等，必然逐项相等。

如果两个有限简单连分数的值相等，不仅要逐项相等，而且必然项数也相同。

无限简单连分数不能与有限简单连分数值相等。有理数与有限简单连分数具有一一对应关系，因此无限简单连分数全都是无理数。

余项（余数）和部分商

从第 k 个变元开始，一直到最后一个变元构成的连分数，记作 r_k ，称为 第 k 余项（余数）。相应地，取整得到的 a_k 称为部分商。

r_k=[a_k,a_{k+1},a_{k+2},\ldots]

余项 r_k 就是上述连分数算法中第 k 步取倒数之后得到的数。

对于各项均为正数的连分数，所有的余项也都是正数。

误差估计

实数 x 也可以写成：

x=[a_0,a_1,\ldots,a_k,r_{k+1}]

最后一项渐近分数就是 x 本身。于是根据渐进分数的递推式，就有：

x=\frac{r_{k+1}p_k+p_{k-1}}{r_{k+1}q_k+q_{k-1}}

于是可以估计渐进分数的误差：

x-\frac{p_k}{q_k}=\frac{(-1)^k}{q_k\left(r_{k+1}q_k+q_{k-1}\right)}

分别对 k 取奇数偶数就得到，x 总小于其奇数阶渐近分数，大于其偶数阶渐近分数。

倒数定理

由于实数与简单连分数一一对应，我们称实数的简单连分数的渐进分数，就是实数的渐进分数。于是就有倒数定理：

对于大于 1 的实数 x，x 的渐进分数的倒数恰好是 $\frac{1}{x} 的渐进分数。显然，该定理也应该对于 0 到 1 之间的实数 x 成立。

证明
x=[a_0,a_1,a_2,\ldots]
\frac{1}{x}=\frac{1}{[a_0,a_1,a_2,\ldots]}=[0,a_0,a_1,a_2,\ldots]

于是根据新的初值与递推就能发现倒数关系成立。

二次有理数

二次有理数：整系数一元二次方程的解。

用词说明

在初等数论书上，“二次有理数”写为“二次无理数”。这是因为，二次有理数不是有理数，而是无理数。在近世代数书上，写为“二次有理数”或者“二次代数数”，表明它与有理数拥有相似的性质。

同样地，还有“二次整数”。二次整数不是整数，在 Pell 方程 会提到。“二次有理数”一词与“二次整数”相对应，与有理数和整数的关系完全一致，有理数是整数的比值。

二次有理数有以下的表示法，一定可以写成：

a+b\sqrt{d}

其中， a 与 b 为有理数， d 为整数。任意这种形式的数都是二次有理数，两者为一一对应。

称 a-b\sqrt{d} 为它的共轭。

称范数为二次有理数与它的共轭的乘积，即：

N(a+b\sqrt{d})=a^2-db^2

于是，除以一个二次有理数，等于除以它的范数，再乘上它的共轭。

二次域

具有同样 \sqrt{d} 的二次有理数的全体，构成一个集合，记作 Q(\sqrt{d}) 。

容易证明，集合 Q(\sqrt{d}) 对于加、减、乘、除封闭，即任意取出两个元素，都可以进行四种运算（保证除数非 0），并且结果也在集合中。因此，它是一个域，称为 \sqrt{d} 的二次域。

1 和 \sqrt{d} 在有理数域上线性无关，所以在同一个二次域中，二次有理数的表示法具有唯一性。如果有：

a+b\sqrt{d}=e+f\sqrt{d}

那么有：

a=e \quad b=f

共轭定理：在同一个二次域中，如果一个等式仅经过有限次合法四则运算构成，那么对等式两边所有数同时取共轭，等式仍然成立。

证明：取共轭后的新的等式左右两边，结果一定仍然在该二次域中。只需证明它们对应的有理系数和无理系数相等。

无论如何，系数都与根号 d 的整体无关，取共轭只是将根号 d 换成了负根号 d，从头到尾只用到“平方等于 d”一个性质，因此，对应系数相等。

拓展

二次域 Q(\sqrt{d}) 中的四则运算与一类特殊形式的二阶方阵同构：

\begin{pmatrix} a & b\\ db & a \end{pmatrix}

比如，乘法的行为模式完全一致：

\begin{pmatrix} a_1 & b_1 \\ db_1 & a_1 \end{pmatrix} \begin{pmatrix} a_2 & b_2 \\ db_2 & a_2 \end{pmatrix} = \begin{pmatrix} a_1a_2 + db_1b_2 & a_1b_2 + b_1a_2 \\ d(a_1b_2 + b_1a_2) & a_1a_2 + db_1b_2 \end{pmatrix}

因此二次有理数的一些性质可以由二阶方阵来解释。比如，范数恰好就是它的行列式：

N(a+b\sqrt{d})= \begin{vmatrix} a & b \\ db & a \end{vmatrix}

求倒数也就与伴随方阵求逆法一致。伴随方阵恰好就是它的共轭：

\begin{pmatrix} a & b\\ db & a \end{pmatrix}^\ast = \begin{pmatrix} a & -b\\ -db & a \end{pmatrix}

这种二阶方阵的记法参考了二维坐标系的旋转矩阵：

\begin{pmatrix} \cos\theta &\sin\theta\\ -\sin\theta&\cos\theta\\ \end{pmatrix}

二维坐标系的旋转矩阵的行为模式就像 d 为 -1 的特殊数域一样。

在下文中，主要研究实二次域。以下的二次有理数，特指实二次有理数，即 d 应当为正。

循环连分数

仿照循环小数的概念，如果在连分数后面形成了循环，则形成 循环连分数。

循环连分数的最小正周期一般用字母 l 来表示，循环的部分称为循环节。容易发现，进入循环的充要条件是余项 r_k 的重复出现。

拉格朗日连分数定理

关于循环连分数有一个特别重要的基础定理：

拉格朗日连分数定理：实二次有理数与循环连分数一一对应。

该定理最早由拉格朗日（Lagrange）于 1769 年证明。

根据余项的重复出现，证明循环连分数一定是二次有理数非常容易。重点在于证明二次有理数一定是循环连分数。

证明

对二次有理数执行“无限简单连分数”计算，即取倒数、取整交替，得到的余数还是二次有理数。

接下来要强行刻画余项，将余项束缚在有限的范围，有限范围里的无限余项必然会发生重复。

设 \xi 是如下形式的二次有理数：

\frac{1}{q}\left(c+\sqrt{d}\right)\quad q|N(c-\sqrt{d})

如果分母不整除分子的范数，那么分子分母同时乘以分母的绝对值，并强行压入根号，在新二次有理数中，分母整除新的分子的范数。因此，任何二次有理数都能写成这形式。

根据上文的简单连分数算法：对余数取整可以得到 a ，进而得到新的 c 。

a_k=\frac{c_{k+1}+c_k}{q_k}

取整后得到的新的 c 为负数，且绝对值一定比 \sqrt{d} 小，因此范数为负。取倒数，得到新的分母 q ， q 总是正的。

q_k q_{k+1}=-N(c_{k+1}-\sqrt{d})

由于范数为负，取倒数之后 \sqrt{d} 前面的符号不变，而 c 的符号由负变正（负数前面加负号变为正数）。

余数 r 里面，每个 c 都为负数，且绝对值一定比 \sqrt{d} 小，因此分子 c 的个数有限。

每个 q 都整除对应 c 构成二次整数的范数，因此分母 q 的个数有限。余数有限必重复，至此证完。

纯循环连分数

如果循环节从第 0 项开始，称为 纯循环连分数，否则称为 混循环连分数。例如纯循环连分数：

[a_0,a_1,a_2,a_3,a_0,a_1,a_2,a_3,…]=[\overline{a_0,a_1,a_2,a_3}]

混循环连分数：

[a_0,a_1,a_2,a_3,a_1,a_2,a_3,…]=[a_0,\overline{a_1,a_2,a_3}]

混循环连分数后面循环的部分，一般要找最早循环的部分，称为它的“纯循环部分”。

纯循环连分数的整数部分 a_0 直接进入到了循环里面，因此要求 a_0 必须至少是 1。因此，纯循环连分数大于 1。

伽罗瓦连分数定理

纯循环连分数有类似于反序定理的定理。记：

x=\left[\overline{a_0,a_1,\ldots,a_{l-1}}\right]
x'=\left[\overline{a_{l-1},a_{l-2},\ldots,a_0}\right]

则两个 x 互为“倒数负共轭”。即，若记：

y=-\frac{1}{x'}

则 x 与 y 共轭。

该定理最早由伽罗瓦（Galois）在他 17 岁那年（1828 年）发现并证明。

证明

不妨改取比较长（例如至少有 5 项）的循环节。将循环节部分反序，根据反序定理，渐进分数有：

\frac{p_{l-1}}{p_{l-2}}=[a_{l-1},a_{l-2},\ldots,a_0]=\frac{{p'}_{l-1}}{{q'}_{l-1}}
\frac{q_{l-1}}{q_{l-2}}=[a_{l-1},a_{l-2},\ldots,a_1]=\frac{{p'}_{l-2}}{{q'}_{l-2}}

由于渐进分数的分子分母总是互素，只能分子分母对应相等。

根据纯循环，循环节的余项与它本身相等，有：

x=\frac{xp_{l-1}+p_{l-2}}{xq_{l-1}+q_{l-2}}
q_{l-1}x^2+(q_{l-2}-p_{l-1})x-p_{l-2}=0

之后只需将上述反序定理代入验证即证完。

根据伽罗瓦连分数定理，纯循环连分数的共轭一定落在 -1 到 0 之间。考虑它的逆问题，就有下面的定理：

如果二次有理数 x 大于 1 ，它的共轭落在 -1 到 0 之间，则它是纯循环连分数。

证明

对二次无理数进行连分数算法，它的余项 r_{k+1} 容易得到。

根据共轭落在 -1 和 0 之间，利用归纳法可以知道，余项的共轭总是落在 -1 到 0 之间，因此部分商 a_k 是 r_{k+1} 的“倒数负共轭”的取整。这给了一种“倒推”的关系。

由拉格朗日连分数定理，x 一定是循环连分数，存在余项 r 相同，于是它们的前一个部分商 a 相同，前一个余项是小数部分的倒数，也相同。最后推得第 0 项在循环节中，该二次有理数纯循环。

根号 d 的连分数

对于非平方整数 d，有：

\sqrt{d}=[\lfloor\sqrt{d}\rfloor,\overline{a_1,a_2,\ldots,a_{l-1},2\lfloor\sqrt{d}\rfloor}]
a_k=a_{l-k}

这是根号 d 的连分数形式。不仅最后一位是整数部分的两倍，而且中间部分还是对称的。

证明

对于非平方整数 d，二次有理数

\lfloor\sqrt{d}\rfloor+\sqrt{d}

是纯循环连分数。于是就有：

\sqrt{d}=[\lfloor\sqrt{d}\rfloor,\overline{a_1,a_2,\ldots,a_{l-1},2\lfloor\sqrt{d}\rfloor}]

而上述纯循环连分数的倒数负共轭既可以用伽罗瓦连分数定理表达，也可以由它本身直接表达：

\frac{1}{-\lfloor\sqrt{d}\rfloor+\sqrt{d}}=[\overline{a_{l-1},a_{l-2},\ldots,a_1,2\lfloor\sqrt{d}\rfloor}]=[\overline{a_1,a_2,\ldots,a_{l-1},2\lfloor\sqrt{d}\rfloor}]

根据简单连分数展开的唯一性就证明了该结论。

同样也可以证明，整数部分为半整数的相同结构：

\frac{\sqrt{d}}{2}=[\lfloor\frac{\sqrt{d}-1}{2}\rfloor+\frac{1}{2},\overline{a_1,a_2,\ldots,a_{l-1},2\lfloor\frac{\sqrt{d}-1}{2}\rfloor+1}]
a_k=a_{l-k}

如果循环节 l 是奇数，则对称部分最中间一个数连续出现两次，对应的两个余项互为共轭。但如果循环节 l 是偶数，就不会出现这种现象。

在后面的 Pell 方程一节中将指出，在根号 d 的连分数中，循环节 l 的奇偶性，将直接决定 Pell 方程中的 -1 形式是否有解。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论