初等数论 第三章 数的表示.docVIP

第三章 数的表示对于数的十进制表示，我们已经是很熟悉的了。本章主要介绍实数的b进制表示和连分数表示，以及一些基本知识。第一节 实数的b进制表示法本节介绍实数的b进制表示法。定理 设b是大于的整数，则任何正整数a都可以写成a = akbk + ak - 1bk - 1 + L + a1b + a 0的形式，其中ak 0，ai（0 i k）是在0与b - 1之间唯一确定的整数。证明 由带余数除法，有整数k，使得 a = q1b + a0， 0 a0 b - 1， q1 b， q1 = q2b + a1， 0 a1 b - 1， q2 b， L Lqk - 1 = qkb + ak - 1，0 ak - 1 b - 1，0 qk b - 1，其中诸ai与qi都是唯一确定的。记qk = ak，则0 m，使得an b - 1，则a的表示式(1)是唯一的。证明 记a1 = ba，则0 a1 b - 1。记a1 = ba - a1，则0 a1 1，并且a =。如果a1 = 0，则定理得证。如果0 a1 1，则重复上述过程，有a1 =，0 a2 b - 1，0 a2 1。将这样的过程进行k次之后，我们得到a =， (2)其中0 ai b - 1（0 i k），0 ak ck，于是，由式(3)得到。 (4)显然。另一方面，由式(3)，有，在上式中，当且仅当ai = b - 1，ci = 0或ci = b - 1，ai = 0（i k + 1） (5)时等号成立。因此，若使式(4)成立，必是式(5)成立。这说明，在定理的假设条件下，表达式(1)是唯一的。证毕。定理 设b是大于1的整数，则任何正实数a都可以唯一地写成a =，0 ai b - 1，i k (6)的形式，其中，对于任何正整数m，都存在n m，使得a - n b - 1。证明 留做习题。定义 设a是正实数，若式(6)成立，则记为a = (akak - 1La1a0.a -1a - 2L)b ， (7)并称它是a的b进制表示，称ai（i k）是a的b进制表示的位数码。当b = 10时，就是通常的十进制记数法，此时常略去式(7)中的括号和下标b = 10。此外，称(akak - 1La1a0)b 与 (0.a-1a -2L)b 分别是a的b进制表示的整数部分和小数部分。定义 设a是实数，0 a 0，使得cs + i = cs + i + kt，i = 1, 2, L, t，k = 0, 1, 2, L (9)成立，则称式(8)中的b进制小数是循环小数，并记作a =()b 。若使式(9)成立的最小的s和t分别是s0和t0，则称是循环节；若s0 = 0，则称式(8)中的小数是（b进制）纯循环小数。下面，我们讨论数的十进制表示的小数的循环性。为方便计，将使用记号表示整数(anan - 1La1a0)10，用0.a1a2L表示小数(0.a1a2L)10。定理 循环小数表示有理数。证明 不妨只考察小于1的正循环小数。设有循环小数a = 0.a1Lasb1Lbtb1LbtL ，记，则是有理数。证毕。推论 纯循环小数表示有理数；若(a, b) = 1，则(b, 10) = 1。证明 在定理4的证明中，取s = 0，则，所以a(10t - 1) = bB。但是(a, b) = 1，所以b10t 1，于是(b, 10) = 1。证毕。定理 设a与b是正整数，0 a b，(a, b) = 1，并且(b, 10) = 1，则的十进制表示是纯循环小数。证明 因为 (b, 10) = 1，由Euler定理可知，有正整数k，使得10k 1 (mod b)，0 k j(b)，因此存在整数q使得， (10)其中0 q = (10k - 1) 10k - 1，即q具有的形式，而且ak, L, a1不能都等于0，也不能都等于9。由式(10)，有= 0.akak - 1La1akak - 1La1L 。证毕。定理 设a与b是正整数，0 a b，(a, b) = 1，并且b = 2a5bb1，(b1, 10) = 1，b1 1，此处a与b是不全为零的正整数，则可以表示成循环小数，其中不循环的位数码个数是m = maxa, b。证明 不妨假设m = b a，则， (11)其中0 a1 b1，0 M 1， a1, a2, L, an 是的有限简单连分数，证明aqn - 1 - bpn - 1 = (-1)n(a, b)，其中(a, b)是a与b的最大公约数。解 由渐近分数定义，。记a = (a, b)A，b = (a, b)B，则(A, B) = 1。由定理2可知(pn, qn) = 1，因此，pn = A，qn = B，a = pn(a, b)，b = qn(a, b)。 (3)再利用定理2，有pnqn - 1 - pn - 1qn = (-1)n，aqn - 1 - bpn - 1 = (-1)n(a, b)。注：例1给出了求不定方程ax + by = c的特解的一个方法。例 求不定方程13x + 17y = 5 (4)的解。解 容易验证，于是p1 = 0，p2 = 10 + 1 = 1，p3 = 31 + 0 = 3，q1 = 1，q2 = 1， q3 = 31 + 1 = 4。由例1有134 - 173 = (-1)4 = 1，因此1345 - 1735 = 5，即x = 20，y = -15是方程(4)的特解，所以方程(4)的一般解是， tZ。例 设是 a1, a2, L, an, L 的第n个渐近分数，则= an, an - 1, L, a2 （n 2）。 (5)解 用归纳法证明。当n = 2时，由式(1)，有= a2 = a2 ，即式(5)成立。假设式(5)当n = k（k 2）时成立，即= ak, ak - 1, L, a2 ， (6)则由式(1)，有，由此及式(6)，得到= ak + 1, ak , L, a2 ，即式(5)当n = k + 1时也成立。由归纳法证得到所需结论。例4 求连分数 0, 1, 2, 1, 2, L 的值。解 设 ，则x =，解这个方程，并注意0 x 0，(a, b) = 1，由辗转相除法，有 , , , ，因此= q1, q2, L, qn + 1 。证毕。定理 任一无理数可以表示成无限简单连分数。证明 对于任意的无理数b，总有无理数b1，使得。由此，对于任意的无理数，我们依次得到： (1)LL下面证明a = a1, a2, L, an, L 。由上面的等式及第二节定理1可见，对于任意的正整数n 1，有a = a1, a2, L, an, an =， (2)其中（i 1）是 a1, a2, L, an, L 的渐近分数。因此，由式(2)及第二节定理2，得到。 (3)再利用式(1)及第二节定理1推论，得到，即a = a1, a2, L, an, L 。证毕。推论 设a是实无理数，那么，对于任意的正整数n，存在dn与hn，0 dn, hn an + 1，因此，anqn + qn - 1 an + 1qn + qn - 1 = qn + 1 qn ，所以，必有dn，hn，0 dn, hn 1，使得，由此及(3)式得证。证毕。定理3 无理数的连分数表示是唯一的。证明 设a = a1, a2, L, an, L = b1, b2, L, bn, L 。 (4)我们用归纳法证明ai = bi ，i 1。 (5)对于正整数i，记ai = ai, ai + 1, L, an, L ，bi = bi, bi + 1, L, bn, L ，则a =，其中a1与b1是整数，a2与b2是大于1的无理数。因此，a1 = b1，即式(5)当i = 1时成立。假设式(5)对于i 1，bm 1，则n = m，ai = bi（1 i n）；() 若an是大于1的整数，则有理数仅有两种表示成简单连分数的方法，即 a1, a2, L, an = a1, a2, L, an -1, 1 。证明 留做习题。定理5 设（n = 1, 2, L）是实数a的连分数的渐近分数，则对于任意的正整数q qn及整数p，有 。 (6)证明 若a =，则式(6)是显然的。若，则a有第n + 1个渐近分数，并且，于是。 (7)分别以下情况讨论：() 若，则由式(7)可知式(6)成立。() 若，则由式(7)得到。由上式及定理2推论得到式(6)。() 若，则pqn + 1 = qp n + 1 ，因此，由第二节定理3得到qn + 1q，q qn + 1 qn ，这与假设矛盾。因此，这一情况不出现。() 若，则容易看出，于是，这与第二节定理2矛盾。因此，这一情况不出现。证毕。定理5说明，在分母不超过qn的分数中，是a的最佳有理逼近。这是渐近分数的一个非常重要的性质。定理6(Hurwitz) 设a是无理数，那么，在它的连分数的任何两个相邻渐近分数中，至少有一个满足不等式。 (8)证明 设是a的两个相邻的渐近分数，不妨设。于是，由第二节定理2，。 （9)若都不使式(8)成立，则， (10)于是， (11)但是qn + 1 qn ，所以qn2 + qn + 12 2qnqn + 1 ，因此，由式(11)得到，这与式(9)矛盾。所以式(10)中至少有一个不等式不成立。证毕。推论 对于任意的无理数a，存在无穷多个有理数满足。例 写出的连分数解 由L L得到= 2, 1, 4, 1, 4, 1, L 。例 求的误差不超过10 - 4的有理近似值。解 由定理2推论，只需求正整数n，使得 10 - 4。利用例1及第二节定理1，有下表n12345678an21414141pn2314178299478577qn11562935169204由于q7q8 104，因此取n = 7。即所求的的有理近似是。习 题 三1. 证明定理4。2. 求的连分数。3. 求的误差 10 - 5的有理逼近。4. 求sin18的误差 10 - 5的有理逼近。5. 已知圆周率p = 3, 7, 15, 1, 292, 1, 1, 1, 21, L ，求p的误差 10 - 6的有理逼近。6. 证明：连分数展开的第k个渐近分数为。此处Fn是Fibonacci数列。第四节 循环连分数本节要讨论整系数二次方程的实无理根的连分数。定义 设 a1, a2, L, an, L 是无限简单连分数。如果存在正整数s与t，使得as + i = as + kt + i，i = 1, 2, L , t；k = 0, 1, 2, L ，则称 a1, a2, L, an, L 是循环连分数,并记为 a1, L, as, 。如果s = 0，则称它是纯循环连分数。定理 任何循环连分数表示一个不可约整系数二次方程的实根。证明 设a = a1, L, as, = a1, a2, L, an, L 是循环连分数。记an = an + 1, an + 2, L，以（n = 1, 2, L）表示a的渐近分数。() 若s = 0，则a = = b1, L, bt, a ，因此，由第二节定理1得到a =，即a满足整系数二次方程qtx2 + (qt - 1 - pt)x - pt - 1 = 0。 (1)() 若s 0，则a = a1, L, as, b1, L, bt, b1, L, bt, L ，由第二节定理可知，a =，于是as =，由此得到(qs + ta - ps + t)(ps - 1 - aqs - 1) = (qsa - ps)(ps + t - 1 - aqs + t - 1)，即a满足整系数二次方程Ax2 + Bx+ C = 0， (2)其中A = qs qs + t - 1 - qs + t qs - 1 ，B = qs + tps - 1 + qs + tps - 1 - psqs + t - 1 - qsps + t - 1 ，C = psps + t - 1 - ps + tps - 1 。由于a是无限连分数，所以是实无理数，因此方程(1)和(2)都是不可约的。证毕。定理 设a = 是纯循环连分数，则它所满足的二次方程的另一个根在-1与0之间。证明 从定理1的证明中可知，a满足方程(1)。记f(x) = qtx2 + (q t - 1 - pt)x - pt - 1 = 0，则由at 1及pi 0，qi 0（i 1）可知f(0) = -pt - 1 0 ，因此，方程(1)必有一根在-1与0之间。由于a1, a2, L, an, L都是正整数，所以a 0，即这个根不是a。证毕。定理 设a是二次不可约整系数方程Ax2 + Bx + C = 0 (3)的实根，则a的简单连分数是循环连分数。证明 因为方程(3)是不可约的，所以a是无理数，因此，由第三节定理2，它可以表示成无限简单连分数，设a = a1, a2, L, an, L 。记an = an + 1, an + 2, L ，则a = a1, a2, L, an, an ，由第二节定理1，得到a =，将此式代入式(3)，可知an满足方程Anx2 + Bnx + Cn = 0， (4)其中。 (5)由第三节定理2推论，。因此，由于a满足方程(3)，有|An| |A|(2|a| + 1) + |B| 。 (6)由式(5)又推出|Cn| |A|(2|a| + 1) + |B| 。 (7)此外，容易验证Bn2 - 4AnCn = (B2 - 4AC)(pnqn - 1 - pn - 1qn)2 = B2 - 4AC，我们看到，存在只与A，B，C及a有关的M，使得|Bn| M。 (8)由式(6)，式(7)，式(8)可知，对于n = 1, 2, 3, L，数组An, Bn, Cn只有有限多个不同的取法，因此，至少有三组是相同的，即存在正整数n1，n2，n3，n1 n2 n3，使得这样，满足同一个方程A0x2 + B0x + C0 = 0。 (9)但是方程(9)至多有两个不同的解，所