高等算术习题(4) -- 连分式

高等算术习题(4) – 连分式

Sun Mar 6, 2022

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

一个有趣的现象是：二次代数数1的连分式总是循环的。这个性质进一步可以用于求解 Pell 方程 x2−Ny2=1 它的解是 N 的（循环）连分式的某些渐进的分子和分母。

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

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

解 这里用书上采用的紧凑记法表示连分式。 105143=11+12+11+13+14+12112153=11+12+11+12+11+12+11+1289144=11+11+11+11+11+11+11+11+11+12239169=11+12+12+12+12+12+12

---

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

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

解 [3,1,4,1,6]=3×1×4×1×6+4×1×6+3×1×6+3×1×6+3×1×4+6+4+3=157[6,1,4,1,3]=[3,1,4,1,6]=157

---

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

1. 1+11+11+11+11+11+11
2. 2+12+12+12+12+12+12
3. 2+14+14+14+14
4. 1+11+12+11+12+11+12

说明 计算渐进 AmBm 可采用递推式 Am=qmAm−1+Am−2Bm=qmBm−1+Bm−2

解

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。

解 用连分式法求解第一个方程。 355113=3+17+116 渐进为 3,227,355113。代入可知 355×7−113×22=−1。由此可知一组整数解为 {x=−7y=−22。通解为 {x=−7+113ty=−22+355t(t∈Z) 改变 y 的符号即得第二个方程的解： {x=−7+113ty=22−355t(t∈Z)

---

4.6 求 51 和 52 的循环的连分数。解不定方程 x2−51y2=±1 和 x2−52y2=±1。

解 求连分式的方法是求这个数的整数部分和小数部分。整数部分就是连分数中的部分商；然后再对小数部分的倒数重复此操作。 α0=51=7+1α1α1=151−7=51+72=7+1α2α2=251−7=51+7=14+1α3α3=151−7=α1 由此可知 α1,α2 是循环节，因此 51=[7;7,14―]。

按照同样的计算方法可知 52=[7;4,1,2,1,4,14―]。

根据本章第 11 节的内容，当 N=q0+1q1+⋯1qn+12q0+1q1+⋯ 时，渐进 AnBn 满足方程 An2−NBn2=(−1)n−1

对于第一个方程，计算 51 在 n=1 时的渐进 A1B1=507。代入得 502−51×72=1。

对于第二个方程，计算 51 在 n=5 时的渐进 A5B5=64990。代入得 6492−52×902=1。

---

4.11 求 31/3 的前若干项部分商，求出对应的渐进并给出十进制表示。

解法一 估算可知 31/3≈1.4, 32/3≈2.1。 α0=31/3=1+1α1α1=131/3−1=32/3+31/3+12=2+1α2α2=232/3+31/3−3=2332/3+31/3+1=3+1α3α3=12332/3+31/3+1=7⋅32/3+10⋅31/3+629=1+α4α4=⋯ 因此 31/3=[1;2,3,1,…]。对应的渐进为 1,32=1.5,107≈1.429,139≈1.444

注 含三次方根的式子（实际上是有理数的三次扩域 Q(31/3) 的元素）求倒数比较麻烦；一般用待定系数法，因为结果总能表示为 x+y31/3+z2/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+11+12+11+11+14+11+11+16+11+11+18+⋯ 第一个逼近 e 到小数点后六位的渐进是哪个？ [e≈2.718281828…]

解 前几项渐进为 21=2,31=3,83≈2.6666667,114=2.75,197≈2.7142857,8732=2.71875,10639≈2.7179487,19371≈2.7183099,1264465≈2.7182796,1457536≈2.7182836,27211001≈2.7182817,232258544≈2.7182818. 可见，第一个准至六位小数的渐进是 27211001。

---

4.13 使用 2 的连分数的交错的渐进求解 Pell 方程 x2−2y2=1 和 x2−2y2=−1。证明每个渐进的分子和分母都满足递推式 un+1=6un−un−1。

解 2=[1;2¯]。渐进为 11,32,75,1712,4129,… 其中，偶数项和奇数项的分子和分母分别满足方程 A2n2−2B2n2=−1A2n+12−2B2n+12=1 这就给出了题中两个方程的解。

根据渐进的递推公式，有 An+1=2An+An−1 对任意 n≥1 都成立。于是当 n≥3 时， An+1=2An+An−1=2(2An−1+An−2)+An−1=6An−1−An−1+2An−2=6An−1−(2An−2+An−3)+2An−2=6An−1−An−3 这样就推出了隔一项的递推式。对 Bn 可以推导出一样的递推式。由此可知满足题中某个 Pell 方程的渐进序列的分子和分母都满足递推式 un+1=6un−un−1。

---

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

解 设 N 是满足条件的数，那么存在整数 m,n 使得 N=m2=n(n+1)/2，这个式子等价于 (2n+1)2−8m2=1 因为 8=[2;1,4―]，所以方程 x2−8y2=1 的解为 x=A2n+1, y=B2n+1。设 un=B2n+1，则 u0=B1=1,u1=B3=6,u2=B5=35,… 仿照 4.13 可得递推式 (∗)un+1=6un−un−1(n≥1) 而所有的 un2 都是平方数且是三角数，例如 u02=12=1×22,u12=62=8×92,u32=352=49×502,… 事实上，可以由 (∗) 得到 un 的通项公式，并由此求出满足条件的数的通项 un2=164[(4+32)(3+22)n+(4−32)(3−22)n]2 其中 n=0,1,2,…。

---

4.17 π 的连分数展开的前几项是 3+17+115+11+1292+11+11+⋯ 求前若干项渐进。其中哪些是 π 的非常好的近似？

解 渐进为 3=3.0000000,227≈3.1428571,333106≈3.1415094,355113≈3.1415929,10399333102≈3.1415927,… 可见 227 和 355113 都是很好的近似。

---

1. 指不可约有理系数二次多项式的根。用抽象代数的语言，即有理数域 ℚ 的某个二次扩域中的元素。 ↩︎

---