初等数论一-夏子厚

初等数论(一)NumberTheory（Chap1）初始版：信阳职业技术学院夏子厚修改：贾祥雪为什么学数论•有用•在研究函数，尤其是周期函数的时候经常性要用到。•大学学习抽象代数及其后续课程的基础•计算机专业的必修课！尤其应用到算法和密码两大领域•好玩，简单，美•自主招生、竞赛中考数论为什么要这样学？•为什么不能直接讲一堆题目，从一个个题目中学习方法和技巧？•为什么那么多字母，没几个具体数字？•为什么很多东西还需要证明?•为什么证明看上去那么纠结，让人觉得多此一举?•为什么学习的顺序和小学不一样?如何能学好数论•最好对数字的一些特征比较敏感，如质数、合数、约数、倍数、完全平方数、完全立方数、公约数、公倍数等等。•不要因为能解具体数的题目而不学抽象的通用方法。要学会符号语言。•要会逻辑清晰地使用符号语言进行论证•最重要的是，要理清知识之间的联系和来龙去脉，构建知识网络。•初等数论有多种构建知识网络的方法，在学完后建议自己尝试用不同的方法进行构建《初等数论》课程内容•第一章整除性质•第一节整除与带余除法•第二节最大公因数•第三节最小公倍数•第四节辗转相除法•第五节算术基本定理•第六节函数[X]、{X}的性质及其应用《初等数论》课程内容•第二章不定方程•第一节二元一次不定方程•第二节多元一次不定方程•第三节勾股数x2y2=z2《初等数论》课程内容•第三章同余性质•第一节同余的概念及其基本性质•第二节完全剩余系•第三节欧拉函数与简化剩余系•第四节欧拉定理与费马定理《初等数论》课程内容•第四章同余方程•第一节一次同余方程•第二节孙子定理（中国剩余定理）•第三节质数模的同余方程•第四节二次同余方程与平方剩余•第五节勒让德符号与二次互反律•第六节雅可比符号第一节整除与带余数除法•定义1设a，b是整数，b0，如果存在整数q，使得•a=bq•成立，则称b整除a或a被b整除，此时a是b的倍数，b是a的因数（约数或除数），并且记作：ba；如果不存在整数q使得a=bq成立，则称b不能整除a或a不被b整除，记作：ba。|第一节整除与带余数除法•定理1下面的结论成立：•(1)ab，bcac；（传递性）•(2)ma，mbm(a±b)•(3)mai，i=1,2,,n•ma1q1a2q2anqn，•此处qi∈Z（i=1,2,,n）。第一节整除与带余数除法•注：①abab；②babcac，此处c是任意的非零整数；③ba，a0|b||a|；•ba且|a||b|a=0。④an-bn=(a-b)M1,n∈Zan+bn=(a+b)M2,n为奇数,M1,M2∈Z|第一节整除与带余数除法•定理2(带余数除法)•设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得•a=bqr，0rb。(1)•此外，ba的充要条件是r=0第一节整除与带余数除法•证明：•存在性作整数序列：•…，-3b，-2b，-b，0，b，2b，3b，….•则a必在上述序列的某两项之间，即存在整数q，使得：•qba(q+1)b•成立，令a-qb=r，则a=bq+r，且0rb。第一节整除与带余数除法•唯一性假设有两对整数q，r与q，r都使得式(1)成立，即•a=qbr=qbr，0r,rb，•则(qq)b=rr，0|rr|b，•…………………(2)•因此由b||rr|知rr=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,而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=3qiri，0ri3，i=1,2,3,4,5。第一节整除与带余数除法•分别考虑以下两种情形：•(ⅰ)若在r1,r2,,r5中数0，1，2都出现，不妨设r1=0，r2=1，r3=2，此时a1a2a3=3(q1q2q3)3可以被3整除；•(ⅱ)若在r1,r2,,r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1=r2=r3=r（r=0，1或2），此时a1a2a3=3(q1q2q3)3r可以被3整除。•综合(ⅰ)、(ⅱ)可知，所证结论成立。你能将上例推广？第一节整除与带余数除法•例2若ax0+by0是形如ax+by（x,y∈Z，a，b是两个不全为零的整数）的数中的最小正数，则•ax0+by0∣ax+by。第一节整除与带余数除法•证明：由于a,b不全为0，所以在整数集合•S={ax+by∣x,y∈Z}中存在正整数，因而有形如ax+by的最小正数ax0+by0。•对任意的x,y∈Z，由带余除法有•ax+by=（ax0+by0）q+r,0≤rax0+by0。•则r=(x-x0q)a+(y-y0q)b∈S，•由ax0+by0是S中的最小整数知r=0。•故ax0+by0∣ax+by。第一节整除与带余数除法•注：（1）设a1,a2,,an为不全为零的整数，以y0表示集合•A={y|y=a1x1a2x2anxn，xiZ，1in}•中的最小正数，则对于任何yA，y0y；特别地，y0ai，1in。（证明留给学生自己）•（2）此类题目的证明方法具有一般性，通常是针对所给的“最小正数”的概念进行反证法。第一节整除与带余数除法•思考与练习1.1•1、证明：maima1q1a2q2anqn，qi∈Z。i=1,2,,n•2、证明：6︱n(n+1)(2n+1)n∈N。•3、设a1,a2,,an为不全为零的整数，以y0表示集合A={y|y=a1x1anxn，xiZ，1in}中的最小正数，则对于任何yA，y0y；特别地，y0ai，1in。第二节最大公因数•定义1设a1,a2,,an是n（n≥2）个整数，若整数d是它们之中每一个的因数，则d就叫做a1,a2,,an的一个公因数；其中最大的一个公因数叫做a1,a2,,an的最大公因数。记为(a1,a2,,an)。•由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，且是正整数。第二节最大公因数•定理1若a1,a2,,an为任意n个不全为零的整数。则：•(1)a1,a2,,an与|a1|,|a2|,,|an|的公因数相同；•(2)(a1,a2,,an)=(|a1|,|a2|,,|an|)。•（证明了（1）也就证明了（2））•由定理1可知，在讨论(a1,a2,,an)时，不妨假设a1,a2,,an是正整数，以后我们就维持这一假设。第二节最大公因数•若(a1,a2,,an)=1，•则称a1,a2,,an是互质的；•若(ai,aj)=1，1i,jn，ij，•则称a1,a2,,an是两两互质的。•显然，a1,a2,,an两两互质可以推出(a1,a2,,an)=1，反之则不然，例如(2,6,15)=1，但(2,6)=2。第二节最大公因数•我们容易得到如下结论：•定理2若b是任一整数，则：•(1)0与b的公因数就是b的因数，反之，b的因数也就是0与b的公因数；(2)（0，b）=︱b︱。第二节最大公因数定理3若a，b，c是任意三个不全为零的整数，且a=bqc，其中q是非零整数，则a，b与b，c有相同的公因数，因而(a,b)=(b,c)。证明留给学生自己。第二节最大公因数•定理4对于任意的n个整数a1,a2,,an，记(a1,a2)=d2，(d2,a3)=d3，，(dn2,an1)=dn1(dn1,an)=dn，则：dn=(a1,a2,,an)。证明（1）dn是a1,a2,,an的一个公因数；（2）dn是a1,a2,,an的公约数中的最大者。（即：对于a1,a2,,an的任何公因数d，ddn）第二节最大公因数•证明：dn=(dn1,an)dnan，dndn1，dn1=(dn2,an1)dn1an1，dn1dn2，•dnan，dnan1，dndn2，dn2=(dn3,an2)dn2an2，dn2dn3•dnan，dnan1，dnan2，dndn3，d2=(a1,a2)dnan，dnan1，，dna2，dna1即dn是a1,a2,,an的一个公因数。第二节最大公因数•另一方面，对于a1,a2,,an的任何公因数d，由d2,,dn的定义，依次得出•da1，da2dd2，dd2，da3dd3，ddn1，danddn，•因此dn是a1,a2,,an的公约数中的最大者。•故dn=(a1,a2,,an)。第二节最大公因数•例1设a1,a2,,an为不全为零的整数，以y0表示集合•A={y|y==a1x1anxn，xiZ，1in}•中的最小正数，则y0=（a1,a2,,an）。niiixa1第二节最大公因数•证明：由于y0是集合A中的最小正数，故设d是a1,a2,,an的任意一个公因数，则d∣，所以d≤y0。又由本章第1节例2的注（1）知，y0ai，1in，因此y0也是a1,a2,,an的一个公因数。故y0一定是a1,a2,,an所有公因数中的最大正数。由此即得：y0=（a1,a2,,an）。niiiiniZxxay1000)1,(niiixay100第二节最大公因数•注：由于（a1,a2,,an）是集合A={y|y=a1x1anxn，xiZ，1in}中的最小正数，由此题的证明过程直接得到如下结论：设不全为零的整数a1,a2,,an的最大公因数是（a1,a2,,an），则存在整数，使得：a1t1antn=（a1,a2,,an）。第二节最大公因数由上我们容易得到：定理5（裴蜀（Bézout,1730-1783）恒等式）设a，b是任意两个不全为零的整数，则存在s，t∈Z，使得asbt=(a,b)第二节最大公因数推论5.1(a,b)＝1的充要条件是：存在s，t∈Z，使得asbt=1。此题可以推广为：推论5.2(a1,a2,,an)=1的充要条件是：存在整数x1,x2,,xn，使得a1x1a2x2anxn=1。第二节最大公因数•定理6若a，b，c是任意的三个整数，且(a,c)＝1，则•(1)ab，c与b，c有相同的公因数；•(2)（ab，c）＝（b，c）•上面假定了b，c至少有一个不为零。•（证明了（1）也就证明了（2））.第二节最大公因数•证明：（1）由题设及推论5.1，存在s，t∈Z，使得asct=1。•两边乘以b，即得：(ab)sc(bt)=b。•设d是ab与c的任一公因数，由上式得：•d︱b，因而d是b，c的一个公因数。反之b，c的任一公因数显然是ab与c的一个公因数。故第一部分获证。•（2）因为b，c不全为零，所以（b,c）是存在的，于是由（1）知（ab，c）存在，且•（ab，c）＝（b，c）第二节最大公因数•推论6.1若(a,c)=1，cab，则cb•推论6.2若(a,bi)=1，1in，•则(a,b1b2bn)=1•推论6.3若(ai,bj)=1，1in，1jm，•则(a1a2an,b1b2bm)=1第二节最大公因数•注：几个常