初等数论初步ppt课件.ppt

《初等数论初步ppt课件.ppt》由会员分享，可在线阅读，更多相关《初等数论初步ppt课件.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、初等数论初步初等数论初步第一讲第一讲 整数的整除整数的整除1.1 整除整除一、数论中的著名问题：一、数论中的著名问题：数数论论在在数数学学中中的的地地位位是是独独特特的的，高高斯斯曾曾经经说说过过“数数学学是是科科学学的的皇皇后后，数数论论是是数数学学中中的的皇皇冠冠”。因因此此，数数学学家家都都喜喜欢欢把把数数论论中中一一些些悬悬而而未未决决的的疑疑难难问问题题叫叫做做“皇皇冠冠上上的的明明珠珠”，以以鼓鼓励励人人们们去去“摘摘取取”。1.费马大定理：费马大定理：当整数当整数n2时，关于时，关于x,y,z的不定方程的不定方程xn+yn=zn无正整数解无正整数解(x=0或或y=0不在考虑之列不

2、在考虑之列).1994年德国数学家维尔斯解决了这个问题，并获得了沃年德国数学家维尔斯解决了这个问题，并获得了沃尔夫奖尔夫奖.2.2.孪素数猜想孪素数猜想：孪素数应有无穷多对。著名数学家：孪素数应有无穷多对。著名数学家陈景润研究哥德巴赫问题时证明了：存在无穷多个陈景润研究哥德巴赫问题时证明了：存在无穷多个素数素数 ,使使 为素数或至多为两个素数的乘积。为素数或至多为两个素数的乘积。(相邻两个奇数同时为素数，这样的数叫做孪素数相邻两个奇数同时为素数，这样的数叫做孪素数)3.3.哥德巴赫猜想哥德巴赫猜想：大致可分为两个猜想：每个不小于：大致可分为两个猜想：每个不小于6 6的偶数都可以表示为两个奇素数

3、之和；每个不小于的偶数都可以表示为两个奇素数之和；每个不小于9 9的的奇数都可以表示为三个奇素数之和。奇数都可以表示为三个奇素数之和。19661966年陈景润证明年陈景润证明了任何一个大偶数都可表示成一个素数与另一个素因子了任何一个大偶数都可表示成一个素数与另一个素因子不超过不超过2 2个的数之和个的数之和”。4.4.圆内整点问题圆内整点问题：高斯曾研究过这样的一个问题：在一：高斯曾研究过这样的一个问题：在一个给定半径的圆内有多少个坐标为整数的点呢？后来它个给定半径的圆内有多少个坐标为整数的点呢？后来它又被称作高斯圆内整点问题。又被称作高斯圆内整点问题。5.5.完全数问题完全数问题：完全数又称

4、完美数或完备数，是一些特：完全数又称完美数或完备数，是一些特殊的自然数。它所有的真因子的和恰好等于它本身殊的自然数。它所有的真因子的和恰好等于它本身.目目前也只知道前也只知道3838个偶完全数，其中最大的是个偶完全数，其中最大的是 是否存在奇完全数仍是一个悬而未解的问题。是否存在奇完全数仍是一个悬而未解的问题。二、整除的性质和概念二、整除的性质和概念定义：定义：设设a,b为整数，且为整数，且b0.如果存在整数如果存在整数q，使得，使得a=bq，那么称，那么称b整除整除a，或者，或者a能被能被b整除，记作整除，记作b|a，并且称并且称b是是a的的因数因数，a是是b的的倍数倍数.如果这样的整数如果

5、这样的整数q不存在，就称不存在，就称b不整除不整除a，记作，记作b|a.性质性质:若若 ，则，则(1)(1)若若 ，则，则 ；(2)(2)若若 ，则，则 ；(3)(3)若若 ，则对任意整数，则对任意整数x,yx,y，恒有，恒有a|bx+cya|bx+cy；(4)(4)若若 ，且，且a,ba,b互质，则互质，则ab|cab|c；(5)(5)若若p p为质数，为质数，p|abp|ab，则，则p|ap|a或或p|bp|b，特别地，若，特别地，若结论：一个正整数的各位数字之和能被结论：一个正整数的各位数字之和能被3 3整除，整除，那么这个正整数能被那么这个正整数能被3 3整除整除.请根据上面整除的性质

