连分数
字数 3164 2025-10-27 08:14:12

连分数

连分数是一种表示实数的方法，它通过将一个数表示为整数部分加上一个分数的倒数，并递归地对分母进行同样的操作来获得。这种表示法在数论中对于研究无理数的有理逼近、解佩尔方程以及分析算法的复杂度等方面都有重要应用。

第一步：连分数的基本定义与有限连分数

一个简单的有限连分数形式如下：

\[a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}} \]

其中 \(a_0\) 是整数，而 \(a_1, a_2, \dots, a_n\) 都是正整数。为了书写简便，这个连分数通常记作 \([a_0; a_1, a_2, \dots, a_n]\)。

让我们看一个具体的例子：考虑有理数 \(\frac{17}{10}\)。

  1. 首先，它的整数部分是 \(1\)，所以 \(a_0 = 1\)。剩下的部分是 \(\frac{7}{10}\)。
  2. 取其倒数，得到 \(\frac{10}{7}\)。这个数的整数部分是 \(1\)，所以 \(a_1 = 1\)。剩下的部分是 \(\frac{3}{7}\)。
  3. 取其倒数，得到 \(\frac{7}{3}\)。整数部分是 \(2\)，所以 \(a_2 = 2\)。剩下的部分是 \(\frac{1}{3}\)。
  4. 取其倒数，得到 \(\frac{3}{1} = 3\)。整数部分是 \(3\)，所以 \(a_3 = 3\)。没有剩余部分了。

因此，\(\frac{17}{10}\) 可以表示为连分数 \([1; 1, 2, 3]\)。你可以通过从右往左计算来验证：\(3\) 的倒数是 \(\frac{1}{3}\)，加上 \(2\) 是 \(2 + \frac{1}{3} = \frac{7}{3}\)，其倒数是 \(\frac{3}{7}\)，加上 \(1\) 是 \(1 + \frac{3}{7} = \frac{10}{7}\)，其倒数是 \(\frac{7}{10}\)，最后加上 \(1\) 得到 \(1 + \frac{7}{10} = \frac{17}{10}\)。关键点：任何一个有理数都有且只有两种有限连分数表示，一种是奇数项结尾，一种是偶数项结尾（例如，\([1; 1, 2, 3]\) 和 \([1; 1, 2, 2, 1]\) 都等于 \(\frac{17}{10}\)）。

第二步：无限连分数与无理数

如果一个数是无理数，那么它的连分数展开将是无限的。例如，黄金比例 \(\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\)。

  1. \(\phi\) 的整数部分是 \(1\)，所以 \(a_0 = 1\)。
  2. 剩下的小数部分是 \(\phi - 1 = \frac{1}{\phi}\)（这是黄金比例的一个关键性质）。
  3. 因此，我们有 \(\phi = 1 + \frac{1}{\phi}\)。
  4. 现在，我们可以把等式右边的 \(\phi\) 再次用这个关系式展开：\(\phi = 1 + \cfrac{1}{1 + \cfrac{1}{\phi}}\)。
  5. 这个过程可以无限继续下去：\(\phi = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{\ddots}}}\)。

所以，黄金比例的连分数表示是 \([1; 1, 1, 1, \dots]\)，一个非常简单的无限循环连分数。这种表示法揭示了 \(\phi\) 的一个深刻性质：它是“最难以”用有理数逼近的无理数之一。

第三步：渐近分数与最佳有理逼近

对于一个连分数 \([a_0; a_1, a_2, \dots]\)（无论是有限还是无限），我们可以计算它在各个阶段“截断”后得到的有理数，这些有理数称为“渐近分数”或“收敛项”。

计算渐近分数有一个高效的递推公式。定义：

  • \(p_{-2} = 0, \quad p_{-1} = 1\)
  • \(q_{-2} = 1, \quad q_{-1} = 0\)

对于 \(k = 0, 1, 2, \dots, n\)，有：

\[p_k = a_k \cdot p_{k-1} + p_{k-2} \]

\[ q_k = a_k \cdot q_{k-1} + q_{k-2} \]

那么，第 \(k\) 个渐近分数就是 \(C_k = \frac{p_k}{q_k}\)。

让我们用之前的例子 \([1; 1, 2, 3]\) 来计算：

  • \(k=0\): \(a_0=1\)

    • \(p_0 = 1 \cdot 1 + 0 = 1\)
    • \(q_0 = 1 \cdot 0 + 1 = 1\)
    • \(C_0 = 1/1 = 1\)

  • \(k=1\): \(a_1=1\)

    • \(p_1 = 1 \cdot 1 + 1 = 2\)
    • \(q_1 = 1 \cdot 1 + 0 = 1\)
    • \(C_1 = 2/1 = 2\)

  • \(k=2\): \(a_2=2\)

    • \(p_2 = 2 \cdot 2 + 1 = 5\)
    • \(q_2 = 2 \cdot 1 + 1 = 3\)
    • \(C_2 = 5/3 \approx 1.666...\)

  • \(k=3\): \(a_3=3\)

    • \(p_3 = 3 \cdot 5 + 2 = 17\)
    • \(q_3 = 3 \cdot 3 + 1 = 10\)
    • \(C_3 = 17/10 = 1.7\)

