第一章 整数可除性

1、 第一章第一章 整数的可除性整数的可除性 初等数论初等数论美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 1.1 1.1 整数的除法整数的除法 带余除法定理带余除法定理 初等数论初等数论美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 定义定义1.1.1 设设a，b是整数，是整数，b 0，如果存在整数，如果存在整数c，使得使得a = bc成立，则称成立，则称a被被b

2、整除，整除，a是是b的倍数，的倍数，b是是a的约数（因数或除数），并且使用记号的约数（因数或除数），并且使用记号b a；如果不；如果不存在整数存在整数c使得使得a = bc成立，则称成立，则称a不被不被b整除，记为整除，记为b a。 显然每个非零整数显然每个非零整数a都有约数都有约数 1， a，称这四个，称这四个数为数为a的平凡约数，的平凡约数，a的另外的约数称为非平凡约数。的另外的约数称为非平凡约数。被被2整除的整数称为偶数，不被整除的整数称为偶数，不被2整除的整数称为奇整除的整数称为奇数。数。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦

3、意淡淡的笑容定理定理1.1.1 下面的结论成立：下面的结论成立：() a b ab；() a b，b c a c；() b ai，i = 1, 2, , k b a1x1 a2x2 akxk，此处，此处xi（i = 1, 2, , k）是任意的整数；）是任意的整数；() b a bc ac，此处，此处c是任意的非零整数；是任意的非零整数；() b a，a 0 |b| |a|；b a且且|a| 1，e2 1，使得，使得d1 = e1e2，因此，因此，e1和和e2也是也是a的正的非平凡约数。这与的正的非平凡约数。这与d1的最小性矛盾。所以的最小性矛盾。所以d1是素数。证毕。是素数。证毕。 美丽有两

