第一章整除理论整除性理论是初等数论的基础。
本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。
第一节数的整除性定义1设a，b是整数，b≠ 0，如果存在整数c，使得a = bc成立，则称a被b整除，a是b的倍数，b是a 的约数（因数或除数），并且使用记号b∣a；如果不存在整数c使得a = bc成立，则称a不被b整除，记为b|/a。
显然每个非零整数a都有约数±1，±a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。
被2整除的整数称为偶数，不被2整除的整数称为奇数。
定理1下面的结论成立：(ⅰ) a∣b⇔±a∣±b；(ⅱ) a∣b，b∣c⇒a∣c；(ⅲ) b∣a i，i = 1, 2, , k⇒b∣a1x1+ a2x2+ +a k x k，此处x i（i = 1, 2, , k）是任意的整数；(ⅳ) b∣a ⇒bc∣ac，此处c是任意的非零整数；(ⅴ) b∣a，a≠ 0 ⇒ |b| ≤ |a|；b∣a 且|a| < |b| ⇒a = 0。
证明留作习题。
定义2若整数a≠0，±1，并且只有约数±1和±a，则称a是素数（或质数）；否则称a为合数。
以后在本书中若无特别说明，素数总是指正素数。
定理2任何大于1的整数a都至少有一个素约数。
证明若a是素数，则定理是显然的。
若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, , d k 。
不妨设d1是其中最小的。
若d1不是素数，则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。
这与d1的最小性矛盾。
所以d1是素数。
证毕。
推论任何大于1的合数a必有一个不超过证明使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12≤a。
证毕。
例1设r是正奇数，证明：对任意的正整数n，有n+ 2|/1r+ 2r+ +n r。
解 对于任意的正整数a ，b 以及正奇数k ，有a k +b k = (a + b )(a k - 1 - a k - 2b + a k - 3b 2 -+ b k - 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 + 2∣s ，由上式知n + 2∣2，因为n + 2 > 2，这是不可能的，所以n + 2|/s 。
例2 设A = { d 1, d 2, , d k }是n 的所有约数的集合，则B =}{,,,21kd n d n d n Λ 也是n 的所有约数的集合。
解 由以下三点理由可以证得结论：(ⅰ) A 和B 的元素个数相同；(ⅱ) 若d i ∈A ，即d i ∣n ，则|i d n n ，反之亦然；(ⅲ) 若d i ≠ d j ，则ji d n d n ≠。
例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 ⋅d n ，因此，n 的正约数d 与dn 是成对地出现的。
只有当d =d n ，即n = d 2时，d 和dn 才是同一个数。
故当且仅当n 是完全平方数时，d (n )是奇数。
因为442 < 1997 < 452，所以在d (1), d (2),, d (1997)中恰有44个奇数，故d (1) + d (2) ++ d (1997)是偶数。
例4 设凸2n 边形M 的顶点是A 1, A 2, , A 2n ，点O 在M 的内部，用1, 2, , 2n 将M 的2n 条边分别编号，又将OA 1, OA 2, , OA 2n 也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA 1A 2,OA 2A 3, , OA 2n A 1的周长都相等。
解 假设这些三角形的周长都相等，记为s 。
则2ns = 3(1 + 2 + + 2n ) = 3n (2n + 1)，即2s = 3(2n + 1)，因此2∣3(2n + 1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。
例5 设整数k ≥ 1，证明：(ⅰ) 若2k ≤ n < 2k + 1，1 ≤ a ≤ n ，a ≠ 2k ，则2k|/a ； (ⅱ) 若3k ≤ 2n - 1 < 3k + 1，1 ≤ b ≤ n ，2b - 1 ≠ 3k ，则3k |/2b - 1。
解(ⅰ) 若2k|a，则存在整数q，使得a=q2k。
显然q只可能是0或1。
此时a= 0或2k，这都是不可能的，所以2k|/a；(ⅱ) 若 3k|2b-1，则存在整数q，使得2b-1=q3k，显然q只可能是0，1, 或2。
此时2⋅，这都是不可能的，所以2b-1= 0，3k，或k33k|/2b- 1。
例6写出不超过100的所有的素数。
解将不超过100的正整数排列如下：1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 8788 89 9091 92 93 94 95 96 97 98 99 100按以下步骤进行：(ⅰ) 删去1，剩下的后面的第一个数是2，2是素数；(ⅱ) 删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；(ⅲ) 再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；(ⅳ) 再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数；照以上步骤可以依次得到素数2, 3, 5, 7, 11, 。
由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。
在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。
它可以用来求出不超过任何固定整数的所有素数。
在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。
例7证明：存在无穷多个正整数a，使得n4+a（n = 1, 2, 3, ）都是合数。
解取a = 4k4，对于任意的n∈N，有n4+ 4k4 = (n2+ 2k2)2- 4n2k2 = (n2+ 2k2+ 2nk)(n2+ 2k2- 2nk)。
因为n2+ 2k2- 2nk = (n-k)2+k2≥k2，所以，对于任意的k= 2, 3, 以及任意的n∈N，n4+a是合数。
例8设a1, a2, , a n是整数，且a1+a2+ +a n = 0，a1a2 a n = n，则4∣n。
解如果2|/n，则n, a1, a2, , a n都是奇数。
于是a1+a2+ +a n是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2∣n，即在a1, a2, , a n中至少有一个偶数。
如果只有一个偶数，不妨设为a1，那么2|/a i（2 ≤i≤n）。
此时有等式a2+ +a n = -a1，在上式中，左端是(n- 1)个奇数之和，右端是偶数，这是不可能的，因此，在a1, a2, , a n中至少有两个偶数，即4∣n。
例9若n是奇数，则8∣n2- 1。
解设n = 2k+ 1，则n2- 1= (2k+ 1)2- 1 = 4k(k+ 1)。
在k和k+1中有一个是偶数，所以8∣n2-1。
例9的结论虽然简单，却是很有用的。
例如，使用例3中的记号，我们可以提出下面的问题：问题d(1)2+d(2)2+ +d(1997)2被4除的余数是多少？例10证明：方程a12+a22+a32 = 1999(1) 无整数解。
解若a1，a2，a3都是奇数，则存在整数A1，A2，A3，使得a12 = 8A1+ 1，a22 = 8A2+ 1，a32 = 8A3+ 1，于是a12+a22+a32 = 8(A1+A2+A3) + 3。
由于1999被8除的余数是7，所以a1，a2，a3不可能都是奇数。
由式(1)，a1，a2，a3中只能有一个奇数，设a1为奇数，a2，a3为偶数，则存在整数A1，A2，A3，使得a12 = 8A1+ 1，a22 = 8A2+r，a32 = 8A3+s，于是a12+a22+a32 = 8(A1+A2+A3) + 1 +r+s，其中r和s是整数，而且只能取值0或4。
这样a12+a22+a32被8除的余数只可能是1或5，但1999被8除的余数是7，所以这样的a1，a2，a3也不能使式(2)成立。
综上证得所需要的结论。
习题一1. 证明定理1。
2. 证明：若m-p∣mn+pq，则m-p∣mq +np。
3.证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。
4. 设p是n的最小素约数，n= pn1，n1> 1，证明：若p >3n，则n1是素数。
5. 证明：存在无穷多个自然数n，使得n 不能表示为a2+p（a > 0是整数，p为素数）的形式。
第二节带余数除法在本节中，我们要介绍带余数除法及其简单应用。
定理1(带余数除法) 设a与b是两个整数，b≠ 0，则存在唯一的两个整数q和r，使得a = bq+r，0 ≤r < |b|。
(1)证明存在性若b∣a，a = bq，q∈Z，可取r = 0。
若b|/a，考虑集合A = { a +kb；k∈Z },其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的集合。
在集合A中有无限多个正整数，设最小的正整数是r = a +k0b，则必有0 < r < |b|， (2) 否则就有r ≥ |b|。
因为b|/a，所以r≠ |b|。
于是r > |b|，即a +k0b > |b|，a +k0b- |b| > 0，这样，在集合A中，又有正整数a +k0b-|b| < r，这与r的最小性矛盾。
所以式(2)必定成立。
取q = - k0知式(1)成立。