资源描述:
《初等数论 第一章 整除理论.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第一章整除理论整除性理论是初等数论的基础。本章要介绍带余数除法,辗转相除法,最大公约数,最小公倍数,算术基本定理以及它们的一些应用。第一节数的整除性定义1设a,b是整数,b¹0,如果存在整数c,使得a=bc成立,则称a被b整除,a是b的倍数,b是a的约数(因数或除数),并且使用记号b½a;如果不存在整数c使得a=bc成立,则称a不被b整除,记为ba。显然每个非零整数a都有约数±1,±a,称这四个数为a的平凡约数,a的另外的约数称为非平凡约数。被2整除的整数称为偶数,不被2整除的整数称为奇数。定理1下面的结论成立:(ⅰ)a½bÛ±a½±b;(ⅱ)a½
2、b,b½cÞa½c;(ⅲ)b½ai,i=1,2,L,kÞb½a1x1+a2x2+L+akxk,此处xi(i=1,2,L,k)是任意的整数;(ⅳ)b½aÞbc½ac,此处c是任意的非零整数;(ⅴ)b½a,a¹0Þ
3、b
4、£
5、a
6、;b½a且
7、a
8、<
9、b
10、Þa=0。证明留作习题。定义2若整数a¹0,±1,并且只有约数±1和±a,则称a是素数(或质数);否则称a为合数。以后在本书中若无特别说明,素数总是指正素数。定理2任何大于1的整数a都至少有一个素约数。证明若a是素数,则定理是显然的。若a不是素数,那么它有两个以上的正的非平凡约数,设它们是d1,d2,L,
11、dk。不妨设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+21r+2r+L+nr。解对于任意的正整数a,b以及正奇数k,有ak+bk=(a+b)(ak-1-ak-2b+ak-3b2-L+bk-1)=(a+b)q,其中q是整数。记s=1r+2r+L+nr
12、,则2s=2+(2r+nr)+(3r+(n-1)r)+L+(nr+2r)=2+(n+2)Q,其中Q是整数。若n+2½s,由上式知n+2½2,因为n+2>2,这是不可能的,所以n+2s。例2设A={d1,d2,L,dk}是n的所有约数的集合,则B=也是n的所有约数的集合。解由以下三点理由可以证得结论:(ⅰ)A和B的元素个数相同;(ⅱ)若diÎA,即di½n,则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)是否为偶数?
13、解对于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(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,
14、OA2nA1的周长都相等。解假设这些三角形的周长都相等,记为s。则2ns=3(1+2+L+2n)=3n(2n+1),即2s=3(2n+1),因此2½3(2n+1),这是不可能的,这个矛盾说明这些三角形的周长不可能全都相等。例5设整数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
15、a,则存在整数q,使得a=q2k。显然q只可能是0或1。此时a=0或2k,这都是不可能的,所以2ka;(ⅱ)若3k
16、2b-1,则存在整数q,使得2b-1=
17、q3k,显然q只可能是0,1,或2。此时2b-1=0,3k,或,这都是不可能的,所以3k2b-1。例6写出不超过100的所有的素数。解将不超过100的正整数排列如下:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100按以
18、下步骤进行:(ⅰ)删去1,剩下的后面的第一个数是2,2是素数;(ⅱ)删去2后面的被2整除的数,剩下的2后面的第一个数是3,