初等数论基础

Transcription

1 第一章整除理论 整除性理论是初等数论的基础 本章要介绍带余数除法, 辗转相除法, 最大公约数, 最小公倍数, 算术基本定理以及它们的一些应用 第一节数的整除性 定义 设 a,b 是整数,b 0, 如果存在整数 c, 使得 a = bc 成立, 则称 a 被 b 整除,a 是 b 的倍数,b 是 a 的约数 ( 因数或除数 ), 并且使用记号 ba; 如果不存在整数 c 使得 a = bc 成立, 则称 a 不被 b 整除, 记为 b a 显然每个非零整数 a 都有约数,a, 称这四个数为 a 的平凡约数,a 的另外的约数称为非平凡约数 被 整除的整数称为偶数, 不被 整除的整数称为奇数 定理 下面的结论成立 : (ⅰ) ab ab; (ⅱ) ab,bc ac; (ⅲ) ba, =,,, ba x a x

2 a x, 此处 x ( =,,, ) 是任意的整数 ; (ⅳ) ba bcac, 此处 c 是任意的非零整数 ; (ⅴ) ba,a 0 b a ;ba 且 a < b a = 0 证明留作习题 定义 若整数 a 0,, 并且只有约数 和 a, 则称 a 是素数 ( 或质数 ); 否则称 a 为合数 以后在本书中若无特别说明, 素数总是指正素数 定理 任何大于 的整数 a 都至少有一个素约数 证明若 a 是素数, 则定理是显然的 若 a 不是素数, 那么它有两个以上的正的非 平凡约数, 设它们是 d, d,, d 不妨设 d 是 其中最小的 若 d 不是素数, 则存在 e >,e >, 使得 d = e e, 因此,e 和 e 也是 a 的正的非平凡约数 这与 d 的最小性矛盾 所以 d 是素数 证毕 推论任何大于 的合数 a 必有一个不超过 a 的素约数 证明使用定理 中的记号, 有 a = d d, 其中 d > 是最小的素约数, 所以 d a 证毕 例 设 r 是正奇数, 证明 : 对任意的正整数 n, 有

3 有 n r r n r 解对于任意的正整数 a,b 以及正奇数, a b = (a b)(a a b a 3 b b ) = (a b)q, 其中 q 是整数 记 s = r r n r, 则 s = ( r n r ) (3 r (n ) r ) (n r r ) = (n )Q, 其中 Q 是整数 若 n s, 由上式知 n, 因为 n >, 这是不可能的, 所以 n s 例 设 A = { d, d,, d } 是 n 的所有约数 的集合, 则 n n n B = {,,, } d d d 也是 n 的所有约数的集合 解由以下三点理由可以证得结论 : (ⅰ) A 和 B 的元素个数相同 ; 然 ; n (ⅱ) 若 d A, 即 d n, 则 n, 反之亦 d n n (ⅲ) 若 d d j, 则 d d j 例 3 以 d(n) 表示 n 的正约数的个数, 例如 : 3

4 d() =,d() =,d(3) =,d(4) = 3, 问 : d() d() d(997) 是否为偶数? 解对于 n 的每个约数 d, 都有 n = d d n, n 因此,n 的正约数 d 与是成对地出现的 只有 d n 当 d =, 即 n = d n 时,d 和才是同一个数 d d 故当且仅当 n 是完全平方数时,d(n) 是奇数 因为 44 < 997 < 45, 所以在 d(), d(),, d(997) 中恰有 44 个奇数, 故 d() d() d(997) 是偶数 例 4 设凸 n 边形 M 的顶点是 A, A,, A n, 点 O 在 M 的内部, 用,,, n 将 M 的 n 条边分别编号, 又将 OA, OA,, OA n 也同 样进行编号, 若把这些编号作为相应的线段的长度, 证明 : 无论怎么编号, 都不能使得三角形 OA A, OA A 3,, OA n A 的周长都相等 则 解假设这些三角形的周长都相等, 记为 s ns = 3( n) = 3n(n ), 4

5 即 s = 3(n ), 因此 3(n ), 这是不可能的, 这个矛盾说明这些三角形的周长不可能全都相等 例 5 设整数, 证明 : (ⅰ) 若 n <, a n,a, 则 a; (ⅱ) 若 3 n < 3 +, b n,b 3, 则 3 b 解 (ⅰ) 若 a, 则存在整数 q, 使得 a= q 显然 q 只可能是 0 或 此时 a= 0 或, 这都是不可能的, 所以 a; (ⅱ) 若 3 b-, 则存在整数 q, 使得 b-= q3, 显然 q 只可能是 0,, 或 此时 b-= 0, 3, 或 3, 这都是不可能的, 所以 3 b 例 6 写出不超过 00 的所有的素数 解将不超过 00 的正整数排列如下 :

6 按以下步骤进行 : (ⅰ) 删去, 剩下的后面的第一个数是, 是素数 ; (ⅱ) 删去 后面的被 整除的数, 剩下的 后面的第一个数是 3,3 是素数 ; (ⅲ) 再删去 3 后面的被 3 整除的数, 剩下的 3 后面的第一个数是 5,5 是素数 ; (ⅳ) 再删去 5 后面的被 5 整除的数, 剩下的 5 后面的第一个数是 7,7 是素数 ; 照以上步骤可以依次得到素数, 3, 5, 7,, 由定理 推论可知, 不超过 00 的合数必有一个不超过 0 的素约数, 因此在删去 7 后面被 7 整除的数以后, 就得到了不超过 00 的全部素数 6

7 在例 6 中所使用的寻找素数的方法, 称为 Eratosthenes 筛法 它可以用来求出不超过任何固定整数的所有素数 在理论上这是可行的 ; 但在实际应用中, 这种列出素数的方法需要大量的计算时间, 是不可取的 例 7 证明 : 存在无穷多个正整数 a, 使得 n 4 a(n =,, 3, ) 都是合数 解取 a = 4 4, 对于任意的 nn, 有 n = (n ) 4n = (n n)(n n) 因为 n n = (n ), 所以, 对于任意的 =, 3, 以及任意的 nn, n 4 a 是合数 例 8 设 a, a,, a n 是整数, 且 则 4n a a a n = 0,a a a n = n, 解如果 n, 则 n, a, a,, a n 都是奇数 于是 a a a n 是奇数个奇数之和, 不可能 等于零, 这与题设矛盾, 所以 n, 即在 a, a,, a n 中至少有一个偶数 如果只有一个偶数, 不妨 7