这些渐近分数 \(1, 2, \frac{5}{3}, \frac{17}{10}\) 依次逼近原始值 \(\frac{17}{10}\)。核心定理：对于一个实数，其连分数展开的渐近分数是所有分母不超过 \(q_k\) 的有理数中，最接近该实数的有理数。这就是“最佳有理逼近”的含义。

第四步：连分数在数论中的应用：解佩尔方程

佩尔方程是形如 \(x^2 - d y^2 = 1\) 的方程，其中 \(d\) 是一个非平方正整数。例如，\(x^2 - 2y^2 = 1\)。

一个关键发现是，\(\sqrt{d}\) 的连分数展开是周期性的。对于 \(\sqrt{2}\)，其连分数展开为 \([1; \overline{2}]\)，即 \([1; 2, 2, 2, \dots]\)。

计算它的渐近分数：

  • \(C_0 = 1/1 = 1\)
  • \(C_1 = [1; 2] = 1 + 1/2 = 3/2 = 1.5\)
  • \(C_2 = [1; 2, 2] = 1 + 1/(2 + 1/2) = 1 + 1/(5/2) = 1 + 2/5 = 7/5 = 1.4\)
  • \(C_3 = [1; 2, 2, 2] = 17/12 \approx 1.416...\)

现在检查这些渐近分数是否满足佩尔方程 \(x^2 - 2y^2 = 1\)：

  • \(C_1 = 3/2\): \(3^2 - 2 \times 2^2 = 9 - 8 = 1\)。成立！所以 (3, 2) 是一个解。
  • \(C_3 = 17/12\): \(17^2 - 2 \times 12^2 = 289 - 288 = 1\)。成立！所以 (17, 12) 是另一个解。

结论：佩尔方程的基本解（最小的正整数解）可以通过计算 \(\sqrt{d}\) 的连分数展开的渐近分数来找到。这个性质使得连分数成为解决这类数论问题的强大工具。

