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

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

2、整数果不存在整数c使得使得a=bc成立，则称成立，则称a不被不被b整除，记为整除，记为b a。|第一节第一节 数的整除性数的整除性 显然每个非零整数显然每个非零整数a都有约数都有约数 1，a，称这四个数为称这四个数为a的平凡约数，的平凡约数，a的另外的约数的另外的约数称为非平凡约数。称为非平凡约数。被被2整除的整数称为偶数，不被整除的整数称为偶数，不被2整除的整除的整数称为奇数。整数称为奇数。由定义可得下面定理，证明留作练习。由定义可得下面定理，证明留作练习。第一节第一节 数的整除性数的整除性定理定理1 下面的结论成立：下面的结论成立：()a b ab；()a b，b c a c；()b ai

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

4、小的素约数，所以是最小的素约数，所以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，则，则2s=2 (2 r n r)(3 r (n 1)r)(n r 2 r)=2 (n 2)Q，|第一节第一节 数的整除性数的整除性其中其中Q是整数。若是整数。若n 2 s，由上式知

5、，由上式知n 2 2，因，因为为n 2 2，这是不可能的，所以，这是不可能的，所以n 2 s。例例2 设设A=d1,d2,dk 是是n的所有约数的集合的所有约数的集合,则则B=也是也是n的所有约数的集合。的所有约数的集合。解解 由以下三点理由可以证得结论：由以下三点理由可以证得结论：()A和和B的元素个数相同；的元素个数相同；()若若di A，即，即di n，则，则 ，反之亦然；，反之亦然；|,21kdndndnndni|第一节第一节 数的整除性数的整除性()若若di dj，则，则 。例例3 以以d(n)表示表示n的正约数的个数，例如：的正约数的个数，例如：d(1)=1，d(2)=2，d(3)

6、=2，d(4)=3，。问：。问：d(1)d(2)d(1997)是否为偶数？是否为偶数？解解对于对于n的每个约数的每个约数d，都有，都有n=d ，因此，因此，n的的正约数正约数d与与 是成对地出现的。是成对地出现的。dnjidndn dn第一节第一节 数的整除性数的整除性只有当只有当d=,即即n=d2时，时，d 和和 才是同一个数。才是同一个数。故当且仅当故当且仅当n是完全平方数时，是完全平方数时，d(n)是奇数。是奇数。dndn因为因为442 1997 452，所以在，所以在d(1),d(2),d(1997)中恰有中恰有44个奇数，故个奇数，故d(1)d(2)d(1997)是偶数。是偶数。第一

7、节第一节 数的整除性数的整除性例例4 设凸设凸2n边形边形M的顶点是的顶点是A1,A2,A2n，点，点O在在M的内部，用的内部，用1,2,2n将将M的的2n条边分别编条边分别编号，又将号，又将OA1,OA2,OA2n也同样进行编号，也同样进行编号，若把这些编号作为相应的线段的长度，证明：若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形无论怎么编号，都不能使得三角形OA1A2,OA2A3,OA2nA1的周长都相等。的周长都相等。第一节第一节 数的整除性数的整除性解解 假设这些三角形的周长都相等，记为假设这些三角形的周长都相等，记为s。则。则2ns=3(1 2 2n)=3n(2n 1)，即即2s=3(2n 1)，因此因此2 3(2n 1)，这是不可能的，这个矛盾，这是不可能的，这个矛盾,说明这些三角形的周长不可能全都相等。说明这些三角形的周长不可能全都相等。第一节第一节 数的整除性数的整除性例例5 设整数设整数k 1，证明：，证明：()若若2k n 2k 1，1 a n，a 2k，则则2k a；()若若3k 2n 1 1，证明：，证明：若若p，则，则n1是素数。是素数。5.证明：存在无穷多个自然数证明：存在无穷多个自然数n，使得，使得n不能表示不能表示为为 a2 p（a 0是整数，是整数，p为素数）的形式。为素数）的形式。