8 设为 a, 那么 a ( n) 此时有等式 a a n = a, 在上式中, 左端是 (n ) 个奇数之和, 右端是偶 数, 这是不可能的, 因此, 在 a, a,, a n 中至 少有两个偶数, 即 4n 例 9 若 n 是奇数, 则 8n 解设 n =, 则 n = ( ) = 4( ) 在 和 中有一个是偶数, 所以 8n 例 9 的结论虽然简单, 却是很有用的 例如, 使用例 3 中的记号, 我们可以提出下面的问题 : 问题 d() d() d(997) 被 4 除的 余数是多少? 例 0 证明 : 方程 a a a 3 = 999 () 无整数解 解若 a,a,a 3 都是奇数, 则存在整数 A,A,A 3, 使得 a = 8A,a = 8A,a 3 = 8A 3, 于是 a a a 3 = 8(A A A 3 ) 3 由于 999 被 8 除的余数是 7, 所以 a,a,a 3 不可能都是奇数 由式 (),a,a,a 3 中只能有一个奇数, 设 a 为奇数,a,a 3 为偶数, 则存在整数 A,A, 8

9 A 3, 使得 a = 8A,a = 8A r,a 3 = 8A 3 s, 于是 a a a 3 = 8(A A A 3 ) r s, 其中 r 和 s 是整数, 而且只能取值 0 或 4 这样 a a a 3 被 8 除的余数只可能是 或 5, 但 999 被 8 除的余数是 7, 所以这样的 a,a,a 3 也不能使式 () 成立 综上证得所需要的结论 习题一. 证明定理. 证明 : 若 m mn q, 则 m mq n 3. 证明 : 任意给定的连续 39 个自然数, 其中至少存在一个自然数, 使得这个自然数的数字和能被 整除 4. 设 是 n 的最小素约数,n = n,n >, 证明 : 若 > 3 n, 则 n 是素数 5. 证明 : 存在无穷多个自然数 n, 使得 n 不能表示为 a (a > 0 是整数, 为素数 ) 的形式 9

10 第二节带余数除法 在本节中, 我们要介绍带余数除法及其简单应用 定理 ( 带余数除法 ) 设 a 与 b 是两个整数, b 0, 则存在唯一的两个整数 q 和 r, 使得 a = bq r,0 r < b () 证明存在性若 ba,a = bq,qz, 可 取 r = 0 若 b a, 考虑集合 A = { a b;z }, 其中 Z 表示所有整数的集合, 以后, 仍使用此记号, 并以 N 表示所有正整数的集合 在集合 A 中有无限多个正整数, 设最小的正整数是 r = a 0 b, 则必有 0 < r < b, () 否则就有 r b 因为 b a, 所以 r b 于是 r > b, 即 a 0 b > b,a 0 b b > 0, 这样, 在集合 A 中, 又有正整数 a 0 b b < r, 这与 r 的最小性矛盾 所以式 () 必定成立 取 q = 0 知式 () 成立 存在性得证 唯一性假设有两对整数 q,r 与 q,r 都使得式 () 成立, 即 a = q b r = q b r,0 r, r < b, 则 (q q )b = r r, r r < b, 0

11 (3) 因此 r r = 0,r = r, 再由式 (3) 得出 q = q, 唯一性得证 证毕 定义 称式 () 中的 q 是 a 被 b 除的商,r 是 a 被 b 除的余数 由定理 可知, 对于给定的整数 b, 可以按照被 b 除的余数将所有的整数分成 b 类 在同一类中的数被 b 除的余数相同 这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究 以后在本书中, 除特别声明外, 在谈到带余数除法时总是假定 b 是正整数 例 设 a,b,x,y 是整数, 和 m 是正整数, 并且 a = a m r,0 r < m, b = b m r,0 r < m, 则 ax by 和 ab 被 m 除的余数分别与 r x r y 和 r r 被 m 除的余数相同 特别地,a 与 r 被 m 除的余数相同 解由 ax by = (a m r )x (b m r )y = (a x b y)m r x r y 可知, 若 r x r y 被 m 除的余数是 r, 即 r x r y = qm r,0 r < m, 则 ax by = (a x b y q)m r,0 r < m, 即 ax by 被 m 除的余数也是 r 同样方法可以证明其余结论 例 设 a, a,, a n 为不全为零的整数,

12 以 y 0 表示集合 A = { y;y = a x a n x n,x Z, n } 中的最小正数, 则对于任何 ya,y 0 y; 特别地, y 0 a, n 解设 y 0 = a x a n x n, 对任意的 y = a x a n x n A, 由定理, 存在 q, r 0 Z, 使 得 因此 y = qy 0 r 0,0 r 0 < y 0 r 0 = y qy 0 = a (x qx ) a n (x n qx n )A 如果 r 0 0, 那么, 因为 0 < r 0 < y 0, 所以 r 0 是 A 中比 y 0 还小的正数, 这与 y 0 的定义矛盾 所以 r 0 = 0, 即 y 0 y 显然 a A( n), 所以 y 0 整除每个 a ( n) 例 3 任意给出的五个整数中, 必有三个数之和被 3 整除 解设这五个数是 a, =,, 3, 4, 5, 记 a = 3q r,0 r < 3, =,, 3, 4, 5 分别考虑以下两种情形 : (ⅰ) 若在 r, r,, r 5 中数 0,, 都出现, 不妨设 r = 0,r =,r 3 =, 此时 a a a 3 = 3(q q q 3 ) 3 可以被 3 整除 ;

13 (ⅱ) 若在 r, r,, r 5 中数 0,, 至少有 一个不出现, 这样至少有三个 r 要取相同的值, 不妨设 r = r = r 3 = r(r = 0, 或 ), 此时 a a a 3 = 3(q q q 3 ) 3r 可以被 3 整除 例 4 设 a 0, a,, a n Z,f(x) = a n x n a x a 0, 已知 f(0) 与 f() 都不是 3 的倍数, 证明 : 若方程 f(x) = 0 有整数解, 则 3f() = a 0 a a () n a n 解对任何整数 x, 都有 x = 3q r,r = 0, 或,qZ (ⅰ) 若 r = 0, 即 x = 3q,qZ, 则 f(x) = f(3q) = a n (3q) n a (3q) a 0 = 3Q a 0 = 3Q f(0), 其中 Q Z, 由于 f(0) 不是 3 的倍数, 所以 f(x) 0; (ⅱ) 若 r =, 即 x = 3q,qZ, 则 f(x) = f(3q ) = a n (3q ) n a (3q ) a 0 = 3Q a n a a 0 = 3Q f(), 其中 Q Z 由于 f() 不是 3 的倍数, 所以 f(x) 0 因此若 f(x) = 0 有整数解 x, 则必是 x = 3q = 3q,q Z, 于是 0 = f(x) = f(3q ) = a n (3q ) n a (3q ) a 0 3