连分数 连分数是一种表示实数的方法，它通过将一个数表示为整数部分加上一个分数的倒数，并递归地对分母进行同样的操作来获得。这种表示法在数论中对于研究无理数的有理逼近、解佩尔方程以及分析算法的复杂度等方面都有重要应用。 第一步：连分数的基本定义与有限连分数 一个简单的有限连分数形式如下： \[ a_ 0 + \cfrac{1}{a_ 1 + \cfrac{1}{a_ 2 + \cfrac{1}{\ddots + \cfrac{1}{a_ n}}}} \] 其中 \(a_ 0\) 是整数，而 \(a_ 1, a_ 2, \dots, a_ n\) 都是正整数。为了书写简便，这个连分数通常记作 \([ a_ 0; a_ 1, a_ 2, \dots, a_ n ]\)。 让我们看一个具体的例子：考虑有理数 \(\frac{17}{10}\)。 首先，它的整数部分是 \(1\)，所以 \(a_ 0 = 1\)。剩下的部分是 \(\frac{7}{10}\)。 取其倒数，得到 \(\frac{10}{7}\)。这个数的整数部分是 \(1\)，所以 \(a_ 1 = 1\)。剩下的部分是 \(\frac{3}{7}\)。 取其倒数，得到 \(\frac{7}{3}\)。整数部分是 \(2\)，所以 \(a_ 2 = 2\)。剩下的部分是 \(\frac{1}{3}\)。 取其倒数，得到 \(\frac{3}{1} = 3\)。整数部分是 \(3\)，所以 \(a_ 3 = 3\)。没有剩余部分了。 因此，\(\frac{17}{10}\) 可以表示为连分数 \([ 1; 1, 2, 3]\)。你可以通过从右往左计算来验证：\(3\) 的倒数是 \(\frac{1}{3}\)，加上 \(2\) 是 \(2 + \frac{1}{3} = \frac{7}{3}\)，其倒数是 \(\frac{3}{7}\)，加上 \(1\) 是 \(1 + \frac{3}{7} = \frac{10}{7}\)，其倒数是 \(\frac{7}{10}\)，最后加上 \(1\) 得到 \(1 + \frac{7}{10} = \frac{17}{10}\)。 关键点 ：任何一个有理数都有且只有两种有限连分数表示，一种是奇数项结尾，一种是偶数项结尾（例如，\([ 1; 1, 2, 3]\) 和 \([ 1; 1, 2, 2, 1 ]\) 都等于 \(\frac{17}{10}\)）。 第二步：无限连分数与无理数 如果一个数是无理数，那么它的连分数展开将是无限的。例如，黄金比例 \(\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\)。 \(\phi\) 的整数部分是 \(1\)，所以 \(a_ 0 = 1\)。 剩下的小数部分是 \(\phi - 1 = \frac{1}{\phi}\)（这是黄金比例的一个关键性质）。 因此，我们有 \(\phi = 1 + \frac{1}{\phi}\)。 现在，我们可以把等式右边的 \(\phi\) 再次用这个关系式展开：\(\phi = 1 + \cfrac{1}{1 + \cfrac{1}{\phi}}\)。 这个过程可以无限继续下去：\(\phi = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{\ddots}}}\)。 所以，黄金比例的连分数表示是 \([ 1; 1, 1, 1, \dots ]\)，一个非常简单的无限循环连分数。这种表示法揭示了 \(\phi\) 的一个深刻性质：它是“最难以”用有理数逼近的无理数之一。 第三步：渐近分数与最佳有理逼近 对于一个连分数 \([ a_ 0; a_ 1, a_ 2, \dots ]\)（无论是有限还是无限），我们可以计算它在各个阶段“截断”后得到的有理数，这些有理数称为“渐近分数”或“收敛项”。 计算渐近分数有一个高效的递推公式。定义： \(p_ {-2} = 0, \quad p_ {-1} = 1\) \(q_ {-2} = 1, \quad q_ {-1} = 0\) 对于 \(k = 0, 1, 2, \dots, n\)，有： \[ p_ k = a_ k \cdot p_ {k-1} + p_ {k-2} \] \[ q_ k = a_ k \cdot q_ {k-1} + q_ {k-2} \] 那么，第 \(k\) 个渐近分数就是 \(C_ k = \frac{p_ k}{q_ k}\)。 让我们用之前的例子 \([ 1; 1, 2, 3 ]\) 来计算： \(k=0\): \(a_ 0=1\) \(p_ 0 = 1 \cdot 1 + 0 = 1\) \(q_ 0 = 1 \cdot 0 + 1 = 1\) \(C_ 0 = 1/1 = 1\) \(k=1\): \(a_ 1=1\) \(p_ 1 = 1 \cdot 1 + 1 = 2\) \(q_ 1 = 1 \cdot 1 + 0 = 1\) \(C_ 1 = 2/1 = 2\) \(k=2\): \(a_ 2=2\) \(p_ 2 = 2 \cdot 2 + 1 = 5\) \(q_ 2 = 2 \cdot 1 + 1 = 3\) \(C_ 2 = 5/3 \approx 1.666...\) \(k=3\): \(a_ 3=3\) \(p_ 3 = 3 \cdot 5 + 2 = 17\) \(q_ 3 = 3 \cdot 3 + 1 = 10\) \(C_ 3 = 17/10 = 1.7\) 这些渐近分数 \(1, 2, \frac{5}{3}, \frac{17}{10}\) 依次逼近原始值 \(\frac{17}{10}\)。 核心定理 ：对于一个实数，其连分数展开的渐近分数是所有分母不超过 \(q_ k\) 的有理数中，最接近该实数的有理数。这就是“最佳有理逼近”的含义。 第四步：连分数在数论中的应用：解佩尔方程 佩尔方程是形如 \(x^2 - d y^2 = 1\) 的方程，其中 \(d\) 是一个非平方正整数。例如，\(x^2 - 2y^2 = 1\)。 一个关键发现是，\(\sqrt{d}\) 的连分数展开是周期性的。对于 \(\sqrt{2}\)，其连分数展开为 \([ 1; \overline{2}]\)，即 \([ 1; 2, 2, 2, \dots ]\)。 计算它的渐近分数： \(C_ 0 = 1/1 = 1\) \(C_ 1 = [ 1; 2 ] = 1 + 1/2 = 3/2 = 1.5\) \(C_ 2 = [ 1; 2, 2 ] = 1 + 1/(2 + 1/2) = 1 + 1/(5/2) = 1 + 2/5 = 7/5 = 1.4\) \(C_ 3 = [ 1; 2, 2, 2 ] = 17/12 \approx 1.416...\) 现在检查这些渐近分数是否满足佩尔方程 \(x^2 - 2y^2 = 1\)： \(C_ 1 = 3/2\): \(3^2 - 2 \times 2^2 = 9 - 8 = 1\)。成立！所以 (3, 2) 是一个解。 \(C_ 3 = 17/12\): \(17^2 - 2 \times 12^2 = 289 - 288 = 1\)。成立！所以 (17, 12) 是另一个解。 结论 ：佩尔方程的基本解（最小的正整数解）可以通过计算 \(\sqrt{d}\) 的连分数展开的渐近分数来找到。这个性质使得连分数成为解决这类数论问题的强大工具。