初等数论第一章整除理论

第一章 整除理论

整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。

第一节 数的整除性

定义1 设a，b是整数，b 0，如果存在整数c，使得

a = bc

成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号ba；如果不存在整数c使得a = bc成立，则称a不被b整除，记为b?|a。

显然每个非零整数a都有约数 1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

被2整除的整数称为偶数，不被2整除的整数称为奇数。

定理1 下面的结论成立： (ⅰ) ab ab； (ⅱ) ab，bc ac； (ⅲ) bai，i = 1, 2, , k ba1x1 a2x2 akxk，此处x（, k）是任意的整ii = 1, 2,

数；

(ⅳ) ba bcac，此处c是任意的非零整数；

(ⅴ) ba，a 0 |b| |a|；ba且|a| < |b| a = 0。

证明 留作习题。

定义2 若整数a 0，1，并且只有约数 1和 a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。

定理2 任何大于1的整数a都至少有一个素约数。

证明 若a是素数，则定理是显然的。 若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, , dk 。不妨设d1是其中最小的。若d1不是素数，则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。

推论 任何大于1的合数a必有一个不超过a的素约数。

证明 使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12 a。证毕。

例1 设r是正奇数，证明：对任意的正整数n，有

n

|1r 2? 2 r n r。

解 对于任意的正整数a，b以及正奇数k，有

ak bk = (a b)(ak 1 ak 2b ak 3b2

bk 1) = (a b)q，

其中q是整数。记s = 1r 2 r n r，则 2s = 2 (2 r n r) (3 r (n 1)r) (n r

2 r) = 2 (n 2)Q，

其中Q是整数。若n 2s，由上式知n 22，因为n 2 > 2，这是不可能的，所以n 2? |s。例2 设A = { d1, d2, 的集合，则

B ={, dk }是n的所有约数

nnn,,?,} d1d2dk也是n的所有约数的集合。

解 由以下三点理由可以证得结论： (ⅰ) A和B的元素个数相同；

(ⅱ) 若diA，即din，则然；

(ⅲ) 若di

dj，则

nn?。 didjn|n，反之亦di例3 以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2) = 2，d(3) = 2，d(4) = 3， 。问：

d(1) d(2) d(1997)

是否为偶数

解 对于n的每个约数d，都有n = d因此，n的正约数d与

n，dn是成对地出现的。只有dnn当d =，即n = d2时，d和才是同一个数。

dd故当且仅当n是完全平方数时，d(n)是奇数。

因为442 < 1997 < 452，所以在d(1), d(2), , d(1997)中恰有44个奇数，故d(1) d(2) d(1997)是偶数。

例4 设凸2n边形M的顶点是A1, A2, , A2n，点O在M的内部，用1, 2, , 2n将M的2n条边分别编号，又将OA1, OA2, , OA2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2, OA2A3, , OA2nA1的周长都相等。

解 假设这些三角形的周长都相等，记为s。则

2ns = 3(1 2 2n) = 3n(2n 1)， 即

2s = 3(2n 1)，

因此23(2n 1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。

例5 设整数k 1，证明： (ⅰ) 若2k n < 2k 1，1 a n，a 2k，

|a； 则2k?(ⅱ) 若3k

2n

1 < 3k + 1，1 1。

b

n，

|2b 2b 1 3k，则3k? 解 (ⅰ) 若2k|a，则存在整数q，使得a= q2k。显然q只可能是0或1。此时a= 0或2k ，这都是不可能的，所以2k?|a；

(ⅱ) 若 3k|2b-1，则存在整数q，使得2b-1= q3k，显然q只可能是0，1, 或2。此时2b-1= 0，3k，或2?3，这都是不可能的，所以3k? |2b 1。例6 写出不超过100的所有的素数。

解 将不超过100的正整数排列如下：

1 2 3 4 5 6 7

8 9 10 11 12 13 14 15 16 17

18 19 20 21 22 23 24 25 26 27

28 29 30 31 32 33 34 35 36 37

38 39 40 41 42 43 44 45 46 47

48 49 50 51 52 53 54 55 56 57

58 59 60 61 62 63 64 65 66 67

68 69 70 71 72 73 74 75 76 77

78 79 80 81 82 83 84 85 86 87

88 89 90 91 92 93 94 95 96 97

k