14 = 3Q 3 a 0 a a ( ) n a n = 3Q 3 f(), 其中 Q 3 Z 所以 3f() = a 0 a a () n a n 例 5 证明 : 对于任意的整数 n,f(n) = 3n 5 5n 3 7n 被 5 整除 解对于任意的正整数 n, 记 n = 5q r,0 r < 5 由例, n = 5Q r,n 4 = 5Q r, 其中 r 与 r 分别是 r 与 r 4 被 5 除的余数 以 R 表示 3n 4 5n 7 被 5 除的余数, 则 R 就是 3r 5r 7 被 5 除的余数, 而且 f(n) 被 5 除的余数就是 rr 被 5 除的余数, 记为 R 当 r = 0 时, 显然 R = 0, 即 53n 5 5n 3 7n 出下表 : 对于 r =,, 3,, 4 的情形, 通过计算列 r =, 4, 3 3, 4, 5, 0 6, 9 7, 8 r = r = R = R=

15 0 0 这证明了结论 例 6 设 n 是奇数, 则 6n 4 4n 解我们有 n 4 4n = (n )(n 5) 6 由第一节例题 9, 有 8n, 由此及 n 5 得到 6(n )(n 5) 例 7 证明 : 若 a 被 9 除的余数是 3,4,5 或 6, 则方程 x 3 y 3 = a 没有整数解 解对任意的整数 x,y, 记 x = 3q r,y = 3q r,0 r, r < 3 则存在 Q, R, Q, R Z, 使得 x 3 = 9Q R,y 3 = 9Q R, 3 3 其中 R 和 R 被 9 除的余数分别与 r 和 r 被 9 除的余数相同, 即 R = 0, 或 8,R = 0, 或 8 (4) 因此 x 3 y 3 = 9(Q Q ) R R 又由式 (4) 可知,R R 被 9 除的余数只可能是 0,,,7 或 8, 所以,x 3 y 3 不可能等于 a 习题二. 证明 :n 4 n 3 n 0n,nZ. 设 3a b, 证明 :3a 且 3b 3. 设 n, 是正整数, 证明 :n 与 n + 4 的个位数字相同 5

16 4. 证明 : 对于任何整数 n,m, 等式 n (n ) = m 不可能成立 5. 设 a 是自然数, 问 a 4 3a 9 是素数还是合数? 6. 证明 : 对于任意给定的 n 个整数, 必可以从中找出若干个作和, 使得这个和能被 n 整除 答案 第三节最大公约数 定义 整数 a, a,, a 的公共约数称为 a, a,, a 的公约数 不全为零的整数 a, a,, a 的公约数中最大的一个叫做 a, a,, a 的最 大公约数 ( 或最大公因数 ), 记为 (a, a,, a ) 由于每个非零整数的约数的个数是有限的, 所以最大公约数是存在的, 并且是正整数 如果 (a, a,, a ) =, 则称 a, a,, a 是 互素的 ( 或互质的 ); 如果 (a, a j) =,, j, j, 则称 a, a,, a 是两两互素的 ( 或两两互质 的 ) 6

17 显然,a, a,, a 两两互素可以推出 (a, a,, a ) =, 反之则不然, 例如 (, 6, 5) =, 但 (, 6) = 定理 下面的等式成立 : (ⅰ) (a, a,, a ) = ( a, a,, a ); (ⅱ) (a, ) =,(a, 0) = a,(a, a) = a ; (ⅲ) (a, b) = (b, a); (ⅳ) 若 是素数,a 是整数, 则 (, a) = 或 a; (ⅴ) 若 a = bq r, 则 (a, b) = (b, r) 证明 (ⅰ)(ⅳ) 留作习题 (ⅴ) 由第一节定理 可知, 如果 da,db, 则有 dr = a bq, 反之, 若 db,dr, 则 da = bq r 因此 a 与 b 的全体公约数的集合就是 b 与 r 的全体公约数的集合, 这两个集合中的最大正数当然相等, 即 (a, b) = (b, r) 证毕 由定理 可知, 在讨论 (a, a,, a n ) 时, 不 妨假设 a, a,, a n 是正整数, 以后我们就维持 这一假设 定理 设 a, a,, a Z, 记 A = { y;y = a x,x Z, } 7

