密码学数学基础 - 连分数进阶 | Alice and Bobの神秘小屋

在前面的章节中，我们已经介绍了连分数的基本概念和一些重要的性质。现在，我们将进一步深入探讨连分数的一些进阶内容，而且我们会在渐进分数的基础上，介绍一些更高级的定理和应用。😎

话不多说了，可能有些难，但是直接进入正题！🤗

渐进分数 🤩

渐进分数是指连分数的前 $n$ 项所对应的有理数，例如 $[a_0]$, $[a_0, a_1]$, $[a_0, a_1, a_2]$ 等等。

我们记 $[a_0, a_1, \ldots, a_n] = \frac{p_n}{q_n}$，其中 $p_n$ 和 $q_n$ 分别是分子和分母，那么我们可以得到以下递推关系①：

$\begin{align*} p_n &= a_n p_{n-1} + p_{n-2} \\ q_n &= a_n q_{n-1} + q_{n-2} \end{align*}$

还有一个有趣的定理②：对于任意的 $n \geq 1$，都有

$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}$

而且这种渐进分数有一种特殊单调性③（很重要，快看！😡）：
对于有限连分数 $[a_0, a_1, \ldots, a_n] = \frac{p_n}{q_n}$，第 $t$ 个渐进分数 $x_t = \frac{p_t}{q_t}$，有

$\frac{p_0}{q_0} < \frac{p_2}{q_2} < \cdots < \frac{p_n}{q_n} < \cdots < \frac{p_3}{q_3} < \frac{p_1}{q_1}$

最佳近似值 😦

在数轴上，如果与其他有理数相比，$\frac{p}{q}$ （$p$ 和 $q$ 互质）到实数 $x$ 的距离最近，那么我们称 $\frac{p}{q}$ 是 $x$ 的一个最佳近似值（只考虑分母大小不超过 $q$ 的有理数）。

而这里和我们前面联系有一个极其重要的定理④：设 $x = [a_0, a_1, \ldots]$ 在分母不超过 $q_t$ 的有理数中，第 $t$ 个渐进分数 $\frac{p_t}{q_t}$ 是 $x$ 的最佳近似值。
注意，实数的最佳近似值不知有它的渐进分数。

结论①②③④证明 😭

结论①证明 😱

我们可以使用数学归纳法来证明结论①。

$\begin{align*} p_0 = a_0, q_0 = 1 \\ p_1 = a_0a_1 + 1, q_1 = a_1 \end{align*}$

假设 $p_t$ 和 $q_t$ 的等式成立：

$[a_0, \ldots, a_t] = \frac{p_t}{q_t} = \frac{a_t p_{t-1} + p_{t-2}}{a_t q_{t-1} + q_{t-2}}$

将后面两项合并一下，也就是

$\begin{align*} \frac{p_{t+1}}{q_{t+1}} &= [a_0, \dots, a_t, a_{t+1}] \\ &= \left[a_0, \dots, a_{t-1}, a_t + \frac{1}{a_{t+1}}\right] \\ &= \frac{\left(a_t + \frac{1}{a_{t+1}}\right)p_{t-1} + p_{t-2}}{\left(a_t + \frac{1}{a_{t+1}}\right)q_{t-1} + q_{t-2}} \\ &= \frac{a_{t+1}(a_t p_{t-1} + p_{t-2}) + p_{t-1}}{a_{t+1}(a_t q_{t-1} + q_{t-2}) + q_{t-1}} \\ &= \frac{a_{t+1} p_t + p_{t-1}}{a_{t+1} q_t + q_{t-1}} \\ \end{align*}$

这恰好就是结论①的形式，所以结论①成立。

结论②证明 😵

就是根据结论①的递推关系不断带入，最终得到结论②的形式。

$\begin{align*} p_n q_{n-1} - p_{n-1} q_n &= (a_n p_{n-1} + p_{n-2}) q_{n-1} - p_{n-1} (a_n q_{n-1} + q_{n-2}) \\ &= -(p_{n-2} q_{n-1} - p_{n-1} q_{n-2}) \\ &= \ldots = (-1)^{n-1} (p_0 q_{-1} - p_{-1} q_0) \\ &= (-1)^{n-1}(a_0 a_1 + 1 - a_0 a_1) \\ &= (-1)^{n-1} \end{align*}$

结论③证明 😵‍💫

这个证明是前面结论的综合应用，要配合这前面看。虽然比较复杂，但是慢慢来也可以证明清楚。🤑

对于奇偶数单调性证明

也就是我们要先证明

$\begin{align*} \frac{p_0}{q_0} < \frac{p_2}{q_2} < \cdots < \frac{p_{2k}}{q_{2k}} \\ \frac{p_{2k+1}}{q_{2k+1}} < \cdots < \frac{p_3}{q_3} < \frac{p_1}{q_1} \end{align*}$

当 $t$ 是偶数时，$xt > x{t-2}$。
当 $t$ 是奇数时，$xt < x{t-2}$。

