初等数论：数的整除性

《初等数论：数的整除性》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《初等数论》第一章整数的可除性第一章整除理论整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。1《初等数论》第一章整数的可除性第一节1数的整除性定义1.设a，b是整数，b0，如果存在整数q，使得a=bq成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号ba；如果不存在整数q使得a=bq成立，则称a不被b整除，记为b

2、a。2第一节1数的整除性《初等数论》第一章整数的可除性显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数

3、。被2整除的整数称为偶数，不被2整除的整数称为奇数。3第一节1数的整除性《初等数论》第一章整数的可除性定理1.下面的结论成立：(ⅰ)abab；证明：因为ab，故b=aq，即b=aq，故ab。(ⅱ)ab，bcac；（传递性）证明：因ab，bc，故b=aq1，c=bq2，则c=aq1q2，故ac。(ⅲ)bai，（i=1,2,,k）ba1x1a2x2akxk，4第一节1数的整除性《初等数论》第一章整数的可除性此处xi（i=1,2,,k）是任意的整数；证明：因为bai，（i=1,2,,k），所以ai=bqi,ai

4、xi=bqixi（i=1,2,,k）故a1x1a2x2akxk=b(q1x1q2x2qkxk)因此ba1x1a2x2akxk，此处xi（i=1,2,,k）是任意的整数(ⅳ)babcac，此处c是任意的非零整数；5第一节1数的整除性《初等数论》第一章整数的可除性证明：因ba，故a=bq，即ac=bcq,则bcac，此处c是任意的非零整数。(ⅴ)ba，a0

5、b

6、

7、a

8、；证明：因ba，故a=bq，即

9、a

10、=

11、b

12、

13、q

14、，又因a0，则q0，故

15、q

16、1，故

17、b

18、≤

19、a

20、；(ⅵ)ba且

21、a

22、<

23、b

24、a=0。证明：因b

25、a，故a=bq，由(ⅴ)可知，若a0，则

26、b

27、

28、a

29、，与

30、a

31、<

32、b

33、矛盾，故a=0。6第一节1数的整除性《初等数论》第一章整数的可除性定义2.若整数a0，1，并且只有约数1和a，则称a是素数（或质数）；否则称a为合数。以后在本书中若无特别说明，素数总是指正素数。7第一节1数的整除性《初等数论》第一章整数的可除性定理2.任何大于1的整数a都至少有一个素约数。证明：若a是素数，则定理是显然的。若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1,d2,,dk。不妨设d1是其中最小的。若d1不是素数，则存在e1>1，e2>1，使得d1=e1e2

34、，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。8第一节1数的整除性《初等数论》第一章整数的可除性推论.任何大于1的合数a必有一个不超过a的素约数。证明：使用定理2中的记号，有a=d1d2，其中d1>1是最小的素约数，2所以d1a。证毕。9第一节1数的整除性《初等数论》第一章整数的可除性例1.设r是正奇数，证明：对任意的正整数n，有rrrn2

35、12n。解：对于任意的正整数a，b以及正奇数k，有kkk1k2k32k1ab=(ab)(aababb)=(ab)q，其中q是整数。rrr记s=12

36、n，rrrr则2s=2(2n)(3(n1))rr(n2)=2(n2)Q，其中Q是整数。若n2s，由上式知n22，因为n2>2，这是不可能的，所以n2

37、s。10第一节1数的整除性《初等数论》第一章整数的可除性例2.设A={d1,d2,,dk}是n的所有约数的集合，nnn{,,,}则B=ddd也是n的所有约数的集合。12k解：由以下三点理由可以证得结论：(ⅰ)A和B的元素个数相同；n(ⅱ)若diA，即din，则d

38、n，反之亦然；inn(ⅲ)若didj，则dd。ij11第一节1数的整除性《初等数论》第一章整数的可除性

39、例3.以d(n)表示n的正约数的个数，例如：d(1)=1，d(2)=2，d(3)=2，d(4)=3，。问：d(1)d(2)d(1997)是否为偶数？n解：对于n的每个约数d，都有n=dd，因此，n的正nn2约数d与d是成对地出现的。只有当d=d，即n=d时，nd和d才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。12第一节1数的整除性《初等数论》第一章整数的可除性22因为44<1997<45，所以在d(1),d(2),,d(1997)中恰有44个奇数，故d(1)d(2)d(1997)是偶数。13第一节1数的整除性《初等数论》第一章整

40、数的可除性