18 如果 y 0 是集合 A 中最小的正数, 则 y 0 = (a, a,, a ) 证明设 d 是 a, a,, a 的一个公约数, 则 dy 0, 所以 d y 0 另一方面, 由第二节例 知,y 0 也是 a, a,, a 的公约数 因此 y 0 是 a, a,, a 的公约数中的最大者, 即 y 0 = ( a, a,, a ) 证毕 推论 设 d 是 a, a,, a 的一个公约数, 则 d(a, a,, a ) 这个推论对最大公约数的性质做了更深的刻划 : 最大公约数不但是公约数中的最大的, 而且是所有公约数的倍数 a ) 推论 (ma, ma,, ma ) = m (a, a,, 推论 3 记 = (a, a,, a ), 则 a a a (,,, ) =, a b 特别地, (, ) = ( a, b) ( a, b) 8

19 定理 3 (a, a,, a ) = 的充要条件是存 在整数 x, x,, x, 使得 a x a x a x = () 证明必要性 由定理 得到 充分性若式 () 成立, 如果 (a, a,, a ) = d >, 那么由 da ( ) 推出 da x a x a x =, 这是不可能的 所以有 (a, a,, a ) = 证毕 定理 4 对于任意的整数 a,b,c, 下面的结论成立 : (ⅰ) 由 bac 及 (a, b) = 可以推出 bc; (ⅱ) 由 bc,ac 及 (a, b) = 可以推出 abc 证明 (ⅰ) 若 (a, b) =, 由定理, 存在整数 x 与 y, 使得 ax by = 因此 acx bcy = c () 由上式及 bac 得到 bc 结论 (ⅰ) 得证 ; (ⅱ) 若 (a, b) =, 则存在整数 x,y 使得式 () 成立 由 bc 与 ac 得到 abac,abbc, 再由式 () 得到 abc 结论 (ⅱ) 得证 证毕 推论 若 是素数, 则下述结论成立 : (ⅰ) ab a 或 b; 9

20 (ⅱ) a a 证明留作习题 推论 若 (a, b) =, 则 (a, bc) = (a, c) 证明设 d 是 a 与 bc 的一个公约数, 则 da, dbc, 由式 () 得到,d c, 即 d 是 a 与 c 的公约数 另一方面, 若 d 是 a 与 c 的公约数, 则它也是 a 与 bc 的公约数 因此,a 与 c 的公约数的集合, 就是 a 与 bc 的公约数的集合, 所以 (a, bc) = (a, c) 证毕 推论 3 若 (a, b ) =, n, 则 (a, b b b n ) = 记 证明留作习题 定理 5 对于任意的 n 个整数 a, a,, a n, (a, a ) = d,(d, a 3 ) = d 3,,(d n, a n ) = d n 则,(d n, a n ) = d n, d n = (a, a,, a n ) 证明由定理 的推论, 我们有 d n = (d n, a n ) d n a n,d n d n, d n = (d n, a n ) d n a n,d n d n, d n a n,d n a n, d n d n, d n = (d n 3, a n ) d n a n,d n d n 3 0

21 d n a n,d n a n, d n a n,d n d n 3, d = (a, a ) d n a n,d n a n,,d n a,d n a, 即 d n 是 a, a,, a n 的一个公约数 另一方面, 对于 a, a,, a n 的任何公约数 d, 由定理 的推论及 d,, d n 的定义, 依次得 出 da,da dd, dd,da 3 dd 3, dd n,da n dd n, 因此 d n 是 a, a,, a n 的公约数中的最大者, 即 d n = (a, a,, a n ) 证毕 n 4 例 证明 : 若 n 是正整数, 则是 4n 3 既约分数 解由定理 得到 (n 4, 4n 3) = (7n, 4n 3) = (7n, ) = 注 : 一般地, 若 (x, y) =, 那么, 对于任意的整数 a,b, 有 (x, y) = (x ay, y) = (x ay, y b(x ay)) = (x ay,

22 (ab )y bx), x ay 因此, 是既约分数 ( ab) y bx 例 证明 : n n,nz 解由于 =,n n = (n ), 所以, 若 (n ), (3) 则 (n ), 因此, 由定理 4 的推论 得到 n, (n ) 再由式 (3) 得到, 这是不可能的 所以式 (3) 不能成立 注 : 这个例题的一般形式是 : 设 是素数,a,b 是整数, 则 (an b) c, 其中 c 是不被 整除的任意整数, 是任意的大于 的整数 例 3 设 a,b 是整数, 且 9a ab b, (4) 则 3(a, b) 解由式 (4) 得到 9(a b) 3ab 3(a b) 3ab 3(a b) 3a b (5) 9(a b) 再由式 (4) 得到 93ab 3ab 因此, 由定理 4 的推论, 得到

23 3a 或 3b 若 3a, 由式 (5) 得到 3b; 若 3b, 由 (5) 式也得到 3a 因此, 总有 3a 且 3b 由定理 的推论推出 3(a, b) 例 4 设 a 和 b 是正整数,b >, 则 b a 解 (ⅰ) 若 a < b, 且 b a (6) 成立, 则 b a b a a ( b a ), 于是 a =,b a =, 即 b =, 这是不可能的, 所以式 (6) 不成立 (ⅱ) 若 a = b, 且式 (6) 成立, 则由式 (6) 得到 a ( a ) a a a 3, 于是 b = a =, 这是不可能的, 所以式 (6) 不成立 (ⅲ) 若 a > b, 记 a = b r,0 r < b, 此时 b = ( b )( ( )b ( )b ) = ( b )Q, 其中 Q 是整数 所以 a = b + r = r ( b ) = r (( b )Q ) = ( b )Q ( r ), 其中 Q 是整数 因此 b a b r, 在 (ⅰ) 中已经证明这是不可能的, 所以式 (6) 不能 3

24 成立 综上证得 b a 习题三. 证明定理 中的结论 (ⅰ) (ⅳ). 证明定理 的推论, 推论 和推论 3 3. 证明定理 4 的推论 和推论 3 4. 设 x,yz,7x 3y, 证明 :79x 5y 5. 设 a,b,cn,c 无平方因子,a b c, 证明 :ab 3 n, Cn,, Cn 6. 设 n 是正整数, 求 C n 的 最大公约数 第四节最小公倍数 定义 整数 a, a,, a 的公共倍数称为 a, a,, a 的公倍数 a, a,, a 的正公倍数 中的最小的一个叫做 a, a,, a 的最小公倍 数, 记为 [a, a,, a ] 4

25 定理 下面的等式成立 : (ⅰ) [a, ] = a,[a, a] = a ; (ⅱ) [a, b] = [b, a]; (ⅲ) [a, a,, a ] = [ a, a, a ]; (ⅳ) 若 ab, 则 [a, b] = b 证明留作习题 由定理 中的结论 (ⅲ) 可知, 在讨论 a, a,, a 的最小公倍数时, 不妨假定它们都是正整 数 在本节中总是维持这一假定 最小公倍数和最大公约数之间有一个很重要的关系, 即下面的定理 定理 对任意的正整数 a,b, 有 ab [a, b] = ( a, b) 证明设 m 是 a 和 b 的一个公倍数, 那么存在整数,, 使得 m = a,m = b, 因此 a = b () 于是 a ( a, b) b ( a, b) a b 由于 (, ) =, 所以由第三节定理 4 得 ( a, b) ( a, b) 到 5

26 b b, 即 t, ( a, b) ( a, b) 其中 t 是某个整数 将上式代入式 () 得到 ab m = t () ( a, b) 另一方面, 对于任意的整数 t, 由式 () 所确定的 m 显然是 a 与 b 的公倍数, 因此 a 与 b 的公倍数必是式 () 中的形式, 其中 t 是整数 当 t = 时, 得到最小公倍数 ab [a, b] = ( a, b) 证毕 推论 两个整数的任何公倍数可以被它们的最小公倍数整除 证明由式 () 可得证 证毕 这个推论说明 : 两个整数的最小公倍数不但是最小的正倍数, 而且是另外的公倍数的约数 推论 设 m,a,b 是正整数, 则 [ma, mb] = m[a, b] 证明由定理 及第三节定理 的推论得到 m ab m ab mab [ma, mb] = = m[a, b] ( ma, mb) m( a, b) ( a, b) 证毕 记 定理 3 对于任意的 n 个整数 a, a,, a n, 6

27 [a, a ] = m,[m, a 3 ] = m 3,,[m n, a n ] = m n, 则 [m n, a n ] = m n, [a, a,, a n ] = m n 证明我们有 m n = [m n, a n ] m n m n,a n m n, m n = [m n, a n ] m n m n m n, a n m n,a n m n m n, m n = [m n3, a n ] m n3 m n m n, a n m n,a n m n,a n m n, a m n, m = [a, a ] a n m n,,a m n, 即 m n 是 a, a,, a n 的一个公倍数 另一方面, 对于 a, a,, a n 的任何公倍数 m, 由定理 的推论及 m,, m n 的定义, 得 m m,m 3 m,,m n m 即 m n 是 a, a,, a n 最小的正的公倍数 证毕 推论若 m 是整数 a, a,, a n 的公倍数, 则 [a, a,, a n ]m 7

28 证明留作习题 定理 4 整数 a, a,, a n 两两互素, 即 (a, a j ) =,, j n, j 的充要条件是 [a, a,, a n ] = a a a n (3) 证明必要性因为 (a, a ) =, 由定理 得到 aa [a, a ] = = a a ( a, a ) 由 (a, a 3 ) = (a, a 3 ) = 及第三节定理 4 推论 3 得到 (a a, a 3 ) =, 由此及定理 3 得到 [a, a, a 3 ] = [[a, a ], a 3 ] = [a a, a 3 ] = a a a 3 如此继续下去, 就得到式 (3) 充分性用归纳法证明 当 n = 时, 式 (3) 成为 [a, a ] = a a 由定理 aa a a = [a, a ] = (a, a ) =, ( a, a ) 即当 n = 时, 充分性成立 假设充分性当 n = 时成立, 即 [a, a,, a ] = a a a (a, a j ) =,, j, j 8

29 对于整数 a, a,, a, a +, 使用定理 3 中的记号, 由定理 3 可知 [a, a,, a, a + ] = [m, a + ] (4) 其中 m = [a, a,, a ] 因此, 如果 [a, a,, a, a + ] = a a a a +, 那么, 由此及式 (4) 得到 即 m a [a, a,, a, a + ] = [m, a + ] = = ( m, a ) a a a a +, m = a a a, ( m, a ) 显然 m a a a,(m, a + ) 所以若使上 式成立, 必是 (m, a + ) =, (5) 并且 m = a a a (6) 由式 (6) 与式 (5) 推出 (a, a + ) =, ; (7) 9

30 由式 (6) 及归纳假设推出 (a, a j ) =,, j, j (8) 综合式 (7) 与式 (8), 可知当 n = 时, 充分性成立 由归纳法证明了充分性 证毕 定理 4 有许多应用 例如, 如果 m, m,, m 是两两互素的整数, 那么, 要证明 m = m m m 整除某个整数 Q, 只需证明对于每个,, 都有 m Q 这一点在实际计算中是很有用的 对于函数 f(x), 要验证命题 mf(n),nz 是否成立, 可以用第二节例 5 中的方法, 验证 mf(r),r = 0,,, m 是否成立 这需要 做 m 次除法 但是, 若分别验证 m f(r ),r = 0,,, m, 是否成立, 则总共需要 做 m m m 次除法 后者的运算次数显 然少于前者 例 设 a,b,c 是正整数, 证明 :[a, b, c](ab, bc, ca) = abc 解由定理 3 和定理 有 [ a, b] c [a, b, c] = [[a, b], c] =, ([ a, b], c) (9) 由第三节定理 5 和定理 的推论, (ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b)) 30

