大学数学---初等数论

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,大学数学,初等数论,线性代数,射影几何,概率统计,初等数论,赵争,Email:zhaoz,序言,数论是研究整数性质的一门很古老的数学分支，,其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布,以及数论函数等内容，统称,初等数论,（,Elementary Number Theory,）。,初等数论的大部份内容早在古希腊欧几里德的,几何原本,中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，,即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的,“,中国剩余定理,”,正是我国古代,孙子算经,中的下卷第,26,题，我国称之为,“,孙子定理,”,。,近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。,1801,年，高斯的,算术探究,是数论的划时代杰作。,“,数学是科学之王，数论是数学之王,”,。,-,高斯,数论是研究整数性质的一门很古老的数学分支，,其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布,以及数论函数等内容，统称,初等数论,（,Elementary Number Theory,）。,初等数论的大部份内容早在古希腊欧几里德的,几何原本,中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，,即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的,“,中国剩余定理,”,正是我国古代,孙子算经,中的下卷第,26,题，我国称之为,“,孙子定理,”,。,近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。,1801,年，高斯的,算术探究,是数论的划时代杰作。,“,数学是科学之王，数论是数学之王,”,。,-,高斯,欧几里德 高斯,费马,欧拉,拉格朗日 毕达格拉斯,由于自,20,世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等 新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了 广泛的应用，无疑同时间促进着数论的发展。,数论是以严格和简洁著称，内容既丰富又深刻。我将会介绍数论中最基本的概念和理论，希望大家能对这门学问产生兴趣，并且对中小学时代学习过的一些基本概念，例如,整除性,、,最大公因子,、,最小公倍数,、,辗转相除法,等，有较深入的了解。,第一章 整数的整除性,1.1,整除的概念,一、基本概念,1,、自然数、整数,2,、正整数、负整数,3,、奇数、偶数,一个性质：,整数,+,整数,=,整数,整数,-,整数,=,整数,整数*整数,=,整数,二、整除,1,、定义：设,a,，,b,是整数，,b0,。如果存在一个整数,q,使得等式：,a=bq,成立，则称,b,能整除,a,或,a,能被,b,整除,，记作,ba,；如果这样的,q,不存在，则称,b,不能整除,a,。,2,、整除的性质,（,1,）如果,ba,，,cb,，则,ca.,（,2,）如果,ba,，则,cbca.,（,3,）如果,ca,，则对任何整数,d,，,cda.,（,4,）如果,ca,，,cb,，则对任意整数,m,，,n,，有,cma+nb.,（,5,）如果,ab,，,ba,，则,a=,b.,3,、质数、合数,质数（素数）,合数,质因数,分解质因数,算术基本定理,4,、带余除法,定理：,设,a,，,b,是两个整数，其中,b,0,，则存在两个唯一的整数,q,及,r,，使得,a=bq+r,，,0r,b,成立,.,我们称,r,是,b,除,a,的余数。,可以看出：,b,整除,a,的充要条件是,r=0,。,1.2,最大公因数和辗转相除法,一、最大公因数,1,、定义,设,a,1,，,a,2,，,，,a,n,是,n,个不全为零的整数，若整数,d,是它们之中每一个的因数，那么,d,就叫做,a,1,，,a,2,，,，,a,n,的一个公因数。整数的公因数中最大的一个叫做它们的最大公因数，记作,（,a,1,，,a,2,，,，,a,n,）,。,2,、互质,设,a1,，,a2,，,，,an,是,n,个不全为零的整数，若,（,a1,，,a2,，,，,an,）,=1,，,则称,a1,，,a2,，,，,an,是,互质,的。,注：三个互质比一定两两互质。,比如（,3,，,4,，,6,）,=1,，但（,3,，,6,）,=3,，（,4,，,6,）,=2.,3,、最大公因数的性质,（,1,）当,ba,时，（,a,，,b,）,=b.,（,2,）,a,，,b,的一切公因数都是（,a,，,b,）的因数,.,（,3,）若,a,，,b,是正整数，,m,是任一正整数，则有,（,am,，,bm,）,=,（,a,，,b,）,m.,（,4,）若（,a,，,b,）,=1,，,c,为任一正整数，则有,（,ac,，,b,）,=,（,c,，,b,）,（,5,）若（,a,，,b,）,=1,，,bac,，则有,bc.,（,6,）若,a,，,b,，,c,是任意三个正整数，则（,a,，,b,）,=d,的充分必要条件是：,4,、辗转相除法,一个推论,若,a,，,b,是正整数，且（,a,，,b,）,=d,，则必存在整数,m,和,n,，使得,d=ma+nb,注：证明可由带余除法逆向代入证得。,例,1,：求（,735000,，,238948,）,.,解：因为,735000=2389483+18156,，,238948=1815613+2920,18156=29206+636,2920=6364+376,636=3761+260,376=2601+116,260=1162+28,116=284+4,28=47,所以（,735000,，,238948,）,=4.,例,2,：求（,2605,，,-5125,）,.,解：因为,5125=26051+2520,，,2605=25201+85,2520=8529+55,85=551+30,55=301+25,30=251+5,25=55,所以（,2605,，,-5125,）,=5.,例,3,：求（,2605,，,3245,，,7250,）,.,解：先求,2065,和,3245,的最大公因数。,因为,3245=26051+1180,，,2605=11801+885,1180=8851+295,885=2953,所以（,2605,，,3245,）,=295.,再求,295,与,7250,的最大公因数。,7250=29524+170,，,295=1701+125,170=1251+45,125=452+35,45=351+10,35=103+5,10=52,所以（,2605,，,3245,，,7250,）,=,（,295,，,7250,）,=5.,练习,求（,125,，,610,）,.,求（,51306,，,1224,）,.,求（,538,，,244,，,555,）,.,1.3,最小公倍数一、定义,二、最小公倍数的性质,1,、定理：,例,1,：求,3468,24871.,解：由辗转相除法得：,（,3468,，,24871,）,=17.,所以,3468,24871= =5073684.,例,2,：求,128,，,234,，,524.,习题,1,、求,21,，,35.,2,、求,123,，,321.,3,、求,125,，,725,，,1125,，,2015.,1.4,整数可除性的检验,一、整数的表示,1,、十进制的整数的意义：各位数字的加权和。,2,、一般表示：,进位制,进位制,是一种记数方式，用有限的,数字,在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为,n,，即可称,n,进位制，简称,n,进制。现在最常用的是,十进制,，通常使用,10,个,阿拉伯数字,0-9,进行记数。,进位制,常见的进位制：,二进制广泛用于计算机,三进制用于军队编制,十进制最常用,十二进制时辰、月份、一打物品,十六进制广泛用于计算机,六十进制,秒、分,角度,二、可除性判别方法,判别方法,1,：（整数被,2,整除）,如果一个整数的末尾数字能被,2,整除，则该数能被,2,整除。即：若,2a,0,，,则,2 N.,判别方法,2,：（整数被,5,整除）,如果一个整数的末尾数字能被,5,整除，则该数能被,5,整除。即：若,5a,0,，,则,5N.,判别方法,3,：（整数被,3,整除）,如果一个整数的各位数字之和能被,3,整除，则该数能被,3,整除。即：若,3a,n,+a,n-1,+,a,1,+a,0,，,则,3 N.,判别方法,4,：（整数被,9,整除）,如果一个整数的各位数字之和能被,9,整除，则该数能被,9,整除。即：若,9a,n,+a,n-1,+,a,1,+a,0,，,则,9 N.,二、可除性判别方法,判别方法,5,：（整数被,11,整除）,如果一个整数将其最后三位数字去掉后得到的位数少,3,位的新整数与该整数末三位数字组成的数之差能被,11,整除，则该整数能,11,整除,.,即如果,，则,11N.,判别方法,6,：（整数被,13,整除）,如果一个整数将其最后三位数字去掉后得到的位数少,3,位的新整数与该整数末三位数字组成的数之差能被,11,整除，则该整数能,11,整除,.,即如果,，则,13N.,第二章 不定方程,2.1,二元一次不定方程,一、齐次方程,二、非齐次方程,例,1,三、有整数解的充要条件,两个推论,推论,1,：,如果（,a,，,b,）,=1,，那么方程（,1,）有整数解,.,推论,2,：,如果（,a,，,b,）,c,，那么方程（,1,）没有整数解,.,例,2,：判断下列不定方程有没有整数解。,四、整数分离法解不定方程,步骤：,1,、把不定方程变形，用系数绝对值较大的未知数表示系数绝对值较小的未知数；,2,、把,1,中的代数式分离成一个整式和一个分式之和；,3,、通过观察和其它方法使分式值为整数从而筛选得到不定方程的整数解。,例,3,例,4:,解下列不定方程,五、不定方程组,例,2,：求解不定方程组,习题,2.2,多元一次不定方程,一、三元一次不定方程,1,、解的存在性,定理：三元一次不定方程,ax+by+cz=d,有整数解的充分必要条件是（,a,，,b,，,c) d,，,其中,a,，,b,，,c,，,d,都是正整数,.,2,、三元一次不定方程的通解,一般解法,第三章 同余,3.1,同余的概念和性质,二、同余的性质,定理,同余关系是等价关系，即,(1),自反性,a,a,(mod,m,),。,(2),对称性 若,a,b,(mod,m,),，则,b,a,(mod,m,),。,(3),传递性 若,a,b,(mod,m,),，,b,c,(mod,m,),，则,a,c,(mod,m,),。,定理,设,a,、,b,、,c,、,d,为整数，,m,为正整数，若,a,b,(mod,m,),，,c,d,(mod,m,),，则：,(1),ax,cy,bx,dy,(mod,m,),，,x,、,y,为任意整数，即同余式可以相加；,(2),ac,bd,(mod,m,),，即同余式可以相乘；,(3),a,n,b,n,(mod,m,),，,n,0,；,(4),f,(,a,),f,(,b,)(mod,m,),，,f,(,x,),为任一整系数多项式。,证明,(1),因为,a,b,(mod,m,),，,c,d,(mod,m,),，所以,m,|(,a,b,),，,m,|(,c,d,),，于是,m,|(,a,b,),x,(,c,d,),y,),，即,m,|(,ax,cy,),(,bx,dy,),，故,ax,cy,bx,dy,(mod,m,),。,(2),因为,a,b,(mod,m,),，,c,d,(mod,m,),，所以,m,|(,a,b,),，,m,|(,c,d,),，于是,m,|(,a,b,),c,(,c,d,),b,),，即,m,|(,ac,bd,),，故,ac,bd,(mod,m,),。,(3),因为,a,b,(mod,m,),，则存在整数,q,使得,a,b,mq,。于是：,a,n,b,n,(,b,mq,),n,b,n,(,b,n,b,n-,1,(,mq,),1,b,1,(,mq,),n-,1,(,mq,),n,),b,n,mp,，其中,p,是一整数。,所以,a,n,b,n,(mod,m,),。,(4),由,(1),和,(3),可证。,定理,若,ac,bc,(mod,m,),，且,(,c,，,m,),d,，则,a,b,(mod,m,/,d,),证明,由,(,c,，,m,),d,得,(,c,/,d,，,m,/,d,),1,。由,ac,bc,(mod,m,),得,m,|(,ac,bc,),，于是,(,m,/,d,)|(,a,b,)(,c,/,d,),。又,(,c,/,d,，,m,/,d,),1,，从而,(,m,/,d,)|(,a,b,),。故,a,b,(mod,m,/,d,),。,例,1,求,3,406,写成十进制数时的个位数。,解,因为,3,2,1(mod 10),，,3,4,1(mod 10),，所以,3,404,1(mod 10),。因此，,3,406,3,404,3,2,9(mod 10),。所以个位数为,9,。,例,2,：求使,2n+1,能被,3,整除的一切自然数,n.,孙子定理和大衍求一术,