《高等算术》第四章讲了连分式。有理数（无理数）总可以表示为有限（无限）长的连分式。满足一定限制条件的情况下，这种表示是唯一的。截取连分式的前若干个数，得到的分数称为渐进 (convergent)，渐进总是交替地大于和小于目标数，并最终收敛到目标数。

一个有趣的现象是：二次代数数¹的连分式总是循环的。这个性质进一步可以用于求解 Pell 方程 \[x^2-Ny^2=1\] 它的解是 \(\sqrt N\) 的（循环）连分式的某些渐进的分子和分母。

一点题外话：连分式在初等数论之外也有应用。例如可以证明 π 和 e 的连分式是无限长的，因此它们是无理数。

4.1 将下列数表示为连分数：105/143, 112/153, 89/144, 169/239。

解 这里用书上采用的紧凑记法表示连分式。 \begin{align*} \frac{105}{143} &= \frac{1}{1+}\frac{1}{2+}\frac{1}{1+}\frac{1}{3+}\frac{1}{4+}\frac{1}{2} \\ \frac{112}{153} &= \frac{1}{1+}\frac{1}{2+}\frac{1}{1+}\frac{1}{2+}\frac{1}{1+}\frac{1}{2+}\frac{1}{1+}\frac{1}{2} \\ \frac{89}{144} &= \frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{2} \\ \frac{239}{169} &= \frac{1}{1+}\frac{1}{2+}\frac{1}{2+}\frac{1}{2+}\frac{1}{2+}\frac{1}{2+}\frac{1}{2} \end{align*}

4.2 计算 \([3,1,4,1,6]\) 和 \([6,1,4,1,3]\)。

说明 这里的方括号表示所谓的高斯括号。 可以用欧拉法则计算：枚举所有在序列中删除若干个（可以是零个）不重叠的相邻数对的方案，每个方案剩下的数字求乘积，最后将乘积相加。此外，根据欧拉法则可知，将括号里的所有数反转次序不影响计算结果。

解 \begin{align*} [3,1,4,1,6] &= 3\times1\times4\times1\times6 \\ &\quad{} + 4\times1\times6 + 3\times1\times6 + 3\times1\times6 + 3\times1\times4\\ &\quad{} + 6 + 4 + 3 \\ &= 157 \\ [6,1,4,1,3] &= [3,1,4,1,6] = 157 \end{align*}

4.3 写出下列连分式的渐进：

1. \(1+\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1}\)
2. \(2+\frac{1}{2+}\frac{1}{2+}\frac{1}{2+}\frac{1}{2+}\frac{1}{2+}\frac{1}{2}\)
3. \(2+\frac{1}{4+}\frac{1}{4+}\frac{1}{4+}\frac{1}{4}\)
4. \(1+\frac{1}{1+}\frac{1}{2+}\frac{1}{1+}\frac{1}{2+}\frac{1}{1+}\frac{1}{2}\)

说明 计算渐进 \(A_m\over B_m\) 可采用递推式 \begin{align*} A_m &= q_m A_{m-1} + A_{m-2} \\ B_m &= q_m B_{m-1} + B_{m-2} \\ \end{align*}

解

1. 1, 2, 3/2, 5/3, 8/6, 13/8, 21/13.
2. 2, 5/2, 12/5, 29/12, 70/29, 169/70, 408/169.
3. 2, 9/4, 28/17, 161/72, 682/305.
4. 1, 2, 5/3, 7/4, 19/11, 26/15, 71/41.

4.5 求下列不定方程的通解：\(355x-113y=1\) 和 \(355x+113y=1\)。

解 用连分式法求解第一个方程。 \[\frac{355}{113} = 3 + \cfrac{1}{7+\cfrac{1}{16}}\] 渐进为 \(3, \frac{22}{7}, \frac{355}{113}\)。代入可知 \(355\times7-113\times22 = -1\)。由此可知一组整数解为 \(\begin{cases}x=-7\\ y=-22\end{cases}\)。通解为 \[\cases{x = -7 + 113t\\ y = -22 + 355t}\qquad (t\in\mathbb Z)\] 改变 \(y\) 的符号即得第二个方程的解： \[\cases{x = -7 + 113t\\ y = 22 - 355t}\qquad (t\in\mathbb Z)\]

4.6 求 \(\sqrt{51}\) 和 \(\sqrt{52}\) 的循环的连分数。解不定方程 \(x^2-51y^2=\pm1\) 和 \(x^2-52y^2=\pm1\)。

