初等数论 第一章整除理论(59页).doc

《初等数论 第一章整除理论(59页).doc》由会员分享，可在线阅读，更多相关《初等数论 第一章整除理论(59页).doc（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、，bc ac；() bai，i = 1, 2, L, k ba1x1 + a2x2 + L + akxk，此处xi（i = 1, 2, L, k）是任意的整数；() ba bcac，此处c是任意的非零整数；() ba，a 0 |b| |a|；ba且|a| 1，e2 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。推论 任何大于1的合数a必有一个不超过的素约数。证明 使用定理2中的记号，有a = d1d2，其中d1 1是最小的素约数，所以d12 a。证毕。例1 设r是正奇数，证明：对任意的正整数n，有n + 21r + 2 r +

3、L + n r。解 对于任意的正整数a，b以及正奇数k，有ak + bk = (a + b)(ak - 1 - ak - 2b + ak - 3b2 - L + bk - 1) = (a + b)q，其中q是整数。记s = 1r + 2 r + L + n r，则2s = 2 + (2 r + n r) + (3 r + (n - 1)r) + L + (n r + 2 r) = 2 + (n + 2)Q，其中Q是整数。若n + 2s，由上式知n + 22，因为n + 2 2，这是不可能的，所以n + 2s。例2 设A = d1, d2, L, dk 是n的所有约数的集合，则B =也是n的所有