31 = (, abc ) ( ab[ a, b], abc) ab([ a, b], c) ab [ a, b] [ a, b] [ a, b] 联合式 (9) 与式 (0) 得到所需结论 (0) 例 对于任意的整数 a, a,, a n 及整数, n, 证明 : [a, a,, a n ] = [[a,, a ],[a +,, a n ]] 解因为 [a, a,, a n ] 是 a,, a, a +,, a n 的公倍数, 所以由定理 推论, 推出 再由定理 3 推论知 [a,, a ][a, a,, a n ], [a +,, a n ][a, a,, a n ], [[a,, a ], [a +,, a n ]][a, a,, a n ] () 另一方面, 对于任意的 a ( n), 显然 a [[a,, a ], [a +,, a n ]], 所以由定理 3 推论可知 [a, a,, a n ][[a,, a ], [a +,, a n ]], 联合上式与式 () 得证 例 3 设 a,b,c 是正整数, 证明 : [a, b, c][ab, bc, ca] = [a, b][b, c][c, a] 解由定理 推论 及例, 有 3

32 [a, b, c][ab, bc, ca] = [[a, b, c]ab, [a, b, c]bc, [a, b, c]ca] = [[a b, ab, abc], [abc, b c, bc ], [a c, abc, ac ]] = [a b, ab, abc, abc, b c, bc, a c, abc, ac ] = [abc, a b, a c, b c, b a, c a, c b] 以及 [a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a] = [ab, b, ac, bc][c, a] = [ab[c, a], b [c, a], ac[c, a], bc[c, a]] = [abc, a b, b c, b a, ac, a c, bc, bca] = [abc, a b, a c, b c, b a, c a, c b], 由此得证 习题四. 证明定理. 证明定理 3 的推论 3. 设 a,b 是正整数, 证明 :(a b)[a, b] = a[b, a b] 4. 求正整数 a,b, 使得 a b = 0,(a, b) = 4,[a, b] = 设 a,b,c 是正整数, 证明 : 3

33 [ a, b, c] ( a, b, c) [ a, b][ b, c][ c, a] ( a, b)( b, c)( c, a) 6. 设 是正奇数, 证明 : 9 9 第五节辗转相除法 本节要介绍一个计算最大公约数的算法 辗转相除法, 又称 Eucld 算法 它是数论中的一个重要方法, 在其他数学分支中也有广泛的应用 定义 下面的一组带余数除法, 称为辗转相除法 设 a 和 b 是整数,b 0, 依次做带余数除法 : a = bq r, 0 < r < b, b = r q r, 0 < r < r, r = r q + r +,0 < r + < r, () r n = r n q n r n, 0 < r n < r n-, r n = r n q n + 由于 b 是固定的, 而且 33

34 b > r > r >, 所以式 () 中只包含有限个等式 下面, 我们要对式 () 所包含的等式的个数, 即要做的带余数除法的次数进行估计 引理 用下面的方式定义 Fbonacc 数列 {F n }: F = F =,F n = F n F n,n 3, 那么对于任意的整数 n 3, 有 F n > n, () 5 其中 = 证明容易验证 = 当 n = 3 时, 由 5 F 3 = > = 可知式 () 成立 假设式 () 对于所有的整数 n(n 3) 成立, 即 F >, n, 则 F n + = F n F n > n n 3 = n 3 ( ) = n 3 = n, 即当 = n 时式 () 也成立 由归纳法知式 () 对一切 n 3 成立 证毕 定理 (Lame) 设 a, bn,a > b, 使用在式 () 中的记号, 则 34

35 n < 5log 0 b 证明在式 () 中,r n,q n +,q ( n), 因此 r n = F, r n r n = F 3, r n r n r n F 3 F = F 4, +, 由此及式 () 得 b r r F n + F n = F n 即 b n = ( 5 ) n, 5 log 0 b nlog 0 n 5 这就是定理结论 证毕 定理 使用式 () 中的记号, 记 P 0 =,P = q,p = q P P,, Q 0 = 0,Q =,Q = q Q Q,, 则, aq bp = () r, =,,, n 证明当 = 时, 式 (3) 成立 当 = 时, 有 (3) 35

36 Q = q Q Q 0 = q,p = q P P 0 = q q, 此时由式 () 得到 aq bp = aq b(q q ) = (a bq )q b = r q b = r, 即式 (3) 成立 假设对于 < m( m n) 式 (3) 成立, 由此假设及式 () 得到 aq m bp m = a(q m Q m Q m ) b(q m P m P m ) = (aq m bp m )q m (aq m bp m ) = () m r m q m () m 3 r m = () m (r m r m q m ) = () m r m, 即式 (3) 当 = m 时也成立 定理由归纳法得证 证毕 定理 3 使用式 () 中的记号, 有 r n = (a, b) 证明由第三节定理, 从式 () 可见 r n = (r n, r n ) = (r n, r n ) = = (r, r ) = (b, r ) = (a, b) 证毕 现在我们已经知道, 利用辗转相除法可以求出整数 x,y, 使得 ax by = (a, b) (4) 为此所需要的除法次数是 O(log 0 b) 但是如果只需要计算 (a, b) 而不需要求出使式 (4) 成立的整数 x 与 y, 则所需要的除法次数还可更少一些 例 设 a 和 b 是正整数, 那么只使用被 除的除法运算和减法运算就可以计算出 (a, b) 36

