初等数论一-夏子厚

1、初等数论(一)NumberTheory（Chap1）,初始版：信阳职业技术学院夏子厚修改：贾祥雪,为什么学数论,有用在研究函数，尤其是周期函数的时候经常性要用到。大学学习抽象代数及其后续课程的基础计算机专业的必修课！尤其应用到算法和密码两大领域好玩，简单，美自主招生、竞赛中考数论,为什么要这样学？,为什么不能直接讲一堆题目，从一个个题目中学习方法和技巧？为什么那么多字母，没几个具体数字？为什么很多东西还需要证明?为什么证明看上去那么纠结，让人觉得多此一举?为什么学习的顺序和小学不一样?,如何能学好数论,最好对数字的一些特征比较敏感，如质数、合数、约数、倍数、完全平方数、完全立方数、公约数、公倍

2、数等等。不要因为能解具体数的题目而不学抽象的通用方法。要学会符号语言。要会逻辑清晰地使用符号语言进行论证最重要的是，要理清知识之间的联系和来龙去脉，构建知识网络。初等数论有多种构建知识网络的方法，在学完后建议自己尝试用不同的方法进行构建,初等数论课程内容,第一章整除性质第一节整除与带余除法第二节最大公因数第三节最小公倍数第四节辗转相除法第五节算术基本定理第六节函数X、X的性质及其应用,初等数论课程内容,第二章不定方程第一节二元一次不定方程第二节多元一次不定方程第三节勾股数x2y2=z2,初等数论课程内容,第三章同余性质第一节同余的概念及其基本性质第二节完全剩余系第三节欧拉函数与简化剩余系第四节

3、欧拉定理与费马定理,初等数论课程内容,第四章同余方程第一节一次同余方程第二节孙子定理（中国剩余定理）第三节质数模的同余方程第四节二次同余方程与平方剩余第五节勒让德符号与二次互反律第六节雅可比符号,第一章整数性质,教学目的和要求（1）深刻理解整除、最大公因数、最小公倍数、质数的概念，正确理解带余数除法和算术基本定理的意义及作用。（2）掌握并能直接运用辗转相除法求最大公因数。（3）熟练掌握整除、质数、最大公因数和最小公倍数的基本性质，理解并掌握函数x、x的概念和基本性质，会求n!的标准分解式（n较小）。,第一节整除与带余数除法,定义1设a，b是整数，b0，如果存在整数q，使得a=bq成立，则称b整

4、除a或a被b整除，此时a是b的倍数，b是a的因数（约数或除数），并且记作：ba；如果不存在整数q使得a=bq成立，则称b不能整除a或a不被b整除，记作：ba。,第一节整除与带余数除法,定理1下面的结论成立：(1)ab，bcac；（传递性）(2)ma，mbm(ab)(3)mai，i=1,2,nma1q1a2q2anqn，此处qiZ（i=1,2,n）。,第一节整除与带余数除法,注：abab；babcac，此处c是任意的非零整数；ba，a0|b|a|；ba且|a|0，则存在唯一的两个整数q和r，使得a=bqr，0rb。(1)此外，ba的充要条件是r=0,第一节整除与带余数除法,证明：存在性作整数序列

5、：，-3b，-2b，-b，0，b，2b，3b，.则a必在上述序列的某两项之间，即存在整数q，使得：qba(q+1)b成立，令a-qb=r，则a=bq+r，且0rb。,第一节整除与带余数除法,唯一性假设有两对整数q，r与q，r都使得式(1)成立，即a=qbr=qbr，0r,rb，则(qq)b=rr，0|rr|b，(2)因此由b|rr|知rr=0，r=r再由式(2)得出q=q从而q和r是唯一的。,第一节整除与带余数除法,定义2称式(1)中的q是a被b除的商，r是a被b除的余数。我们设b=15，则：当a=255时，a=17b+0,r=015,而q=17;当a=417时，a=27b+12,r=1215

6、,而q=27;当a=-81时，a=-6b+9,r=915,而q=-6。,第一节整除与带余数除法,由定理2可知，对于给定的正整数b，可以按照被b除的余数将所有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究（我们将在第三章同余性质里讨论）。,第一节整除与带余数除法,例1任意给出的五个整数中，必有三个数之和被3整除。证明设这五个数是ai，i=1,2,3,4,5，记ai=3qiri，0ri，所以式(1)中只包含有限个等式。,第四节辗转相除法,如（1）：a=1859,b=15731859=11573+2861573=5286+143286=2

