有理数、小数与连分数

有理数与小数表示

Proposition

两个整数之比是（ $10$ 进制下的）有限小数或无限循环小数，并且当且仅当分母只含 $2,5$ 作为素因子时，可以表示为有限小数。

Proof

对于两个整数之比 $\frac{a}{b}$ （ $b > 0$ ），将 $b$ 分解为两个非负整数的乘积

Copy LaTeX

其中 $b_1 = 1$ 或者 $b_1$ 只含有 $2,5$ 作为素因子； $b_2$ 的素因子不含 $2,5$ 。显然存在 $m \in \mathbb{N}$ ，使得 $b_1 \mid 10^n$ ，由欧拉定理，由于 $\text{gcd}(b_2,10)=1$ ，有 $b_2 \mid 10^{\varphi(b_2)} - 1$ ，因此

Copy LaTeX

对于 $b_2 = 1$ （即 $\varphi(b_2) = 0$ ）的情况， $\frac{a}{b}$ 可以表示为有限小数

Copy LaTeX

对于 $\varphi(b_2) > 0$ 的情况， $\frac{a}{b}$ 可以表示为无限循环小数

Copy LaTeX

Remark

上述证明过程也可以绕过欧拉定理，只使用简单直观的抽屉原理：考虑 $b_2+1$ 个数

Copy LaTeX

关注它们模 $b_2$ 的余数，由于余数只有 $b_2$ 种，必然存在 $0 \leqslant m_1 < m_2 \leqslant b_2$ ，使得

Copy LaTeX

再利用 $gcd(b_2,10) = 1$ 可以得到

Copy LaTeX

其它证明步骤不变。

Remark

上述结论显然可以推广到任意整数进制：对于 $m$ 进制，当且仅当分母仅含 $m$ 的素因子作为素因子时，可以表示为（ $m$ 进制下的）有限小数。这个结论同时表明，有限小数与无限循环小数并不是有理数中截然不同的两个类型，只是在指定进制下的表示形式不同。例如考虑二进制下的例子（以下标区分小数的进制）

Copy LaTeX

由于二进制只有素因子 $2$ ，十进制有素因子 $2,5$ ，因此二进制下有限小数在十进制下必然也是有限小数，但是反之不成立。

埃及分数

Definition

称分子为 $1$ ，分母为正整数的有理数为埃及分数，又称为单位分数。

Theorem

任何真分数 $\frac{p}{q} \in \mathbb{Q}^+$ （ $p < q$ ）都可以表示为有限个互不相同的单位分数之和：

Copy LaTeX

其中 $n_1 < n_2 < \cdots < n_k$ ， $n_i \in \mathbb{Z}^+$ 。

Remark

如果不要求单位分数互不相同，那么显然有

Copy LaTeX 个

这个结论过于平凡。

Remark

我们需要讨论单位分数分解的存在性和唯一性，存在性是容易证明的，唯一性通常无法保证，例如总是可以进一步分解（这种处理也可以用来保证分母互异）

Copy LaTeX

但是我们可以考虑某种意义上的最优分解：例如要求分解的单位分数个数尽可能少，或者出现的最大分母尽可能小。我们还可以考虑固定分解的单位分数个数等，这部分的问题仍然未被解决，例如 Erdős–Straus 猜想：对于任意大于 $1$ 的正整数 $n$ ， $\frac{4}{n}$ 始终可以分解为三个单位分数

Copy LaTeX

Proof (埃及分数展开式的存在性证明)

有很多方法都可以用来构造单位分数分解，下面给出一种最简单直观的贪心算法：对于目标有理数 $\frac{p}{q}$ ，首先寻找最小的正整数 $n_1$ ，使得

Copy LaTeX

显然有 $n_1 = \lceil \frac{q}{p} \rceil$ 。因此

Copy LaTeX

那么，如果 $\frac{p_1}{q_1}$ 是既约分数，

Copy LaTeX

分子严格递减，如果可以约分，显然分子会更小。如果新的分子大于 $1$ ，继续重复上述构造过程，可以得到分母序列 $\{q,q_1,q_2,\cdots\}$ 和严格递减的分子序列 $\{p,p_1,p_2,\cdots\}$ ，由于分子严格递减，这个过程必然在有限步之后终止，最终得到

Copy LaTeX

如果最终的分解中出现分母重复，很容易对其进行进一步处理以保证分母互异。

Example

例如考虑 $\frac{7}{19}$ 的分解，第一步

Copy LaTeX

第二步

Copy LaTeX

因此

Copy LaTeX

连分数

在理论和应用中通常只考虑简单连分数——要求分子全为 $1$ ，如果允许任意的分子，则称为一般连分数，下面默认讨论简单连分数。

Definition (连分数)

称形如

Copy LaTeX

的表达式为连分数，记为

Copy LaTeX

其中

Copy LaTeX

若展开在有限步终止，则称为有限连分数，否则称为无限连分数。

对任意 $x \in \mathbb{R}$ ，连分数的计算是非常直接的：首先，取 $a_0 = \lfloor x \rfloor$ ，此时记余项的倒数为 $x_1$ ，得到

Copy LaTeX

对于 $x_k$ 进行判断：若 $x_k \in \mathbb{Z}$ ，则过程终止，否则继续递归定义

Copy LaTeX

这个计算过程要么在有限步终止，要么可以无限持续下去，分别对应有限连分数和无限连分数。由构造过程可以立刻得到如下结论：

Theorem

任意实数 $x \in \mathbb{R}$ 都可以表示为一个（有限或无限的）连分数。

Theorem (有理数的连分数刻画)

对于实数 $x \in \mathbb{R}$ ，有

Copy LaTeX 的连分数展开是有限的

Proof

必要性是显然的，只需要证明充分性：设 $x = \frac{p}{q} \in \mathbb{Q}$ ，对整数对 $(p,q)$ 进行欧几里得算法：

Copy LaTeX

由于余数严格递减，必在有限步终止，即存在 $r_k = 0$ 。该过程与连分数展开完全一致，因此可以得到有限连分数表示。

Remark

在小数表示法中对实数进行的分类如下：有理数等价于有限或无限循环小数；无理数则等价于无限不循环小数。有限或无限循环小数的差异并不是有理数内蕴的，而是完全由进制决定的。在连分数表示法中对实数进行的分类则更加完美：有理数等价于有限连分数，无理数等价于无限连分数。

Remark

连分数表示在无限情形下唯一；在有限情形下存在如下非唯一性。例如

Copy LaTeX

更一般地，总是有

Copy LaTeX

通常约定最后一项满足 $a_n \geqslant 2$ ，使得表示具有唯一性。

Example

Copy LaTeX

Solution

直接计算

Copy LaTeX

继续

Copy LaTeX

观察到出现循环，始终有

Copy LaTeX

Remark

更一般的结论： $x$ 有无限循环的连分数表示，当且仅当 $x$ 是二次无理数（例如 $\sqrt{2}$ ）。

连分数和行列式还存在一些联系。

Proposition

有限简单连分数可以表示为两个行列式的商：

Copy LaTeX

其中

Copy LaTeX

Remark

证明只需要对递推关系进行归纳。例如考虑 $n=2$ 的例子：

Copy LaTeX