$\begin{align*} x_t - x_{t-2} &= \frac{p_t}{q_t} - \frac{p_{t-2}}{q_{t-2}} \\ &= (\frac{p_t}{q_t} - \frac{p_{t-1}}{q_{t-1}}) + (\frac{p_{t-1}}{q_{t-1}} - \frac{p_{t-2}}{q_{t-2}}) \\ &= \frac{p_t q_{t-1} - p_{t-1} q_t}{q_t q_{t-1}} + \frac{p_{t-1} q_{t-2} - p_{t-2} q_{t-1}}{q_{t-1} q_{t-2}} \\ &= \frac{(-1)^{t-1}}{q_t q_{t-1}} + \frac{(-1)^{t-2}}{q_{t-1} q_{t-2}} = \frac{(-1)^t (q_t - q_{t-2})}{q_t q_{t-1} q_{t-2}} \\ &= \frac{(-1)^t a_t q_{t-1}}{q_t q_{t-1} q_{t-2}} = \frac{(-1)^t a_t}{q_t q_{t-2}} \end{align*}$

所以得证。

奇数编号渐进分数大于偶数编号

先证明，任何奇数编号的渐进分数大于相邻的两个偶数编号的渐进分数：

$\begin{align*} x_t - x_{t-1} &= \frac{p_t}{q_t} - \frac{p_{t-1}}{q_{t-1}} \\ &= \frac{p_t q_{t-1} - p_{t-1} q_t}{q_t q_{t-1}} \\ &= \frac{(-1)^{t-1}}{q_t q_{t-1}} > 0 \\ 当t 是奇数时，&x_t > x_{t-1} \\ 当t 是偶数时，&x_{t-1} > x_t \end{align*}$

有了这个结论，我们就可以用反证法证明任何奇数编号的渐进分数都大于任何偶数编号的渐进分数了。

假设 $\exists r$，使得

$x_{2m+1} \leq x_{2r}$

如果 $r < m$，则

$x_{2r} < x_{2m} \Longrightarrow x_{2m+1} \leq x_{2r} < x_{2m}$

与前面证明的矛盾。

如果 $r > m$，则

$x_{2r+1} < x_{2m+1} \Longrightarrow x_{2r+1} < x_{2m+1} \leq x_{2r}$

与前面证明的矛盾。

综上所述，假设不成立，任何奇数编号的渐进分数都大于任何偶数编号的渐进分数。

综述

所以我们就得到了结论③的单调性了：

有限连分数 $[a_0, a_1, \ldots, a_n] = \frac{p_n}{q_n} = x_n$

如果 $n$ 是偶数，则 $x_n$ 是偶数编号里最大的渐进分数，且 $x_n$ 小于所有奇数编号的渐进分数。

如果 $n$ 是奇数，则 $x_n$ 是奇数编号里最小的渐进分数，且 $x_n$ 大于所有偶数编号的渐进分数。

结论④证明 😵

我们已知相邻两项一定分别为奇偶数编号，所以由结论③可知，$x\in (xt ,x{t-1})$

又因为，$qt > q{t-1}$，所以

$\frac{p_t}{q_t} \text{ 和 } \frac{p_{t-1}}{q_{t-1}} \text{ 都是分母不超过 } q_t \text{ 的渐进分数。}$

假设 $\frac{p}{q}$ 是分母不超过 $q_t$ 的 $x$ 的最佳近似值（$q \leq q_t$）。那么

$\frac{p}{q} \text{比 } \frac{p_t}{q_t} \text{ 和 } \frac{p_{t-1}}{q_{t-1}} \text{ 更接近 } x$

所以

$\frac{p}{q} \text{ 位于 } x \text{ 和 } x_t \text{ 之间，或者位于 } x \text{ 和 } x_{t-1} \text{ 之间。}$

构建这两个式子：

$\begin{align*} \vert \frac{p}{q} - \frac{p_{t-1}}{q_{t-1}} \vert = \vert \frac{p q_{t-1} - p_{t-1} q}{q q_{t-1}} \vert \geq \frac{1}{q q_{t-1}} \\ \vert \frac{p}{q} - \frac{p_{t-1}}{q_{t-1}} \vert \leq \vert \frac{p_t}{q_t} - \frac{p_{t-1}}{q_{t-1}} \vert = \vert \frac{p_t q_{t-1} - p_{t-1} q_t}{q_t q_{t-1}} \vert = \frac{1}{q_t q_{t-1}} \end{align*}$

组合这两个式子，我们得到：

$\frac{1}{q q_{t-1}} \leq \vert \frac{p}{q} - \frac{p_{t-1}}{q_{t-1}} \vert \leq \frac{1}{q_t q_{t-1}}$ $q \leq q_t \Longrightarrow \frac{1}{q q_{t-1}} \geq \frac{1}{q_t q_{t-1}} \Longrightarrow \vert \frac{p}{q} - \frac{p_{t-1}}{q_{t-1}} \vert = \frac{1}{q q_{t-1}} = \frac{1}{q_t q_{t-1}}$

所以，$\frac{p}{q} = \frac{p_t}{q_t}$，得证。

上一章：密码学数学基础 - 连分数 👈
下一章：密码学数学基础 - 群论基础 👈
回到开始：关于我 👈

相关链接：
密码学算法 - Wiener算法 👈