37 解下面的四个基本事实给出了证明 : (ⅰ) 若 ab, 则 (a, b) = a; (ⅱ) 若 a = a, a, b b, b,, 则 (a, b) = ( a, b ); (ⅲ) 若 a, b b, b, 则 (a, b) = (a, b ); ( ⅳ ) 若 a b a, b, 则 ( a, b) (, b) 在实际计算过程中, 若再灵活运用最大公约数的性质 ( 例如第三节定理 4 的推论 ), 则可使得求最大公约数的过程更为简单 例 用辗转相除法求 (5, 7), 以及 x,y, 使得 5x 7y = (5, 7) 解做辗转相除法 : 5 = 77 6,q = 7,r = 6, 7 = 6 5,q =,r = 5, 6 = 5,q 3 =,r 3 =, 5 = 5, q 4 = 5 由定理 4,(5, 7) = r 3 = 利用定理 计算 (n = 3) P 0 =,P = 7,P = 7 = 5,P 3 = 5 7 =, Q 0 = 0,Q =,Q = 0 =,Q 3 = = 3, 37

38 取 x = () 3 Q 3 = 3,y = () 3 P 3 =, 则 53 7() = (5, 7) = 例 3 求 (345, 678) 解 (345, 678) = (345, 339) = (006, 339) = (6003, 339) = (5664, 339) = (77, 339) = (77, 6) = (77, 8) = (96, 8) = (3, 8) = 3 例 4 在 m 个盒子中放若干个硬币, 然后以下述方式往这些盒子里继续放硬币 : 每一次在 n (n < m) 个盒子中各放一个硬币 证明 : 若 (m, n) =, 那么无论开始时每个盒子中有多少硬币, 经过若干次放硬币后, 总可使所有盒子含有同样数量的硬币 解由于 (m, n) =, 所以存在整数 x,y, 使得 mx ny = 因此对于任意的自然数, 有 m(x n) = n(m y), 这样, 当 充分大时, 总可找出正整数 x 0,y 0, 使得 mx 0 = ny 0 上式说明, 如果放 y 0 次 ( 每次放 n 个 ), 那么在使 m 个盒子中各放 x 0 个后, 还多出一个硬币 把这个硬币放入含硬币最少的盒子中 ( 这是可以做到的 ), 就使它与含有最多硬币的盒子所含硬币数量之差减少 因此经过若干次放硬币后, 必可使所有盒子中的硬币数目相同 38

39 习题五. 说明例 证明中所用到的四个事实的依据. 用辗转相除法求整数 x,y, 使得 387x 6y = (387, 6) 3. 计算 :(7090, 67, 35) 4. 使用引理 中的记号, 证明 :(F n +, F n ) = 5. 若四个整数 836,458,564,65 被同一个大于 的整数除所得的余数相同, 且不等于零, 求除数和余数各是多少? 6. 记 M n = n, 证明 : 对于正整数 a,b, 有 (M a, M b ) = M (a, b) 第六节算术基本定理 在本节中, 我们要介绍整数与素数的一个重要关系, 即任何大于 的正整数都可以表示成素数的乘积 引理 任何大于 的正整数 n 可以写成素数之积, 即 n = m, () 其中 ( m) 是素数 证明当 n = 时, 结论显然成立 假设对于 n, 式 () 成立, 我们来证明 39

40 式 () 对于 n = 也成立, 从而由归纳法推出式 () 对任何大于 的整数 n 成立 如果 是素数, 式 () 显然成立 如果 是合数, 则存在素数 与整数 d, 使得 = d 由于 d, 由归纳假定知存 在素数 q, q,, q l, 使得 d = q q q l, 从而 = q q q l 证毕 定理 ( 算术基本定理 ) 任何大于 的整数 n 可以唯一地表示成 n =, () 其中,,, 是素数, < < <,,,, 是正整数 证明由引理, 任何大于 的整数 n 可以表示成式 () 的形式, 因此, 只需证明表示式 () 的唯一性 假设 ( ) 与 q j ( j l) 都是素数,,q q q l, 并且 (3) n = = q q q l, (4) 则由第三节定理 4 推论, 必有某个 q j ( j l), 40

41 使得 q j, 所以 = q j ; 又有某个 ( ), 使得 q, 所以 q = 于是, 由式 (3) 可知 = q, 从而由式 (4) 得到 = q q l 重复上述这一过程, 得到 = l, = q, 证毕 定义 使用定理 中的记号, 称 n = 是 n 的标准分解式, 其中 ( ) 是素数, < < <, ( ) 是正整数 推论 使用式 () 中的记号, 有 (ⅰ) n 的正因数 d 必有形式 d =, Z,0, ; (ⅱ) n 的正倍数 m 必有形式 m = M,MN, N,, 证明留作习题 推论 设正整数 a 与 b 的标准分解式是 a, r, l q ql b r s s 其中 ( ), q ( l) 与 r ( s) 是两两不相同的素数,, ( ), ( l) 与 ( s) 都是非负整数, 则 4