7、143+0如（2）：a=169,b=121169=1121+48121=248+2548=125+2325=123+223=112+12=21+0,第四节辗转相除法,定理1若a，bZ，则（a，b）=rn证明：从(1)式可见，rn=(rn1,rn)=(rn2,rn1)=(r1,r2)=(b,r1)=(a,b)。推论1.1a，b的公因数与（a，b）的因数相同。,第四节辗转相除法,例1求（1859，1573）解：（1859，1573）=（1859，1573）=（286，1573）=（286，143）=143例2求（169，121）解：（169，121）=（48，121）=（48，25）=（23，25

8、）=1,第四节辗转相除法,例3证明：若n是正整数，则是既约分数。解由定理1得到(21n4,14n3)=(7n1,14n3)=(7n1,1)=1。,第四节辗转相除法,定理2设a，b是任意两个不全为零的整数，（）若m是任一正整数，则（am，bm）=（a，b）m（）若是a，b的任一公因数，则（，）=特别地,=1。,第四节辗转相除法,证明：当a,b有一个为零时，定理显然都成立。今设ab0。由前两节知，（am,bm）=(|a|m,|b|m),（a，b）m=（|a|，|b|）m。从而不妨设a0，b0。在辗转相除法（1）式中两边同乘以m，即得：,第四节辗转相除法,am=（bm）q1r1m，0r1mbm，bm

9、=（r1m）q2r2m，0r2mr1m，rn2m=（rn1m）qnrnm，0rnmrn-1m，rn1m=（rnm）qn+1rn+1m，rn+1m=0。由定理1得，（am,bm）=rnm=（a，b）m,第四节辗转相除法,推论2.1(ma1,ma2,man)=|m|(a1,a2,an)。m0推论2.2记=(a1,a2,an)，则=1,第四节辗转相除法,例4记Mn=2n1，证明：对于正整数a，b，有(Ma,Mb)=M(a,b)证明：作辗转相除：a=bq1r1，0r1b，b=r1q2r2，0r2r1，rn2=rn1qnrn，0rn1，否则a是质数因q是a的除1外最小正因数，所以qa1，q2qa1a。故

10、q。注：由定理1易得：若大于1的整数a不能被任何适合q的质数q整除，则a必为质数。,第五节算术基本定理,我们容易得到如下结论：定理2若p是一质数，a是任一整数，则（p,a）=1或pa。推论2.1设a1,a2,an是n个整数，p是一质数，若pa1a2an，则存在1kn,使得pak。,第五节算术基本定理,定理3(算术基本定理)任何大于1的整数都可以表示成若干个质数的乘积。即任何大于1的整数ap1p2pn，p1p2pn，其中p1,p2,pn是质数，并且若aq1q2qm，q1q2qm，其中q1,q2,qm是质数，则m=n，qipii=1,2,n。（这里不再给予证明）,第五节算术基本定理,推论3.1任何

11、大于1的整数a能够唯一地表示成a=，其中p1,p2,pk是质数，p1p2pk，1,2,k是正整数。使用推论3.1中的记号，称a=是a的标准分解式，其中pi（1ik）是质数，p1p21，an1是质数，则a=2，并且n是质数。3、设a，b，c是整数，证明：(a,b,c)=(a,b),(a,c)。,第五节函数x，x及其在数论中的一个应用,定义1设x是实数，以x表示不超过x的最大整数，称它为x的整数部分，又称x=xx为x的小数部分。如：请大家画出x和x的图像，分析其性质。,第五节函数x，x及其在数论中的一个应用,定理1设x与y是实数，则(1)x=x+x(2)x1xxx+10x1(3)若n是整数，则nx

12、=nx,nZ；(4)x+yxyx+yx+y(5)x=；,第五节函数x，x及其在数论中的一个应用,(6)若b是正整数，那么对于任意的整数a，有(7)设a与b是正整数，则在1,2,a中能被b整除的整数有个。,第五节函数x，x及其在数论中的一个应用,证明能被b整除的正整数是b,2b,3b,，因此，若数1,2,a中能被b整除的整数有k个，则kba(k1)bkn,则=0，故上式只有有限项不为零，因而有意义。,第五节函数x，x及其在数论中的一个应用,推论2.1设n是正整数，则n!=其中表示对不超过n的所有质数p求积。推论2.2设n是正整数，1kn1，则贾宪数N。若n是质数，则n，1kn1。,第五节函数x，x及其在数论中的一个应用,例1求最大的正整数k，使得10k199!。解由定理2，199!的标准分解式中所含的5的幂指数是=47，所以，所求的最大整数是k=47。,第五节函数x，x及其在数论中的一个应用,例2设与是实数，则22。(1)解设=x，0x1，=y，0y1，则=22xy，(2)22=222x2y(3),第五节函数x，x及其在数论中的一个应用,如果xy=0，那么显然有xy2x2y；如果xy=1，那么x与y中至少有一个不小于1/2，于是2x2y1=xy。因此无论xy=0或1，都有xy2x2y由此及式(2)和式(3)可以推出式(1)。,第五节函数x，x及