解 求连分式的方法是求这个数的整数部分和小数部分。整数部分就是连分数中的部分商；然后再对小数部分的倒数重复此操作。 \begin{align*} \alpha_0 &= \sqrt{51} = 7 + \frac{1}{\alpha_1}\\ \alpha_1 &= \frac{1}{\sqrt{51}-7} = \frac{\sqrt{51}+7}{2} = 7 + \frac{1}{\alpha_2} \\ \alpha_2 &= \frac{2}{\sqrt{51}-7} = \sqrt{51}+7 = 14 + \frac{1}{\alpha_3} \\ \alpha_3 &= \frac{1}{\sqrt{51}-7} = \alpha_1\\ \end{align*} 由此可知 \(\alpha_1,\alpha_2\) 是循环节，因此 \(\sqrt{51} = [7; \overline{7, 14}]\)。

按照同样的计算方法可知 \(\sqrt{52} = [7;\overline{4,1,2,1,4,14}]\)。

根据本章第 11 节的内容，当 \[\sqrt{N} = q_0 + \frac{1}{q_1+}\cdots\frac{1}{q_n+}\frac{1}{2q_0+}\frac{1}{q_1+}\cdots\] 时，渐进 \(A_n\over B_n\) 满足方程 \[A_n^2 - NB_n^2 = (-1)^{n-1}\]

对于第一个方程，计算 \(\sqrt{51}\) 在 \(n=1\) 时的渐进 \(\frac{A_1}{B_1} = \frac{50}{7}\)。代入得 \(50^2 - 51\times 7^2 = 1\)。

对于第二个方程，计算 \(\sqrt{51}\) 在 \(n=5\) 时的渐进 \(\frac{A_5}{B_5} = \frac{649}{90}\)。代入得 \(649^2 - 52\times 90^2 = 1\)。

4.11 求 \(3^{1/3}\) 的前若干项部分商，求出对应的渐进并给出十进制表示。

解法一 估算可知 \(3^{1/3}\approx 1.4\), \(3^{2/3}\approx2.1\)。 \begin{align*} \alpha_0 &= 3^{1/3} = 1 + \frac{1}{\alpha_1}\\ \alpha_1 &= \frac{1}{3^{1/3}-1} = \frac{3^{2/3}+3^{1/3}+1}{2} = 2 + \frac{1}{\alpha_2} \\ \alpha_2 &= \frac{2}{3^{2/3}+3^{1/3}-3} = \frac{2}{3}3^{2/3}+3^{1/3}+1 = 3 + \frac{1}{\alpha_3} \\ \alpha_3 &= \frac{1}{\frac{2}{3}3^{2/3}+3^{1/3}+1} = \frac{7\cdot3^{2/3}+10\cdot3^{1/3}+6}{29} = 1 + \alpha_4\\ \alpha_4 &= \cdots \end{align*} 因此 \(3^{1/3} = [1;2,3,1,\ldots]\)。对应的渐进为 \[1,\frac{3}{2}=1.5,\frac{10}{7}\approx 1.429,\frac{13}{9}\approx 1.444\]

注 含三次方根的式子（实际上是有理数的三次扩域 \(\mathbb Q(3^{1/3})\) 的元素）求倒数比较麻烦；一般用待定系数法，因为结果总能表示为 \(x+y3^{1/3}+z^{2/3}\) 的形式。

解法二 为了避免繁琐的算术，可以使用电子计算器在浮点数的精度内计算若干项。

import math

x = 3 ** (1/3)
for i in range(8):
    q = math.floor(x)
    x = 1 / (x - q)
    if i == 0:
        aa, bb, a, b = 1, 0, q, 1
    else:
        aa, bb, a, b = a, b, q * a + aa, q * b + bb
    print(q, "%3d/%-3d=%.6f" % (a, b, a / b))

1   1/1  =1.000000
2   3/2  =1.500000
3  10/7  =1.428571
1  13/9  =1.444444
4  62/43 =1.441860
1  75/52 =1.442308
5 437/303=1.442244
1 512/355=1.442254

4.12 写出 \(e\) 的连分式的前几项渐进： \[2+\frac{1}{1+}\frac{1}{2+}\frac{1}{1+}\frac{1}{1+}\frac{1}{4+}\frac{1}{1+}\frac{1}{1+}\frac{1}{6+}\frac{1}{1+}\frac{1}{1+}\frac{1}{8+}\cdots\] 第一个逼近 \(e\) 到小数点后六位的渐进是哪个？ [\(e\approx2.718281828\ldots\)]

