初等数论初步-

初等数论初步第一讲整数的整除§1.1整除一、数论中的著名问题：数论在数学中的地位是独特的，高斯曾经说过“数学是科学的皇后，数论是数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题叫做“皇冠上的明珠”，以鼓励人们去“摘取”。1.费马大定理：当整数n2时，关于x,y,z的不定方程xn+yn=zn无正整数解(x=0或y=0不在考虑之列).1994年德国数学家维尔斯解决了这个问题，并获得了沃尔夫奖.2.孪素数猜想：孪素数应有无穷多对。著名数学家陈景润研究哥德巴赫问题时证明了：存在无穷多个素数,使为素数或至多为两个素数的乘积。(相邻两个奇数同时为素数，这样的数叫做孪素数)2pp3.哥德巴赫猜想：大致可分为两个猜想：每个不小于6的偶数都可以表示为两个奇素数之和；每个不小于9的奇数都可以表示为三个奇素数之和。1966年陈景润证明了任何一个大偶数都可表示成一个素数与另一个素因子不超过2个的数之和”。4.圆内整点问题：高斯曾研究过这样的一个问题：在一个给定半径的圆内有多少个坐标为整数的点呢？后来它又被称作高斯圆内整点问题。5.完全数问题：完全数又称完美数或完备数，是一些特殊的自然数。它所有的真因子的和恰好等于它本身.目前也只知道38个偶完全数，其中最大的是是否存在奇完全数仍是一个悬而未解的问题。69725922.二、整除的性质和概念定义：设a,b为整数，且b≠0.如果存在整数q，使得a=bq，那么称b整除a，或者a能被b整除，记作b|a，并且称b是a的因数，a是b的倍数.如果这样的整数q不存在，就称b不整除a，记作b|a.性质:若，则(1)若，则；(2)若，则；(3)若，则对任意整数x,y，恒有a|bx+cy；(4)若，且a,b互质，则ab|c；(5)若p为质数，p|ab，则p|a或p|b，特别地，若0,0ab|,|abbaabab或|,|abbc|ac|,|abbc|,|abac|,,|npanNpa则结论：一个正整数的各位数字之和能被3整除，那么这个正整数能被3整除.请根据上面整除的性质证明这个命题.探究：利用类似的方法证明能被9,11,7整除的正整数的特征。1、一个正整数的各位数字之和能被9整除，那么这个正整数能被9整除。2、一个正整数的奇数位数字之和与偶数为数字之和的差能被11整除，那么这个整数能被11整除.3、一个正整数的末三位数字组成的数与末三位数字之前的数字组成的数之差能被7(或11)整除，那么这个正整数能被7(或11)整除.三、带余除法(欧式除法算式)例1：判断710316能否被9，11整除.一般地，设a,b为整数，且b≠0，则存在唯一的一对整数q和r，使得a=bq+r,0≤r|b|.其中唯一的q和r分别叫做a除以b的商和余数.例2：2004除以某个整数，其商为74，求除数和余数.探究：我们用符号[x]表示不超过实数x的最大整数，试用a,b表示a除以正整数b的商q和余数r.四、素数及其判别式定义：素数：仅有两个正因数的正整数叫做素数（正因数只有1和它本身）.合数：不是素数又不是1的正整数叫做合数。观察：对于正整数6，7，9，21，65，77，121.观察它们除1以外的最小的正因数，从中你能发现什么规律？结论：每个正整数n除1外的最小正因数p是一个素数.为什么？结论：任何一个大于1的整数n总可分解为一些素数的乘积。结论：素数有无穷多个.结论：如果大于1的整数a不能被所有不超过的素数整除，那么一定是素数。a对给定的大于1的正整数，如何判断它是不是素数呢？例3：找出1～100中的全部素数.埃拉托斯特尼筛法初等数论初步第一讲整数的整除§1.2最大公因数与最小公倍数一、最大公因数定义：给定两个整数a，b，必有公共的因数，叫做它们的公因数。当a，b不全为零时，在有限个公因数中最大的一个叫做a，b的最大公因数，记作(a，b).定义可以推广到n个整数.定义：如果a，b的最大公因数为1，那么称a，b是互素的.类似地，我们也可以定义三个非零整数或更多个非零整数的最大公因数的概念，将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).(6)(ma1,ma2,,mak)=|m|(a1,a2,,ak).(7)记d=(a1,a2,,ak)，则=112,,,()kaaaddd求两个数的最大公因数的方法：1.短除法2.辗转相除法思考：如果b除a的余数为r，那么(a,b)=1成立吗？(a,b)与(b,r)有什么关系？结论：如果b除a的余数为r，那么(a，b)=(b，r).结论：(a,b,c)=((a,b),c)结论：设整数a,b不同时为零，则存在一对整数m,n，使得(a,b)=am+bn.你能用辗转相除法证明这个定理吗？对于任意的整数a，b，c，下面的结论成立：(1)若bac，且(a,b)=1，则bc；(2)若bc，ac且(a,b)=1，则abc.(3)设p为素数，若p|ab，则p|a，或p|b.(4)设p为素数，若，则存在,使得。12|kpaaa(1)iaik|ipa一、最小公倍数定义：任给两个非零整数a,b，一定存在一个整数，它同时为a,b的倍数，这个倍数叫做a,b的公倍数。我们把a,b的最小的正公倍数叫做a,b的最小公倍数，记作[a，b].类似地，我们也可以定义三个非零整数或更多个非零整数的最小公倍数的概念，将a,b,c的最小公倍数记作[a,b,c]，依此类推。结论：两个非零整数a,b的最小公倍数[a,b]一定整除a,b的公倍数。(证明)结论：(a,b)，[a，b]和ab之间的关系：(a,b)[a，b]=|ab|。(证明)例4：求[375，105]的值.结论：[a,b,c]=[[a,b],c]例题讲解例1:若n是奇数，则8n21.例2:证明:若mpmnpq，则mpmqnp.例3:证明:121n22n12，nZ.注：这个例题的一般形式是：设p是素数，a，b是整数，则pk(anb)kpk-1c，其中c是不被p整除的任意整数，k是任意的大于1的整数.||