资源描述：
《数论01_0924new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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½
2、bÛ±a½±b；(ⅱ)a½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都至少有一个素约数。37证明若a是素数，则定理是显然的。若a不是素数，那
11、么它有两个以上的正的非平凡约数，设它们是d1,d2,L,dk。不妨设d1是其中最小的。若d1不是素数，则存在e1>1，e2>1，使得d1=e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。推论任何大于1的合数a必有一个不超过的素约数。证明反证法。（注意我们还没有讲算术基本定理）定理3(Euclid)素数有无穷多个证明多种方法。例1设r是正奇数，证明：对任意的正整数n，有n+21r+2r+L+nr。解对于任意的正整数a，b以及正奇数k，有ak+bk=(a+b)(ak-1-ak-2b
12、+ak-3b2-L+bk-1)=(a+b)q，其中q是整数。记s=1r+2r+L+nr，则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，则。37例3以d(n)表示n的正约数的个数，例如
13、：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(1)+d(2)+L+d(1997)是偶数。例4设整数k³1，证明：(ⅰ)若2k£n<2k+1，1£a£n，a¹2k，则2ka；(ⅱ)若3k£2n-1<3k
14、+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=q3k，显然q只可能是0，1,或2。此时2b-1=0，3k，或，这都是不可能的，所以3k2b-1。例5写出不超过100的所有的素数。解将不超过100的正整数排列如下：12345678910111213141516171819202122232425262728293031323334353637383940
17、414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910037按以下步骤进行：(ⅰ)删去1，剩下的后面的第一个数是2，2是素数；(ⅱ)删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；(ⅲ)再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；(ⅳ)再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数；L
18、L照以上步骤可以依次得到素数2,3,5,7,11,L。由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。在例5中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这