6、证明这个命题请根据上面整除的性质证明这个命题.探究：探究：利用类似的方法证明能被利用类似的方法证明能被9,11,79,11,7整除的正整数的特征。整除的正整数的特征。1 1、一个正整数的各位数字之和能被、一个正整数的各位数字之和能被9 9整除，那么这个正整除，那么这个正整数能被整数能被9 9整除。整除。2 2、一个正整数的奇数位数字之和与偶数为数字之和的差、一个正整数的奇数位数字之和与偶数为数字之和的差能被能被1111整除，那么这个整数能被整除，那么这个整数能被1111整除整除.3 3、一个正整数的末三位数字组成的数与末三位数字之前、一个正整数的末三位数字组成的数与末三位数字之前的数字组成的数

7、之差能被的数字组成的数之差能被7(7(或或11)11)整除，那么这个正整数整除，那么这个正整数能被能被7(7(或或11)11)整除整除.三、带余除法三、带余除法(欧式除法算式欧式除法算式)例例1：判断：判断710316能否被能否被9，11整除整除.一般地，设一般地，设a,ba,b为整数，且为整数，且b b0，则存在唯一的，则存在唯一的一对整数一对整数q q和和r r，使得，使得a=bq+r,0a=bq+r,0r|b|.其中唯其中唯一的一的q q和和r r分别叫做分别叫做a a除以除以b b的的商商和和余数余数.例例2 2：20042004除以某个整数，其商为除以某个整数，其商为7474，求除数

8、，求除数和余数和余数.探究：探究：我们用符号我们用符号xx表示不超过实数表示不超过实数x x的最大整数，试的最大整数，试用用a,ba,b表示表示a a除以正整数除以正整数b b的商的商q q和余数和余数r.r.四、素数及其判别式四、素数及其判别式定义：定义：素数：素数：仅有两个正因数的正整数叫做素数（正仅有两个正因数的正整数叫做素数（正因数只有因数只有1 1和它本身）和它本身）.合数：合数：不是素数又不是不是素数又不是1 1的正整数叫做合数。的正整数叫做合数。观察：观察：对于正整数对于正整数6，7，9，21，65，77，121.观察它观察它们除们除1以外的最小的正因数，从中你能发现什么以外的最

9、小的正因数，从中你能发现什么规律？规律？结论：每个正整数结论：每个正整数n n除除1 1外的最小正因数外的最小正因数p p是一个是一个素数素数.为什么？为什么？结论：任何一个大于结论：任何一个大于1 1的整数的整数n n总可分解为一些总可分解为一些素数的乘积。素数的乘积。结论：素数有无穷多个结论：素数有无穷多个.结论：如果大于结论：如果大于1 1的整数的整数a a不能被所有不超过不能被所有不超过 的素数整除，那么一定是素数。的素数整除，那么一定是素数。对给定的大于对给定的大于1 1的正整数，如何判断它是不是的正整数，如何判断它是不是素数呢？素数呢？例例3 3：找出：找出1 1100100中的全

10、部素数中的全部素数.埃拉托斯特尼筛法埃拉托斯特尼筛法初等数论初步初等数论初步第一讲第一讲 整数的整除整数的整除1.2 最大公因数与最小公倍数最大公因数与最小公倍数一、最大公因数一、最大公因数 定义：定义：给定两个整数给定两个整数a a，b b，必有公共的因数，必有公共的因数，叫做它们的公因数。当叫做它们的公因数。当a a，b b不全为零时，在有不全为零时，在有限个公因数中最大的一个叫做限个公因数中最大的一个叫做a a，b b的的最大公因最大公因数数，记作，记作(a(a，b).b).定义可以推广到定义可以推广到n n个整数个整数.定义：定义：如果如果a a，b b的最大公因数为的最大公因数为1