4、种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 推论推论 任何大于任何大于1的合数的合数a必有一个不超过的素约数。必有一个不超过的素约数。 证明证明 使用定理使用定理2中的记号，有中的记号，有a = d1d2，其中，其中d1 1是最小的是最小的素约数，所以素约数，所以d12 a。证毕。证毕。 例例1.1.1 设设r是正奇数，证明：对任意的正整数是正奇数，证明：对任意的正整数n，有，有n 21r 2 r n r。 解解 对于任意的正整数对于任意的正整数a，b以及正奇数以及正奇数k，有，有ak bk = (a b)(ak 1 ak 2b ak

5、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 2 s，由上式知，由上式知n 2 2，因为，因为n 2 2，这是不可能的，所以这是不可能的，所以n 2s。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 例例1.1.3 以以d(n)表示表示n的正约数的个数，例如：的正约数的个数，例如：d(1) = 1，d(2) = 2，d(3) = 2，d(4

6、) = 3， 。问：。问：d(1) d(2) d(1997)是否为偶数？是否为偶数？ 解解 对于对于n的每个约数的每个约数d，都有，都有n = d ，因此，因此，n的正的正约数约数d与是成对地出现的。只有当与是成对地出现的。只有当d =，即，即n = d2时，时，d和才是同一个数。故当且仅当和才是同一个数。故当且仅当n是完全平方数时，是完全平方数时，d(n)是奇数。是奇数。因为因为442 1997 452，所以在，所以在d(1), d(2), , d(1997)中恰有中恰有44个奇数，故个奇数，故d(1) d(2) d(1997)是偶是偶数。数。 美丽有两种美丽有两种一是深刻又动人的方程一是深

7、刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 例例1.1.4 设整数设整数k 1，证明：，证明：() 若若2k n 2k 1，1 a n，a 2k，则，则2ka；() 若若3k 2n 1 3k + 1，1 b n，2b 1 3k，则则3k2b 1。 解解 () 若若2k|a，则存在整数则存在整数q，使得，使得a= q2k。显然。显然q只可能是只可能是0或或1。此时。此时a= 0或或2k ，这都是不可能的，这都是不可能的，所以所以2ka；() 若若 3k|2b-1，则存在整数，则存在整数q，使得，使得2b-1= q3k，显，显然然q只可能是只可能是0，1, 或或2。此时。此时2

8、b-1= 0，3k，或，这都，或，这都是不可能的，所以是不可能的，所以3k 2b 1。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 例例1.1.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

9、= 2, 3, 以及任意的以及任意的n N，n4 a是合数。是合数。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 例例1.1.8 设设a1, a2, , an是整数，且是整数，且a1 a2 an = 0，a1a2an = n，则则4 n。 解解 如果如果2n，则，则n, a1, a2, , an都是奇数。于是都是奇数。于是a1 a2 an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2 n，即在，即在a1, a2, , an中至少有一个偶数。如果只有一个偶数，中至少有一个偶数

10、。如果只有一个偶数，不妨设为不妨设为a1，那么，那么2ai（2 i n）。此时有等式）。此时有等式a2 an = a1，在上式中，左端是在上式中，左端是(n 1)个奇数之和，右端是偶数，这是不可个奇数之和，右端是偶数，这是不可能的，因此，在能的，因此，在a1, a2, , an中至少有两个偶数，即中至少有两个偶数，即4 n。 初等数论初等数论 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 例例1.1.9 若若n是奇数，则是奇数，则8 n2 1。 解解 设设n = 2k 1，则，则 n2 1= (2k 1)2 1 = 4k(k 1)

11、。在在k和和k 1中有一个是偶数，所以中有一个是偶数，所以8 n2 1。 例例9的结论虽然简单，却是很有用的。例如，使用的结论虽然简单，却是很有用的。例如，使用例例3中的记号，我们可以提出下面的问题：中的记号，我们可以提出下面的问题： 问题问题 d(1)2 d(2)2 d(1997)2被被4除的余数是除的余数是多少？多少？ 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 下面，我们要介绍带余数除法及其简单应用。下面，我们要介绍带余数除法及其简单应用。 定理定理1.1.3(带余数除法带余数除法) 设设a与与b是两个整数，是两个整数，b

12、 0，则存在唯一的两，则存在唯一的两个整数个整数q和和r，使得，使得 a = bq r，0 r |b|。 (1) 证明证明 存在性存在性 若若b a，a = bq，q Z，可取，可取r = 0。若。若ba，考虑集合，考虑集合A = a kb；k Z ,其中其中Z表示所有整数的集合，以后，仍使用此记号，并以表示所有整数的集合，以后，仍使用此记号，并以N表示所有表示所有正整数的集合。正整数的集合。 在集合在集合A中有无限多个正整数，设最小的正整数是中有无限多个正整数，设最小的正整数是r = a k0b，则必，则必有有 0 r |b|，即，即a k0b |b|，a k0b |b| 0，这样，在集合，

13、这样，在集合A中，又有正整数中，又有正整数a k0b |b| r，这与，这与r的最小性矛盾。所以式的最小性矛盾。所以式(2)必定成立。取必定成立。取q = k0知式知式(1)成立。存在性成立。存在性得证。得证。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 唯一性唯一性 假设有两对整数假设有两对整数q ，r 与与q ，r 都使得式都使得式(1)成立，成立，即即a = q b r = q b r ，0 r , r |b|，则则(q q )b = r r ，|r r | |b|， (3)因此因此r r = 0，r = r ，再由式，再

14、由式(3)得出得出q = q ，唯一性得证。，唯一性得证。 证毕。证毕。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 定义定义1.1.3 称式称式(1)中的中的q是是a被被b除的商，除的商，r是是a被被b除的余数。除的余数。 由定理由定理1可知，对于给定的整数可知，对于给定的整数b，可以按照被，可以按照被b除除的余数将所有的整数分成的余数将所有的整数分成b类。在同一类中的数被类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。可以归化为对有

15、限个整数类的研究。 以后在本书中，除特别声明外，在谈到带余数除以后在本书中，除特别声明外，在谈到带余数除法时总是假定法时总是假定b是正整数。是正整数。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 例例1.1.14 设设a0, a1, , an Z，f(x) = anxn a1x a0 ，已知，已知f(0)与与f(1)都不是都不是3的倍数，证明：若方程的倍数，证明：若方程f(x) = 0有整数解，则有整数解，则3 f( 1) = a0 a1 a2 ( 1)nan 。 解解 对任何整数对任何整数x，都有，都有x = 3q r，r =

16、 0，1或或2，q Z。() 若若r = 0，即，即x = 3q，q Z，则，则f(x) = f(3q) = an(3q)n a1(3q) a0 = 3Q1 a0 = 3Q1 f(0)，其中其中Q1 Z，由于，由于f(0)不是不是3的倍数，所以的倍数，所以f(x) 0；() 若若r = 1，即，即x = 3q 1，q Z，则，则f(x) = f(3q 1) = an(3q 1)n a1(3q 1) a0= 3Q2 an a1 a0 = 3Q2 f(1)，其中其中Q2 Z。由于。由于f(1)不是不是3的倍数，所以的倍数，所以f(x) 0。因此若因此若f(x) = 0有整数解有整数解x，则必是，则

17、必是x = 3q 2 = 3q 1，q Z，于是，于是0 = f(x) = f(3q 1) = an(3q 1)n a1(3q 1) a0= 3Q3 a0 a1 a2 ( 1)nan = 3Q3 f( 1)，其中其中Q3 Z。所以。所以3 f( 1) = a0 a1 a2 ( 1)nan 。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 例例1.1.15 证明：对于任意的整数证明：对于任意的整数n，f(n) = 3n5 5n3 7n被被15整除。整除。 解解 对于任意的正整数对于任意的正整数n，记，记n = 15q r，0 r 0

18、是整数，是整数，p为素数）的形式。为素数）的形式。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 6. 证明：证明：12 n4 2n3 11n2 10n，n Z。 7. 设设3 a2 b2，证明：，证明：3 a且且3 b。 8. 设设n，k是正整数，证明：是正整数，证明：nk与与nk + 4的个位数的个位数字相同。字相同。 9. 证明：对于任何整数证明：对于任何整数n，m，等式，等式n2 (n 1)2 = m2 2不可能成立。不可能成立。 10. 设设a是自然数，问是自然数，问a4 3a2 9是素数还是合数？是素数还是合数？ 1.

19、2 1.2 最大公约数与最大公约数与 辗转相除法辗转相除法 初等数论初等数论美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 定义定义1.2.1 整数整数a1, a2, , ak的公共约数称为的公共约数称为a1, a2, , ak的的公约数。不全为零的整数公约数。不全为零的整数a1, a2, , ak的公约数中最大的一个的公约数中最大的一个叫做叫做a1, a2, , ak的最大公约数（或最大公因数），记为的最大公约数（或最大公

20、因数），记为(a1, a2, , ak)。 由于每个非零整数的约数的个数是有限的，所以最大公约数由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。是存在的，并且是正整数。 如果如果(a1, a2, , ak) = 1，则称，则称a1, a2, , ak是互素的（或互质是互素的（或互质的）；如果的）；如果(ai, a j) = 1，1 i, j k，i j，则称则称a1, a2, , ak是两两互素的（或两两互质的）。是两两互素的（或两两互质的）。 显然，显然，a1, a2, , ak两两互素可以推出两两互素可以推出(a1, a2, , ak) = 1，反，反之则不然，

21、例如之则不然，例如(2, 6, 15) = 1，但，但(2, 6) = 2。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 定理定理1.2.1 下面的等式成立：下面的等式成立：() (a1, a2, , ak) = (|a1|, |a2|, , |ak|)；() (a, 1) = 1，(a, 0) = |a|，(a, a) = |a|；() (a, b) = (b, a)；() 若若p是素数，是素数，a是整数，则是整数，则(p, a) = 1或或p a；() 若若a = bq r，则，则(a, b) = (b, r)。 证明证明

22、()()留作习题。留作习题。 () 由第一节定理由第一节定理1可知，如果可知，如果d a，d b，则有，则有d r = a bq，反之，若反之，若d b，d r，则，则d a = bq r。因此。因此a与与b的全体公约数的的全体公约数的集合就是集合就是b与与r的全体公约数的集合，这两个集合中的最大正数的全体公约数的集合，这两个集合中的最大正数当然相等，即当然相等，即(a, b) = (b, r)。证毕。证毕。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 定理定理1.2.2 设设a1, a2, , ak Z，记，记 A = y；y

23、 =，xi Z， i k 。如果如果y0是集合是集合A中最小的正数，则中最小的正数，则y0 = (a1, a2, , ak)。 证明证明 设设d是是a1, a2, , ak的一个公约数，则的一个公约数，则d y0，所以所以d y0。另一方面，由第二节例。另一方面，由第二节例2知，知，y0也是也是a1, a2, , ak的公约数。因此的公约数。因此y0是是a1, a2, , ak的公约数的公约数中的最大者，即中的最大者，即y0 = ( a1, a2, , ak)。证毕。证毕。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 定理定理1

24、.2.3 (a1, a2, , ak) = 1的充要条件是存在整的充要条件是存在整数数x1, x2, , xk，使得，使得 a1x1 a2x2 akxk = 1。 (1) 证明证明 必要性必要性 由定理由定理2得到。得到。充分性充分性 若式若式(1)成立，如果成立，如果 (a1, a2, , ak) = d 1，那么由那么由d ai（1 i k）推出）推出d a1x1 a2x2 akxk = 1，这是不可能的。所以有，这是不可能的。所以有(a1, a2, , ak) = 1。 证毕。证毕。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的

25、笑容 定理定理1.2.4 对于任意的整数对于任意的整数a，b，c，下面的结论成立：，下面的结论成立：() 由由b ac及及(a, b) = 1可以推出可以推出b c；() 由由b c，a c及及(a, b) = 1可以推出可以推出ab c。 证明证明 () 若若(a, b) = 1，由定理，由定理2，存在整数，存在整数x与与y，使得，使得ax by = 1。因此因此acx bcy = c。 (2)由上式及由上式及b ac得到得到b c。结论。结论()得证；得证；() 若若(a, b) = 1，则存在整数，则存在整数x，y使得式使得式(2)成立。由成立。由b c与与a c得到得到ab ac，ab

26、 bc，再由式，再由式(2)得到得到ab c。结论。结论()得证。证毕。得证。证毕。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 推论推论1.2.4 若若p是素数，则下述结论成立：是素数，则下述结论成立：() p ab p a或或p b；() p a2 p a。 证明证明 留作习题。留作习题。 推论推论1.2.5 若若 (a, b) = 1，则，则(a, bc) = (a, c)。 证明证明 设设d是是a与与bc的一个公约数，则的一个公约数，则d a，d bc，由式（，由式（2）得到，得到，d|c, 即即d是是a与与c的公约数。

27、另一方面，若的公约数。另一方面，若d是是a与与c的公约的公约数，则它也是数，则它也是a与与bc的公约数。因此，的公约数。因此，a与与c的公约数的集合，的公约数的集合，就是就是a与与bc的公约数的集合，所以的公约数的集合，所以(a, bc) = (a, c)。证毕。证毕。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 定理定理1.2.5 对于任意的对于任意的n个整数个整数a1, a2, , an，记，记(a1, a2) = d2，(d2, a3) = d3，(dn 2, an 1) = dn 1，(dn 1, an) = dn，则则

28、 dn = (a1, a2, , an)。 证明证明 由定理由定理2的推论，我们有的推论，我们有 dn = (dn 1, an) dn an，dn dn 1，dn 1 = (dn 2, an 1) dn 1 an 1，dn 1 dn 2， dn an，dn an 1，dn dn 2，dn 2 = (dn 3, an 2) dn 2 an 2，dn 2 dn 3 dn an，dn an 1，dn an 2，dn dn 3， d2 = (a1, a2) dn an，dn an 1，dn a2，dn a1，即即dn是是a1, a2, , an的一个公约数。的一个公约数。 美丽有两种美丽有两种一是深刻

29、又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 另一方面，对于另一方面，对于a1, a2, , an的任何公约数的任何公约数d，由定理，由定理2的推的推论及论及d2, , dn的定义，依次得出的定义，依次得出 d a1，d a2 d d2， d d2，d a3 d d3， d dn 1，d an d dn，因此因此dn是是a1, a2, , an的公约数中的最大者，即的公约数中的最大者，即dn = (a1, a2, , an)。 证毕。证毕。 美丽有两种美丽有两种一是深刻又动人的方程一是深刻又动人的方程一是你泛着倦意淡淡的笑容一是你泛着倦意淡淡的笑容 例例1.

30、2.1 1.2.1 证明：若证明：若n n是正整数，则是既约分数。是正整数，则是既约分数。 解解 由定理由定理1 1得到得到(21n (21n 4, 14n 4, 14n 3) = (7n 3) = (7n 1, 14n 1, 14n 3) = (7n 3) = (7n 1, 1) = 1 1, 1) = 1。注：一般地，若注：一般地，若(x, y) = 1(x, y) = 1，那么，对于任意的整数，那么，对于任意的整数a a，b b，有，有(x, y) = (x (x, y) = (x ay, y) = (x ay, y) = (x ay, y ay, y b(x b(x ay) = (x

31、ay) = (x ay, (ab ay, (ab 1)y 1)y bx) bx)，因此，是既约分数。因此，是既约分数。 例例1.2.2 1.2.2 证明：证明：121n2 121n2 2n 2n 12 12，n n Z Z。 解解 由于由于121 = 112121 = 112，n2 n2 2n 2n 12 = (n 12 = (n 1)2 1)2 11 11，所以，所以，若若112112 (n (n 1)2 1)2 11 11， (3)(3)则则1111 (n (n 1)2 1)2，因此，由定理，因此，由定理4 4的推论的推论1 1得到得到1111 n n 1 1，112112 (n (n 1)2 1)2。再由式再由式(3)(3)得到得到 112112 1111，这是不可能的。所以式这是