4、约数的集合。解 由以下三点理由可以证得结论：() A和B的元素个数相同；() 若diA，即din，则n，反之亦然；() 若di dj，则。例3 以d(n)表示n的正约数的个数，例如：d(1) = 1，d(2) = 2，d(3) = 2，d(4) = 3，L 。问：d(1) + d(2) + L + d(1997)是否为偶数？解 对于n的每个约数d，都有n = d，因此，n的正约数d与是成对地出现的。只有当d =，即n = d2时，d和才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。因为442 1997 452，所以在d(1), d(2), L, d(1997)中恰有44个奇数，故d(

5、1) + d(2) + L + d(1997)是偶数。例4 设凸2n边形M的顶点是A1, A2, L, A2n，点O在M的内部，用1, 2, L, 2n将M的2n条边分别编号，又将OA1, OA2, L, OA2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2, OA2A3, L, OA2nA1的周长都相等。解 假设这些三角形的周长都相等，记为s。则2ns = 3(1 + 2 + L + 2n) = 3n(2n + 1)，即2s = 3(2n + 1)，因此23(2n + 1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。例5 设

6、整数k 1，证明：() 若2k n 2k + 1，1 a n，a 2k，则2ka；() 若3k 2n - 1 1，证明：若p ，则n1是素数。5. 证明：存在无穷多个自然数n，使得n不能表示为a2 + p（a 0是整数，p为素数）的形式。第二节 带余数除法在本节中，我们要介绍带余数除法及其简单应用。定理1(带余数除法) 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得a = bq + r，0 r |b|。 (1)证明 存在性 若ba，a = bq，qZ，可取r = 0。若ba，考虑集合A = a + kb；kZ ,其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的

7、集合。 在集合A中有无限多个正整数，设最小的正整数是r = a + k0b，则必有0 r |b|，即a + k0b |b|，a + k0b - |b| 0，这样，在集合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 ，再由式(3)得出q = q ，唯一性得证。证毕。

8、定义1 称式(1)中的q是a被b除的商，r是a被b除的余数。由定理1可知，对于给定的整数b，可以按照被b除的余数将所有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。以后在本书中，除特别声明外，在谈到带余数除法时总是假定b是正整数。例1 设a，b，x，y是整数，k和m是正整数，并且a = a1m + r1，0 r1 m，b = b1m + r2，0 r2 m，则ax + by和ab被m除的余数分别与r1x + r2y和r1r2被m除的余数相同。特别地，ak与r1k被m除的余数相同。解 由ax + by = (a1m + r1)x +

9、 (b1m + r2)y = (a1x + b1y)m + r1x + r2y可知，若r1x + r2y被m除的余数是r，即r1x + r2y = qm + r，0 r m，则ax + by = (a1x + b1y + q)m + r，0 r m，即ax + by被m除的余数也是r。同样方法可以证明其余结论。例2 设a1, a2, L, an为不全为零的整数，以y0表示集合A = y；y = a1x1 + L + anxn，xiZ，1 i n 中的最小正数，则对于任何yA，y0y；特别地，y0ai，1 i n。解 设y0 = a1x1 + L + anxn，对任意的y = a1x1 + L

10、+ anxnA，由定理1，存在q, r0Z，使得y = qy0 + r0，0 r0 y0 。因此r0 = y - qy0 = a1(x1 - qx1) + L + an(xn - qxn)A。如果r0 0，那么，因为0 r0 y0，所以r0是A中比y0还小的正数，这与y0的定义矛盾。所以r0 = 0，即y0y。显然aiA（1 i n），所以y0整除每个ai（1 i n）。例3 任意给出的五个整数中，必有三个数之和被3整除。解 设这五个数是ai，i = 1, 2, 3, 4, 5，记ai = 3qi + ri，0 ri 3，i = 1, 2, 3, 4, 5。分别考虑以下两种情形：() 若在r1

11、, r2, L, r5中数0，1，2都出现，不妨设r1 = 0，r2 = 1，r3 = 2，此时a1 + a2 + a3 = 3(q1 + q2 + q3) + 3可以被3整除；() 若在r1, r2, L, r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1 = r2 = r3 = r（r = 0，1或2），此时a1 + a2 + a3 = 3(q1 + q2 + q3) + 3r可以被3整除。例4 设a0, a1, L, anZ，f(x) = anxn + L + a1x + a0 ，已知f(0)与f(1)都不是3的倍数，证明：若方程f(x) = 0有整数解，则

12、3f(-1) = a0 - a1 + a2 - L + (-1)nan 。解 对任何整数x，都有x = 3q + r，r = 0，1或2，qZ。() 若r = 0，即x = 3q，qZ，则f(x) = f(3q) = an(3q)n + L + a1(3q) + a0 = 3Q1 + a0 = 3Q1 + f(0)，其中Q1Z，由于f(0)不是3的倍数，所以f(x) 0；() 若r = 1，即x = 3q + 1，qZ，则f(x) = f(3q + 1) = an(3q + 1)n + L + a1(3q + 1) + a0= 3Q2 + an + L + a1 + a0 = 3Q2 + f(

13、1)，其中Q2Z。由于f(1)不是3的倍数，所以f(x) 0。因此若f(x) = 0有整数解x，则必是x = 3q + 2 = 3q - 1，q Z，于是0 = f(x) = f(3q - 1) = an(3q - 1)n + L + a1(3q - 1) + a0= 3Q3 + a0 - a1 + a2 - L + (- 1)nan = 3Q3 + f(-1)，其中Q3Z。所以3f(-1) = a0 - a1 + a2 - L + (-1)nan 。例5 证明：对于任意的整数n，f(n) = 3n5 + 5n3 + 7n被15整除。解 对于任意的正整数n，记n = 15q + r，0 r 1

14、5。由例1，n2 = 15Q1 + r1，n4 = 15Q2 + r2，其中r1与r2分别是r2与r4被15除的余数。以R表示3n4 + 5n2 + 7被15除的余数，则R就是3r2 + 5r1 + 7被15除的余数，而且f(n)被15除的余数就是rR被15除的余数，记为R 。当r = 0时，显然R = 0，即153n5 + 5n3 + 7n。对于r = 1, 2, 3, L, 14的情形，通过计算列出下表： r = 1, 14 2, 13 3, 12 4, 11 5, 10 6, 9 7, 8r1 = 1 4 9 1 10 6 4r2 = 1 1 6 1 10 6 1R = 0 0 10 0

15、 12 10 0R= 0 0 0 0 0 0 0这证明了结论。例6 设n是奇数，则16n4 + 4n2 + 11。解 我们有n4 + 4n2 + 11 = (n2 - 1)(n2 + 5) + 16。由第一节例题9，有8n2 - 1，由此及2n2 + 5得到16(n2 - 1)(n2 + 5)。例7 证明：若a被9除的余数是3，4，5或6，则方程x3 + y3 = a没有整数解。解 对任意的整数x，y，记x = 3q1 + r1，y = 3q2 + r2，0 r1, r2 1，那么由dai（1 i k）推出da1x1 + a2x2 + L + akxk = 1，这是不可能的。所以有(a1, a

16、2, L, ak) = 1。证毕。定理4 对于任意的整数a，b，c，下面的结论成立：() 由bac及(a, b) = 1可以推出bc；() 由bc，ac及(a, b) = 1可以推出abc。证明 () 若(a, b) = 1，由定理2，存在整数x与y，使得ax + by = 1。因此acx + bcy = c。 (2)由上式及bac得到bc。结论()得证；() 若(a, b) = 1，则存在整数x，y使得式(2)成立。由bc与ac得到abac，abbc，再由式(2)得到abc。结论()得证。证毕。推论1 若p是素数，则下述结论成立：() pab pa或pb；() pa2 pa。证明 留作习题。

17、推论2 若 (a, b) = 1，则(a, bc) = (a, c)。证明 设d是a与bc的一个公约数，则da，dbc，由式（2）得到，d|c, 即d是a与c的公约数。另一方面，若d是a与c的公约数，则它也是a与bc的公约数。因此，a与c的公约数的集合，就是a与bc的公约数的集合，所以(a, bc) = (a, c)。证毕。推论3 若 (a, bi) = 1，1 i n，则(a, b1b2Lbn) = 1。证明 留作习题。定理5 对于任意的n个整数a1, a2, L, an，记(a1, a2) = d2，(d2, a3) = d3，L，(dn - 2, an - 1) = dn - 1，(dn

18、 - 1, an) = dn，则dn = (a1, a2, L, an)。证明 由定理2的推论，我们有 dn = (dn - 1, an) dnan，dndn - 1，dn - 1 = (dn - 2, an - 1) dn - 1an - 1，dn - 1dn - 2， dnan，dnan - 1，dndn - 2，dn - 2 = (dn - 3, an - 2) dn - 2an - 2，dn - 2dn - 3 dnan，dnan - 1，dnan - 2，dndn - 3， d2 = (a1, a2) dnan，dnan - 1，L，dna2，dna1，即dn是a1, a2, L,

19、an的一个公约数。另一方面，对于a1, a2, L, an的任何公约数d，由定理2的推论及d2, L, dn的定义，依次得出 da1，da2 dd2， dd2，da3 dd3，ddn - 1，dan ddn，因此dn是a1, a2, L, an的公约数中的最大者，即dn = (a1, a2, L, an)。证毕。例1 证明：若n是正整数，则是既约分数。解 由定理1得到(21n + 4, 14n + 3) = (7n + 1, 14n + 3) = (7n + 1, 1) = 1。注：一般地，若(x, y) = 1，那么，对于任意的整数a，b，有(x, y) = (x -ay, y) = (x

20、-ay, y - b(x -ay) = (x -ay, (ab + 1)y - bx)，因此，是既约分数。例2 证明：121n2 + 2n + 12，nZ。解 由于121 = 112，n2 + 2n + 12 = (n + 1)2 + 11，所以，若112(n + 1)2 + 11， (3)则11(n + 1)2，因此，由定理4的推论1得到11n + 1，112(n + 1)2。再由式(3)得到11211，这是不可能的。所以式(3)不能成立。注：这个例题的一般形式是：设p是素数，a，b是整数，则pk(an + b)k + pk - 1c，其中c是不被p整除的任意整数，k是任意的大于1的整数。例

21、3 设a，b是整数，且9a2 + ab + b2， (4)则3(a, b)。解 由式(4)得到9(a - b)2 + 3ab 3(a - b)2 + 3ab 3(a - b)2 3a - b (5) 9(a - b)2。再由式(4)得到93ab 3ab。因此，由定理4的推论1，得到3a或3b。若3a，由式(5)得到3b；若3b，由(5)式也得到3a。因此，总有3a且3b。由定理2的推论推出3(a, b)。例4 设a和b是正整数，b 2，则2b - 12a + 1。解 () 若a b，记a = kb + r，0 r b，此时2kb - 1 = (2b - 1)(2(k - 1)b + 2(k -

22、 2)b + L + 1) = (2b - 1)Q，其中Q是整数。所以2a + 1 = 2kb + r + 1 = 2r(2kb - 1 + 1) + 1 = 2r(2b - 1)Q + 1) + 1 = (2b - 1)Q + (2r + 1)，其中Q是整数。因此2b - 12a + 1 2b - 12r + 1，在()中已经证明这是不可能的，所以式(6)不能成立。综上证得2b - 12a + 1。习 题 三1. 证明定理1中的结论()()。2. 证明定理2的推论1, 推论2和推论3。3. 证明定理4的推论1和推论3。4. 设x，yZ，172x + 3y，证明：179x + 5y。5. 设a

23、，b，cN，c无平方因子，a2b2c，证明：ab。6. 设n是正整数，求的最大公约数。第四节 最小公倍数定义1 整数a1, a2, L, ak的公共倍数称为a1, a2, L, ak的公倍数。a1, a2, L, ak的正公倍数中的最小的一个叫做a1, a2, L, ak的最小公倍数，记为a1, a2, L, ak。定理1 下面的等式成立：() a, 1 = |a|，a, a = |a|；() a, b = b, a；() a1, a2, L, ak = |a1|, |a2| L, |ak|；() 若ab，则a, b = |b|。证明 留作习题。由定理1中的结论()可知，在讨论a1, a2,

24、L, ak的最小公倍数时，不妨假定它们都是正整数。在本节中总是维持这一假定。最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理。定理2 对任意的正整数a，b，有a, b =。证明 设m是a和b的一个公倍数，那么存在整数k1，k2，使得m = ak1，m = bk2，因此ak1 = bk2 。 (1)于是由于= 1，所以由第三节定理4得到其中t是某个整数。将上式代入式(1)得到m =t 。 (2)另一方面，对于任意的整数t，由式(2)所确定的m显然是a与b的公倍数，因此a与b的公倍数必是式(2)中的形式，其中t是整数。当t = 1时，得到最小公倍数a, b =。证毕。推论1 两个整数的任

25、何公倍数可以被它们的最小公倍数整除。证明 由式(2)可得证。证毕。这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数。推论2 设m，a，b是正整数，则ma, mb = ma, b。证明 由定理2及第三节定理2的推论得到ma, mb = ma, b。证毕。定理3 对于任意的n个整数a1, a2, L, an，记a1, a2 = m2，m2, a3 = m3，L，mn-2, an-1 = mn-1，mn-1, an = mn，则a1, a2, L, an = mn。证明 我们有 mn = mn-1, an mn-1mn，anmn，mn-1 = mn-2, an-1 mn

26、-2mn-1mn，anmn，an-1mn-1mn，mn-2 = mn-3, an-2 mn-3mn-2mn，anmn，an-1mn，an-2mn， m2 = a1, a2 anmn，L，a2mn，a1mn，即mn是a1, a2, L, an的一个公倍数。另一方面，对于a1, a2, L, an的任何公倍数m，由定理2的推论及m2, L, mn的定义，得m2m，m3m，L，mnm。即mn是a1, a2, L, an最小的正的公倍数。证毕。推论 若m是整数a1, a2, L, an的公倍数，则a1, a2, L, anm 。证明 留作习题。定理4 整数a1, a2, L, an两两互素，即(ai,

27、 aj) = 1，1 i, j n，i j的充要条件是a1, a2, L, an = a1a2Lan 。 (3)证明 必要性 因为(a1, a2) = 1，由定理2得到a1, a2 = a1a2 。由(a1, a3) = (a2, a3) = 1及第三节定理4推论3得到(a1a2, a3) = 1，由此及定理3得到a1, a2, a3 = a1, a2, a3 = a1a2, a3 = a1a2a3 。如此继续下去，就得到式(3)。充分性 用归纳法证明。当n = 2时，式(3)成为a1, a2 = a1a2。由定理2a1a2 = a1, a2 = (a1, a2) = 1，即当n = 2时，充

28、分性成立。假设充分性当n = k时成立，即a1, a2, L, ak = a1a2Lak (ai, aj) = 1，1 i, j k，i j。对于整数a1, a2, L, ak, ak + 1，使用定理3中的记号，由定理3可知a1, a2, L, ak, ak + 1 = mk, ak + 1。 (4)其中mk = a1, a2, L, ak。因此，如果a1, a2, L, ak, ak + 1 = a1a2Lakak + 1，那么，由此及式(4)得到a1, a2, L, ak, ak + 1 = mk, ak + 1 = a1a2Lakak + 1，即= a1a2Lak ，显然mk a1a2Lak，(mk, ak + 1) 1。所以若使上式成立，必是(mk, ak + 1) = 1， (5)并且mk = a1a2Lak 。 (6)由式(6)与式(5)推出(ai, ak + 1) = 1，1 i k； (7)由式(6)及归纳假设推出(ai, aj) = 1，1