11、1，那么称，那么称a a，b b是互素的是互素的.类似地，我们也可以定义三个非零整数或更多类似地，我们也可以定义三个非零整数或更多个非零整数的最大公因数的概念，将个非零整数的最大公因数的概念，将a,b,ca,b,c的的最大公因数记作最大公因数记作(a,b,c)(a,b,c)，依此类推。，依此类推。相关性质：相关性质：(1)(a1,a2,ak)=(|a1|,|a2|,|ak|)；(2)(a,1)=1，(a,0)=|a|，(a,a)=|a|；(3)(a,b)=(b,a)；(4)若若p是素数，是素数，a是整数，则是整数，则(p,a)=1或或p a；(5)若若a=bq r，则，则(a,b)=(b,r)

12、.(6)(ma1,ma2,mak)=|m|(a1,a2,ak).(7)记记d=(a1,a2,ak)，则，则 =1 求两个数的最大公因数的方法：求两个数的最大公因数的方法：1.短除法短除法2.辗转相除法辗转相除法 思考：思考：如果如果b b除除a a的余数为的余数为r r，那么，那么(a,b)=1(a,b)=1成立吗？成立吗？(a,b)(a,b)与与(b,r)(b,r)有什么关系？有什么关系？结论：如果结论：如果b b除除a a的余数为的余数为r r，那么，那么(a(a，b)=(bb)=(b，r).r).结论：结论：(a,b,c)=(a,b),c)结论：设整数结论：设整数a,ba,b不同时为零，

13、则存在一对整不同时为零，则存在一对整数数m,nm,n，使得，使得(a,b)=am+bn.(a,b)=am+bn.你能用辗转相除法证明这个定理吗？你能用辗转相除法证明这个定理吗？对于任意的整数对于任意的整数a a，b b，c c，下面的结论成立：，下面的结论成立：(1)(1)若若b b acac，且，且(a a,b b)=1 1，则，则b b c c；(2)(2)若若b b c c，a a c c且且(a a,b b)=1 1，则，则abab c c.(3)(3)设设p p为素数，若为素数，若p|abp|ab，则，则p|ap|a，或，或p|b.p|b.(4)(4)设设p p为素数，若为素数，若

14、，则存在，则存在 ,使得使得 。一、最小公倍数一、最小公倍数 定义：定义：任给两个非零整数任给两个非零整数a,ba,b，一定存在一个，一定存在一个整数，它同时为整数，它同时为a,ba,b的倍数，这个倍数叫做的倍数，这个倍数叫做a,ba,b的公倍数。我们把的公倍数。我们把a,ba,b的最小的正公倍数叫做的最小的正公倍数叫做a,ba,b的的最小公倍数最小公倍数，记作，记作aa，b.b.类似地，我们也可以定义三个非零整数或更多类似地，我们也可以定义三个非零整数或更多个非零整数的最小公倍数的概念，将个非零整数的最小公倍数的概念，将a,b,ca,b,c的的最小公倍数记作最小公倍数记作a,b,ca,b,c

15、，依此类推。，依此类推。结论：两个非零整数结论：两个非零整数a,ba,b的最小公倍数的最小公倍数a,ba,b一一定整除定整除a,ba,b的公倍数。的公倍数。(证明证明)结论：结论：(a,b)(a,b)，aa，bb和和abab之间的关系：之间的关系：(a,b)a(a,b)a，b=|ab|b=|ab|。(证明证明)例例4 4：求：求375375，105105的值的值.结论：结论：a,b,c=a,b,c例题讲解例题讲解例例1:若若n是奇数，则是奇数，则8 n2 1.例例2:证明证明:若若m p mn pq，则，则m p mq np.例例3:证明证明:121 n2 2n 12，n Z.注：这个例题的一般形式是：设注：这个例题的一般形式是：设p p是素数，是素数，a a，b b是整数，是整数，则则p pk k(an an b b)k k p pk-1k-1c c，其中，其中c c是不被是不被p p整除的任意整整除的任意整数，数，k k是任意的大于是任意的大于1 1的整数的整数.