初等数论第一章整除.ppt

2019/11/2014:22,初等数论教师：何艳,2019/11/2014:22,数论的基本内容,按照研究方法的不同，数论可分为初等数论解析数论代数数论几何数论,2019/11/2014:22,参考书目,1、南基洙主编初等数论；2、柯召、孙琦编著数论讲义，高等教育出版社；3、闵嗣鹤、严士健编初等数论，高等教育出版社；4、郑克明主编初等数论，西南师范大学出版社。,2019/11/2014:22,初等数论,第一章整除1自然数与整数,2019/11/2014:22,归纳原理,设S是N的一个子集，满足条件：()1S;()如果nS，则n+1S,那么，S=N.,2019/11/2014:22,定理1数学归纳法,设P(n)是关于自然数n的一种性质或命题.如果()当n=1时，P(1)成立；()由P(n)成立必可推出P(n+1)成立，那么，P(n)对所有自然数n成立.,2019/11/2014:22,定理2最小自然数原理,设T是N的一个非空子集.那么，必有t0T,使对任意的tT有t0t，即t0是T中的最小自然数.,2019/11/2014:22,定理3最大自然数原理,设M是N的非空子集.若M有上界，即存在aN,使对任意的mM有ma,那么必有m0M，使对任意的mM有mm0，即m0是M中的最大自然数。,2019/11/2014:22,定理4第二数学归纳法,设P(n)是关于自然数n的一种性质或命题.如果()当n=1时，P(1)成立；()设n1.若对所有的自然数mn,P(m)成立，则必可推出P(n)成立，那么,P(n)对所有自然数n成立.,2019/11/2014:22,定理5鸽巢原理,设n是一个自然数.现有n个盒子和n+1个物体.无论怎样把这n+1个物体放入这n个盒子中，一定有一个盒子中被放了两个或两个以上的物体。,2019/11/2014:22,2整除,2019/11/2014:22,定义1,设a，b是整数，a0，如果存在整数q，使得b=aq，则称b可被a整除，记作ab，且称b是a的倍数，a是b的约数(因数、除数)；如果不存在整数q使得b=aq成立，则称b不被a整除，记为ab。被2整除的数称为偶数，不被2整除的称为奇数,2019/11/2014:22,定理1下面的结论成立：,()a|b(-a)|ba|(-b)(-a)|(-b)|a|b|；()ab，bcac；()ab,ac对任意x、y,有abx+cy,一般地，abi，i=1,2,kab1x1b2x2bkxk，此处xi（i=1,2,k）是任意的整数；()abacbc，c是任意的非零整数；()ab且baa=b；()ab，b0|a|b|；ab且|b|1是合数的充要条件是a=de,11,q是不可约数且d|q,则d=q.定理4若a是合数，则必有不可约数p|a.,2019/11/2014:22,定理5设整数a2,那么a一定可表为素数的乘积,(包括a本身是素数)，即a=p1p2ps其中pj（1js)是素数.证明当a=2时，结论显然成立。假设对于2ak，式(1)成立，我们来证明式(1)对于a=k1也成立，若k1是素数，式(1)显成立.如果k1是合数，则存在素数p与整数d，使得k1=pd.由于2dk，由归纳假定知存在素数q1,q2,ql，使得d=q1q2ql，从而k1=pq1q2ql.从而由归纳法推出式(1)对任何大于1的整数a成立。证毕。,2019/11/2014:22,推论,任何大于1的合数a必有一个不超过a1/2的素因数。证明由于a是合数，故存在整数b和c使abc,其中:1ba,1ca.若b和c均大于a1/2,则abca1/2a1/2a,这是不可能的.因此b和c中必有一个小于或等于a1/2.,2019/11/2014:22,例5写出不超过100的所有的素数.,解将不超过100的正整数排列如下：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100,2019/11/2014:22,按以下步骤进行：,()删去1，剩下的后面的第一个数是2，2是素数；()删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；()再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；()再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数；照以上步骤可以依次得到素数2,3,5,7,11,.由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数.,2019/11/2014:22,在例5中所使用的寻找素数的方法,称为Eratosthenes筛法.它可以用来求出不超过任何固定整数的所有素数.在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的.,2019/11/2014:22,定理7.(Euclid)素数有无穷多个.,证明：(反证法)假设素数是有限多个,共有n个,令它们是p1,p2,pn,并令a=p1p2pn+1.若a是素数,则因api，其中10,我们有ma1,mak=ma1,ak,2019/11/2014:22,3带余除法与辗转相除法,2019/11/2014:22,定理1带余数除法,设a与b是两个整数，a0,则存在唯一的两个整数q和r，使得b=aqr，0r|a|(1)证明存在性若ab，b=aq，qZ，可取r=0.若ab，考虑集合A=bka；kZ，在集合A中有无限多个正整数，设最小的正整数是r=bk0a，则必有0|a|，即bk0a|a|，bk0a|a|0，这样,在集合A中,又有正整数r1=bk0a|a|2是奇数.证明：()一定存在正整数da-1,使得a|2d-1.()设d0是满足()的最小正整数d.那么，a|2h-1(hN)的充要条件是d0|h.()必有正整数d使得（2d-3,a)=1.,2019/11/2014:22,定理4(Euclid)欧几里德算法.,设a,b是给定的两个整数，b0,ba.我们一定可以重复定理1得到下面的等式：a=bq1+r1,0rl|b|b=r1q2+r2,0r2r1r1=r2q3+r3,0r3r2.rn-2=rn-1qn+rn,0rnrn-1rn-1=rnqn+1+0则(a,b)=rn.,2019/11/2014:22,证明:由于|b|r1r2rn0,故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式,即rn+1=0.根据前面定理可知：(a,b)=(b,r1)=(rn-1,rn)=(rn,0)=rn.欧几里德算法也称辗转相除法.,2019/11/2014:22,在Euclid算法中,由:rn=rn-2-rn-1qn,rn-1=rn-3-rn-2qn-1,得rn=rn-2(1+qnqn-1)-rn-3qn,再将rn-2=rn-4-rn-3qn-2代入上式,如此继续下去,最后得到:rn=sa+tb,其中s和t是整数.于是有(a,b)是a和b线性组合表示定理.定理5()若任给整数a,b,则存在整数x和y,使得(a,b)=ax+by.容易证明下面结论()a和b的公因数整除(a,b).,2019/11/2014:22,例6,用欧几里德算法求(1997,57).用1997和57的线性组合表示(1997,57)求1997和57的所有公因数解用下划线标识余数19975735+257228+12l2+0因此,(1997,57)=l,即1997和57是互素的.,2019/11/2014:22,1=57-228=57-(1997-5735)28=-281997+(57+573528）=-281997+98157由于1997和57是互素的,公因数只有1和-1.,2019/11/2014:22,例7,设m,n是正整数.证明（2m-1,2n-1)=2(m,n)-1,2019/11/2014:22,4最大公因数理论,2019/11/2014:22,定理1aj|c(1jk)的充要条件是a1,ak|c,证明：充分性显然.必要性，设a1,ak=m.c是a1,ak的任一公倍数,利用带余除法得:c=mq+r,0rm,aj|c,aj|m,aj|r,(1jk).故a1|r,ak|r,即r是a1,ak的公倍数.但由于:1rm与m是a1,ak的最小公倍数发生矛盾,故:r=0,即:cmq.故m|c.即a1,ak|c,2019/11/2014:22,定理2,设D是正整数.那么D=（a1,a2,ak）的充要条件是：()D|aj(1jk);()若daj(1jk),则d(a1,a2,ak).这个结论表明：公约数一定是最大公约数的约数。,2019/11/2014:22,定理3,(ma1,ma2,mak)=|m|(a1,a2,ak).定理4()(a1,a2,ak)=(a1,a2),a3,ak)；()(a1,a2,ak+r)=(a1,ak),(ak+1,ak+r)；推论（a1,a2)(b1,b2)=(a1b1,a1b2,a2b1,a2b2),2019/11/2014:22,定理5,若(m,a)=1，则(m,ab)=(m,b).证明:(m,b)=(m,(m,a)b)=(m,mb,ab)=(m,ab).推论若(a,bi)=1,1in,则(a,b1b2bn)=1.,2019/11/2014:22,定理6,对于任意的整数a，b，m，下面的结论成立：()由mab及(m,a)=1可以推出mb；()由m1n，m2n及(m1,m2)=1可以推出m1m2n.一般地，若m1,m2,mk两两互素，及mjn(1jk），则m1m2mkn.证明：()(m,a)=1，则(m,ab)=(m,b)，由mab，(m,ab)=|m|，故(m,b)=|m|，从而mb.()m1n知n=m1n1,m2n,即m2m1n1,又(m1,m2)=1,知m2n1，因而m1m2n.,2019/11/2014:22,定理7,设a1和a2是正整数,且(a1,a2)=d,a1,a2=m,则a1a2md.,2019/11/2014:22,例1,设p是素数.证明：()p|，1jp-1()对任意的正整数a,p|ap-a;()若(p,a)=1，则p|ap-1-1.例2证明：()(a,uv)=(a,(a,u)v);()(a,uv)|(a,u)