解 前几项渐进为 \begin{align*} \tfrac21 &= 2, & \tfrac31 &= 3,\\ \tfrac83 &\approx 2.6666667, & \tfrac{11}4 &= 2.75, \\ \tfrac{19}7 &\approx 2.7142857, & \tfrac{87}{32} &= 2.71875,\\ \tfrac{106}{39} &\approx 2.7179487, & \tfrac{193}{71} &\approx 2.7183099,\\ \tfrac{1264}{465} &\approx 2.7182796, & \tfrac{1457}{536} &\approx 2.7182836,\\ \tfrac{2721}{1001} &\approx 2.7182817, & \tfrac{23225}{8544} &\approx 2.7182818.\\ \end{align*} 可见，第一个准至六位小数的渐进是 \(2721\over1001\)。

4.13 使用 \(\sqrt2\) 的连分数的交错的渐进求解 Pell 方程 \(x^2-2y^2=1\) 和 \(x^2-2y^2=-1\)。证明每个渐进的分子和分母都满足递推式 \(u_{n+1} = 6u_n - u_{n-1}\)。

解 \(\sqrt2 = [1;\bar 2]\)。渐进为 \[\frac11, \frac32, \frac75, \frac{17}{12}, \frac{41}{29}, \ldots\] 其中，偶数项和奇数项的分子和分母分别满足方程 \begin{align*} A_{2n}^2 - 2B_{2n}^2 &= -1\\ A_{2n+1}^2 - 2B_{2n+1}^2 &= 1 \end{align*} 这就给出了题中两个方程的解。

根据渐进的递推公式，有 \(A_{n+1} = 2A_n + A_{n-1}\) 对任意 \(n \ge 1\) 都成立。于是当 \(n \ge 3\) 时， \begin{align*} A_{n+1} &= 2A_n + A_{n-1} \\ &= 2(2A_{n-1} + A_{n-2}) + A_{n-1} \\ &= 6A_{n-1} - A_{n-1} + 2A_{n-2} \\ &= 6A_{n-1} - (2A_{n-2}+A_{n-3}) + 2A_{n-2} \\ &= 6A_{n-1} - A_{n-3} \\ \end{align*} 这样就推出了隔一项的递推式。对 \(B_n\) 可以推导出一样的递推式。由此可知满足题中某个 Pell 方程的渐进序列的分子和分母都满足递推式 \(u_{n+1} = 6u_n - u_{n-1}\)。

4.16 求既是平方数（可以表为 \(n^2\)）又是三角数（可以表为 \(n(n+1)/2\)）的数。

解 设 \(N\) 是满足条件的数，那么存在整数 \(m,n\) 使得 \(N=m^2 = n(n+1)/2\)，这个式子等价于 \[(2n+1)^2 - 8m^2 = 1\] 因为 \(\sqrt 8 = [2; \overline{1, 4}]\)，所以方程 \(x^2 - 8y^2 = 1\) 的解为 \(x = A_{2n+1}\), \(y=B_{2n+1}\)。设 \(u_n = B_{2n+1}\)，则 \[u_0 = B_1 = 1,\,u_1 = B_3 = 6,\,u_2 = B_5 = 35,\,\ldots\] 仿照 4.13 可得递推式 \[u_{n+1} = 6u_n - u_{n-1}\qquad(n\ge 1)\tag{$*$}\] 而所有的 \(u_n^2\) 都是平方数且是三角数，例如 \[u_0^2 = 1^2 = \frac{1\times2}{2},\,u_1^2 = 6^2 = \frac{8\times9}{2},\,u_3^2 = 35^2 = \frac{49\times50}{2},\,\ldots\] 事实上，可以由 \((*)\) 得到 \(u_n\) 的通项公式，并由此求出满足条件的数的通项 \[u_n^2 = \frac1{64}\left[\bigl(4+3\sqrt2\bigr)\bigl(3+2\sqrt2\bigr)^n + \bigl(4-3\sqrt2\bigr)\bigl(3-2\sqrt2\bigr)^n\right]^2\] 其中 \(n=0,1,2,\ldots\)。

4.17 \(\pi\) 的连分数展开的前几项是 \[3+\frac{1}{7+}\frac{1}{15+}\frac{1}{1+}\frac{1}{292+}\frac{1}{1+}\frac{1}{1+}\cdots\] 求前若干项渐进。其中哪些是 \(\pi\) 的非常好的近似？

解 渐进为 \begin{align*} 3 &= 3.0000000, & \frac{22}{7} &\approx 3.1428571, \\ \frac{333}{106} &\approx 3.1415094, & \frac{355}{113} &\approx 3.1415929,\\ \frac{103993}{33102} &\approx 3.1415927, & \ldots \end{align*} 可见 \(\frac{22}{7}\) 和 \(\frac{355}{113}\) 都是很好的近似。