初等数论一演示文稿课件.ppt

《初等数论一演示文稿课件.ppt》由会员分享，可在线阅读，更多相关《初等数论一演示文稿课件.ppt（27页珍藏版）》请在三一办公上搜索。

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

2、练习。,第一节 数的整除性,定理1 下面的结论成立：()ab ab；()ab，bc ac；()bai，i=1,2,k ba1x1 a2x2 akxk，此处xi(i=1,2,k)是任意的整数；()ba bcac，此处c是任意的非零整数；()ba,a0|b|a|;ba且|a|b|a=0。,第一节 数的整除性,定义2 若整数a 0，1，并且只有约数 1和 a，则称a是素数(或质数)；否则称a为合数。以后无特别说明，素数总是指正素数。,定理2 任何大于1的整数a都至少有一个素约数。,证明 若a是素数，则定理是显然的。,若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1,d2,dk。,第一节

3、数的整除性,不妨设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 2 1r 2 r n r。,解 对于任意的正整数a，b以及正奇数k，有ak bk=(a b)(ak 1 ak 2b ak 3b2 bk 1)=(a b)q，,其中q是整数。记s=1r 2 r n r

4、，则2s=2(2 r n r)(3 r(n 1)r)(n r 2 r)=2(n 2)Q，,第一节 数的整除性,其中Q是整数。若n 2s，由上式知n 22，因为n 2 2，这是不可能的，所以n 2 s。,例2 设A=d1,d2,dk 是n的所有约数的集合,则B=也是n的所有约数的集合。,解 由以下三点理由可以证得结论：()A和B的元素个数相同；()若diA，即din，则，反之亦然；,第一节 数的整除性,()若di dj，则。,例3 以d(n)表示n的正约数的个数，例如：d(1)=1，d(2)=2，d(3)=2，d(4)=3，。问：d(1)d(2)d(1997)是否为偶数？,解对于n的每个约数d，

5、都有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)是偶数。,第一节 数的整除性,例4 设凸2n边形M的顶点是A1,A2,A2n，点O在M的内部，用1,2,2n将M的2n条边分别编号，又将OA1,OA2,OA2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2,OA2A3,OA2nA1的周长都相等。,第一节 数的整除

6、性,解 假设这些三角形的周长都相等，记为s。则2ns=3(1 2 2n)=3n(2n 1)，即2s=3(2n 1)，因此23(2n 1)，这是不可能的，这个矛盾,说明这些三角形的周长不可能全都相等。,第一节 数的整除性,例5 设整数k 1，证明：()若2k n 2k 1，1 a n，a 2k，则2k a；()若3k 2n 1 3k+1，1 b n，2b 1 3k，则3k 2b 1。,第一节 数的整除性,解()若2k|a，则存在整数q，使得a=q2k。显然q只可能是0或1。此时a=0或2k，这都是不可能的，所以2k a；,()若 3k|2b-1，则存在整数q，使得2b-1=q3k，显然q只可能是

7、0，1,或2。此时2b-1=0，3k，或，这都是不可能的，所以3k 2b 1。,第一节 数的整除性,例6 写出不超过100的所有的素数。,解 将不超过100的正整数排列如下：,第一节 数的整除性,1 2 3 4 5 6 7 8 9 10 11 12 1314 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72

8、 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100,第一节 数的整除性,按以下步骤进行：()删去1，剩下的后面的第一个数是2，2是素数,删去2后面的被2整除的数；()剩下的2后面的第一个数是3，3是素数,再删去3后面的被3整除的数；()剩下的3后面的第一个数是5，5是素数,再删去5后面的被5整除的数；()剩下的5后面的第一个数是7，7是素数,再删去7后面的被7整除的数.,第一节 数的整除性,照以上步骤可以到素数2,3,5,7,11,等25个。由定理2推论可知，不超过100的合

9、数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。,在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。,第一节 数的整除性,例7 证明：存在无穷多个正整数a，使得n4 a（n=1,2,3,）都是合数。,解 取a=4k4，对于任意的nN，有n4 4k4=(n2 2k2)2 4n2k2=(n2 2k2 2nk)(n2 2k2 2nk)。因为 n2 2k2 2nk=(n k)2 k2 k2，所以，对于任意的k=

10、2,3,以及任意的nN，n4 a是合数。,第一节 数的整除性,例8 设a1,a2,an是整数，且a1 a2 an=0，a1a2an=n，则4n。,解 如果2 n，则n,a1,a2,an都是奇数。于是a1 a2 an是奇数个奇数之和，不可能等于零，这与题设矛盾，,所以2n，即在a1,a2,an中至少有一个偶数。,第一节 数的整除性,如果只有一个偶数，不妨设为a1，那么2 ai（2 i n）。此时有等式a2 an=a1，在上式中，左端是(n 1)个奇数之和，右端是偶数，这是不可能的，因此，在a1,a2,an中至少有两个偶数，即4n。,第一节 数的整除性,例9 若n是奇数，则8n2 1。,解 设n=

11、2k 1，则n2 1=(2k 1)2 1=4k(k 1)。在k和k 1中有一个是偶数，所以8n2 1。,例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，我们可以提出下面的问题：问题 d(1)2 d(2)2 d(1997)2被4除的余数是多少？,第一节 数的整除性,例10 证明：方程 a12 a22 a32=1999(1)无整数解。,解 若a1，a2，a3都是奇数，则存在整数A1，A2，A3，使得a12=8A1 1，a22=8A2 1，a32=8A3 1，于是a12 a22 a32=8(A1 A2 A3)3。,第一节 数的整除性,由于1999被8除的余数是7，所以a1，a2，a3不可能

12、都是奇数。由式(1)，a1，a2，a3中只能有一个奇数，设a1为奇数，a2，a3为偶数，则存在整数A1，A2，A3，使得a12=8A1 1，a22=8A2 r，a32=8A3 s，于是a12 a22 a32=8(A1 A2 A3)1 r s，,第一节 数的整除性,其中r和s是整数，而且只能取值0或4。这样a12 a22 a32被8除的余数只可能是1或5，但1999被8除的余数是7，所以这样的a1，a2，a3也不能使式(2)成立。综上证得所需要的结论。,习 题 一,1.证明定理1。2.证明：若m pmn pq,则m pmq np。3.证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。4.设p是n的最小素约数，n=pn1，n1 1，证明：若p，则n1是素数。5.证明：存在无穷多个自然数n，使得n不能表示为 a2 p（a 0是整数，p为素数）的形式。,