42 4 (a, b) =, = mn{, },, [a, b] = s l s l r r q q, = max{, }, 证明留作习题 为了方便, 推论 常叙述为下面的形式 : 推论 设正整数 a 与 b 的标准分解式是 b a,, 其中,,, 是互不相同的素数,, ( ) 都是非负整数, 则,,,,, b a b a }, max{ ], [ }, mn{ ), ( 推论 3 设 a,b,c,n 是正整数, ab = c n,(a, b) =, (5) 则存在正整数 u,v, 使得 a = u n,b = v n,c = uv,(u, v) = 证明设 c =, 其中,,, 是互不相同的素数, ( ) 是正整数 又设 b a,, 其中 I, ( ) 都是非负整数 由式 (5) 及推论 可知 mn{, } = 0, = n,,

43 43 因此, 对于每个 ( ), 等式 = n, = 0 与 = 0, = n 有且只有一个成立 这就证明了推论 证毕 例 写出 5480 的标准分解式 解我们有 5480 = 5740 = 870 = = = = = 例 设 a,b,c 是整数, 证明 : (ⅰ) (a, b)[a, b] = ab; (ⅱ) (a, [b, c]) = [(a, b), (a, c)] 解为了叙述方便, 不妨假定 a,b,c 是正整数 (ⅰ) 设 b a,, 其中,,, 是互不相同的素数,, ( ) 都是非负整数 由定理 推论, 有,,,,, b a b a }, max{ ], [ }, mn{ ), ( 由此知 (a, b)[a, b] = }, max{ }, mn{ =a

44 (ⅱ) 设 b; a, b, c, 其中,,, 是互不相同的素数,,, ( ) 都是非负整数 由定理 推论, 有 ( a,[ b, c]), [( a, b),( a, c)], 其中, 对于, 有 = mn{, max{, }}, = max{mn{, }, mn{, }}, 不妨设, 则 mn{, } mn{, }, 所以 = mn{, } =, 即 (a, [b, c]) = [(a, b), (a, c)] 注 : 利用定理 可以容易地处理许多像例 这样的问题 例 3 证明 : N (n 3 5 n ) 不是整数 解设 3 n < 3 + 对于任意的 n, 3, 记 = 3 Q,Q Z, 44

45 由第一节例 5, 知 因为 3 Q Q Q n 是整数, 所以, 如果 N 是整数, 则存在整数 Q, 使得 3 Q Q Q n N = Q 3 Q Q Q n 3 由于 3 Q Q Q n, 所以上式右端不是整数, 这个矛盾说明 N 不能是整数 习题六. 证明定理 的推论. 证明定理 的推论 3. 写出 的标准分解式 4. 证明 : 在,,, n 中任取 n 数, 其中至少有一个能被另一个整除 5. 证明 : (n ) 不是整数 n 6. 设 a,b 是正整数, 证明 : 存在 a,a, b,b, 使得 a = a a,b = b b,(a, b ) =, 并且 [a, b] = a b 45

46 46 第七节函数 [x] 与 {x} 本节中要介绍函数 [x], 它在许多数学问题中有广泛的应用 定义 设 x 是实数, 以 [x] 表示不超过 x 的最大整数, 称它为 x 的整数部分, 又称 {x} = x [x] 为 x 的小数部分 定理 设 x 与 y 是实数, 则 (ⅰ) x y [x] [y]; (ⅱ) 若 m 是整数, 则 [m x] = m [x]; (ⅲ) 若 0 x <, 则 [x] = 0; ( ⅳ ) [x y] = } { } { ] [ ] [ } { } { ] [ ] [ y x y x y x y x 若若 ; (ⅴ) [x] = Z Z x x x x 若若 ] [ ] [ ; (ⅵ) {x} = Z Z x x x 若若 } { 0 证明留作习题 定理 设 a 与 b 是正整数, 则在,,, a 中能被 b 整除的整数有 ] [ b a 个 证明能被 b 整除的正整数是 b, b, 3b,,

47 因此, 若数,,, a 中能被 b 整除的整数有 个, 则 a a b a < ( )b < = [b] b 证毕 由定理 我们看到, 若 b 是正整数, 那么对于任意的整数 a, 有 a a a b[ ] b{ }, b b 即在带余数除法 a = bq r,0 r < b a a 中有 q [ ], r b{ } b b 定理 3 设 n 是正整数,n! = n! 的标准分解式, 则 = r [ n r ] 是 () 证明对于任意固定的素数, 以 () 表示在 的标准分解式中的 的指数, 则 (n!) = () () (n) 以 n j 表示 (), (),, (n) 中等于 j 的个数, 那 么 (n!) = n n 3n 3, () 47

48 显然,n j 就是在,,, n 中满足 j a 并且 j + a 的整数 a 的个数, 所以, 由定理 有 n n n j = [ ] [ ] j j 将上式代入式 (), 得到 n n n n ( n!) ([ ] [ ]) ([ ] [ ]) 3 3 r [ n r ] ([ n 3 ] [ n 4 ]) 即式 () 成立 证毕 其中 n 推论设 n 是正整数, 则 n! = n [ ] r r n, 表示对不超过 n 的所有素数 求积 定理 4 设 n 是正整数, n, 则 C n n! N (3)!( n )! 若 n 是素数, 则 n C, n n 证明由定理 3, 对于任意的素数, 整数 n!,! 与 (n )! 的标准分解式中所含的 的指数 48

49 分别是 [ r n r ] 利用定理 可知 n [ r n r n, [ ] 与 [ ] r r ] 因此 C 是整数 r [ r r ] r [ r n 若 n 是素数, 则对于 n, 有 (n,!) =,(n, (n )!) = (n,!(n )!) =, 由此及 C n n ( n )! N,!( n )! 推出!(n )!(n )!, 从而 n C 证毕 例 求最大的正整数, 使得 0 99! 解由定理 3,99! 的标准分解式中所含的 5 的幂指数是 r n ], [ ] [ ] 5 5 [ ] 3 = 47, 所以, 所求的最大整数是 = 47 例 设 x 与 y 是实数, 则 [x] [y] [x] [x y] [y] (4) 解设 x = [x],0 <,y = [y],0 <, 则 49

50 [x] [x y] [y] = [x] [y] [ ], (5) [x] [y] = [x] [y] [] [] (6) 如果 [ ] = 0, 那么显然有 [ ] [] []; 如果 [ ] =, 那么 与 中至少有一个不 小于, 于是 [] [] = [ ] 因此无论 [ ] = 0 或, 都有 [ ] [] [], 由此及式 (5) 和式 (6) 可以推出式 (4) 例 3 设 n 是正整数, 则 [ n n ] [ 4n ] [ (7) 解首先, 我们有 n n ] n n n n( n ) n n 4n, 所以 [ n n ] [ 4n ] 若上式中的等号不成立, 即 [ n n ] [ 4n ], 则存在整数 a, 使得 (8) 50

51 [ n n ] a [ 4n ], 因此 n n( n ) a 4n, n n a n n, (n ) < (a n ) (n ), 所以 a n = n a = 4n (9) 但是, 无论 a 或 a, 式 (9) 都不能成立, 这 个矛盾说明式 (8) 不能成立, 即式 (7) 成立 例 4 设 x 是正数,n 是正整数, 则 n [ x] [ x ] [ x ] [ x ] = [nx] n n n 解设 x = [x],,0 n n n, 则 n [ x] [ x ] [ x ] [ x ] n n n = n[x] = n[x] [n] = [n([x] )] = [nx] 99 例 5 求 [ ( 3 ) ] 的个位数 解由 ( 3 ) 5 6 得 99 ( 3 ) ( 3 ) 99 5

52 996 = ( 5 6) (5 6) = (5 C ) 996 = 0A = 0A = 0A (5 ) 498 (0) = 0B, 其中 A 和 B 都是整数 由于 0 < 5 6 <, 所 996 以, 由式 (0) 可知 [ ( 3 ) ] 的个位数是, 则由 注 : 一般地, 如果 A,BN,A > B, A B < ( A B) ( A B) ( A C A B ) 可以求出 [ ( A B) ] 例 6 设 x 和 y 是正无理数,, 证 x y 明 : 数列 [x], [x],, [x], 与 [y], [y],, [my], () 联合构成了整个正整数集合, 而且, 两个数列中的数互不相同 解显然 x >,y >, 并且 x y 因此, 5

53 在数列 () 中至多有一个数等于给定的正整数 n, 否则存在正整数 与 m, 使得 n = [x] = [my] 因为 x 与 y 都是无理数, 所以我们有 n < x < n,n < my < n, m m,, n x n n y n m m, n x y n n < m < n, 这是不可能的 下面证明, 对于任意给定的正整数 n, 总可找到某个正整数, 使得 n 等于 [x] 或者 [y] 假设不然, 则存在, qn, 使得 [x] < n < [( )x],[qy] < n < [(q )y] 于是 ( 因为 x 和 y 是无理数 ), x < n < n [( )x] < ( )x, qy < n < n [(q )y] < (q )y, q n x y q, n q < n < n < q, 这是不可能的 习题七. 证明定理 53

54 r. 求使 347! 被 35 整除的最大的 值 3. 设 n 是正整数,x 是实数, 证明 : [ n r r ] = n 4. 设 n 是正整数, 求方程 x [x ] = (x [x]) 在 [, n] 中的解的个数 5. 证明 : 方程 f(x) = [x] [x] [ x] [ 3 x] [ 4 x] [ 5 x] = 345 没有实数解 6. 证明 : 在 n! 的标准分解式中, 的指数 h = n, 其中 是 n 的二进制表示的位数码之和 第八节素数 在第六节中我们已经证明了 : 每个正整数可以表示成素数幂的乘积 这就引出了一个问题 : 素数是否有无穷多个? 如果有无穷多个, 那么, 作为无穷大量, 素数个数具有怎样的性状? 这是数论研究中的一个中心课题 本节要对这一问题作初步的研究 定义 对于正实数 x, 以 (x) 表示不超过 x 的素数个数 例如,(5) = 6,(0.4) = 4,(50) = 5 定理 素数有无限多个 54

55 证明我们给出三个证明方法 证法 Ⅰ 假设只有 个素数, 设它们是,,, 记 N = 由第一节定理 可知,N 有素因数, 我们要说明,, 从而得出矛盾 事实上, 若有某个,, 使得 =, 则由 N = 推出, 这是不可能的 因此在,,, 之外又有一个素数, 这与假设是矛盾的 所以素数不可能是有限个 证法 Ⅱ 我们证明整数 n,,,,, 是两两互素的, 从而由第六节引理 可知素数有无限多个 事实上, 若 m 和 n 是整数,m > n 0, 则 m ( ( ( m m mn Q( n )( )( )( ), m m m ) )( m ) ( ) n )( n ) 此处 Q 是整数 因此 55

56 m Q ( n ), 故 ( m, n ) (, n ) 证法 Ⅲ 假设只有有限个素数,,, 由第六节定理, 每个正整数可以写成 由于 n =,, ( ) 0 所以, 对于任何正整数 N, 有, 3 N ( ) ( ) ( ) 当 N 时, 上式左端是一个无穷大量, 右端是有限的, 这个矛盾说明素数不能是有限多个 证毕 注 : 形如 n (n = 0,,, ) 的数称 为 Fermat 数 Fermat 曾经猜测它们都是素数 这是错误的, 因为尽管 F 0,F,F,F 3,F 4 都是 5 素数,F 5 = 却是合数 注 : 将全体素数按大小顺序排列为 56

57 =, = 3, 3 = 5, 4,, n,, 那么由第一个证明方法可以看出 n + n,n 定理 对于 n, (ⅰ) (n) log n; (ⅱ) n n 证明 (ⅰ) 设 n 是大于 的正整数 由算术基本定理, 对于任意的整数, n, 都有整数 a 和 b, 使得 = a b, 其中整数 b 不能被任何大于 的整数的平方整除 现在, 我们来看使得 = a b, n () 即 a b n 成立的整数 a,b 有多少对 首先, 整数 a 的个数 n ; 其次, 由于 b n 并且不 含有平方因数, 所以, 整数 b 的因数只可能是不超过 n 的不同的素数的乘积, 因此, 整数 b 的个数 (n) 这样, 使得式 () 成立的整数 a 和 b 至多是 n (n) 对, 所以,n n (n), 即 (n) log n (ⅱ) 以 m 表示第 m 个素数, 在结论 (ⅰ) 中取 n = m, 我们得到 m log m, 由此即可 得到结论 (ⅱ) 证毕 57

58 注 : 定理 对于无穷大量 (x) 的下界估计是相当粗糙的 下面的定理是已经知道的 ( 由于其证明较繁, 故本书中不予证明 ) 定理 3( 素数定理 ) 我们有 x (x),( x), log x 此处 logx 是以 e 为底的 x 的对数 推论以 n 表示第 n 个素数, 则 n nlogn(n) 证明由定理 3, 当 n 时, 有 n n log n () 因此 nlog n n, logn loglog n log n, logn log n 由上式与式 () 得 n nlogn(n) 证毕 例 若 a >,a n 是素数, 则 a =, 并且 n 是素数 解若 a >, 则由 a n = (a )(a n a n ) 可知 a n 是合数 所以 a = 若 n 是合数, 则 n = xy,x >,y >, 于是由 xy = ( x )( x(y ) x(y ) ) 以及 x > 可知 n 是合数, 所以 n 是素数时,n 必是素数 注 : 若 n 是素数, 则称 n 是 Mersenne 58

59 数 例 形如 4n 3 的素数有无限多个 解若不然, 假设只有 个形如 4n 3 的素 数,,, 记 N = 4 由第六节引理, 正整数 N 可以写成若干个素数之积 我们指出, 这些素因数中至少有一个是 4n 3 形式 否则, 若它们都是 4n 的形式, 则 N 也是 4n 的形式, 这与 N 的定义矛盾 以 表示这个素因数, 则, 否则若有某个,, 使得 =, 则由 N 推 出, 这是不可能的 因此在,,, 之 外又存在一个形如 4n 3 的素数, 这与原假设矛盾, 所以形如 4n 3 的素数有无限多个 例 3 设 f(x) = a x a x a 0 是整 系数多项式, 那么, 存在无穷多个正整数 n, 使得 f(n) 是合数 解不妨假定 a > 0 于是 f(x) (x ), 因此, 存在正整数 N, 使得当 n > N 时, 有 f(n) > 取整数 x > N, 记 y = f(x) = a x a x a 0, 又设 r 是任意的正整数,n = ry x, 则 f(n) = f(ry x) = a (ry x) a (ry x) a 0 = yq f(x) = y(q ) 59

60 是合数 习题八. 证明 : 若 n 是素数, 则 n 是 的乘幂. 证明 : 若 n 是素数, 则 n 是素数 3. 证明 : 形如 6n 5 的素数有无限多个 4. 设 d 是正整数,6 d, 证明 : 在以 d 为 公差的等差数列中, 连续三项都是素数的情况最多发生一次 5. 证明 : 对于任意给定的正整数 n, 必存在连续的 n 个自然数, 使得它们都是合数 6. 证明 : 级数 n n 发散, 此处使用了定 理 注 中的记号 60