Chapter7数论1

离散数学（数论基础篇）,DiscreteMathematics（NumberTheory）,计算机科学及信息类专业基础教材,内蒙古大学计算机学院:段禅伦,斯勤夫,数论基础,本章主要介绍整数的整除性和因数分解等内容在本章或下一章中，如无特别说明，常以小写英文字母，或有时标以足码或肩码表示整数当几个字母写在一起时，表示它们相乘，如:abc=abc;但注意数目字写在一起不表示相乘，如168不是168而是一百六十八当数目字和字母写在一起时，则表示该数目字和字母相乘,如168abc168abC.,7.1因数和倍数,定义7.1.1设a,b为整数，a0.若有一整数q,使得b=aq,则称a是b的因数为是a的倍数;并称a整除b,记为a|b,可形式地表示为:a|b:=(q)(b=aq)若a不能整除b，记为ab.若b=aq,而a既非b又非1,则称a是b的真因数.,7.1因数和倍数,关于整除，显然有下列定理：定理7.1.2对所有a,1|a.对所有a,a|0.对所有a,a|a.若a|b且b|c,则a|c.若a|b,则对任意的c,有ac|bc.若ac|bc且c0,则a|b.,7.1因数和倍数,若a|b且a|c,则对任意的m,n,有a|(bm+cn).若a|b,则b=0或|a|b|,其中|a|是a的绝对值,当a0时|a|=a;当a0时|a|=-a.若a|b,则(-a)|b,a|(-b),(-a)|(-b),|a|b|.证明只证明,余下不难证明.因为a|b且a|c,故b=aq1和c=aq2.于是,bm+cn=a(q1m+q2n),所以,a|(bm+cn).,7.1因数和倍数,定理7.1.2若a是b的真因数,则1|a|b|.定理7.1.3若a为是整数,且|a|b|,|b|a|,则a=0.证明因为|b|a|,故有整数q,使得|a|=|b|q.若|a|=0,则a=0.若|a|0,则由于00,则由q是整数而有q1.由|a|=|b|和q1有|a|b|,这与|a|b|矛盾,故q=0;若q=0和|a|=|b|q有a=0.,7.1因数和倍数,定理7.1.4(带余除法)若a为是二个整数,b0,则唯一存在二个整数q和r,使得下式成立:a=bq+r,0r|b|.证明考虑两种可能：只证明.存在一整数q,使得a=bq,故r=0,定理成立.,7.2素数和合数,在正整数中,1只能被它本身整除.任何大于1的整数都至少能被1和它本身整除定义7.2.1一个大于1且只能被1和它本身整除的整数,称为素数;否则,称为合数.由该定义可知，正整数集合可分三类:素数、合数和1.素数常用户或p或p1,p2,来表示.,7.2素数和合数,定义7.2.2若正整数a有一因数b,而b又是素数,则称b为a的素因数例:12=34,其中3是12的素因数,而4则不是.定理7.2.1若a是大于1的整数,则a的大于1的最小因数一定是素数.证明若a是素数,显然a的大于二的最小因素就是素数a;若a是合数,则除1和a外还有其它的因数，令b是这些正因数中最小者,可以证明b不是合数而是素数,若其不然,b必有大于1且不等于b的因数c,于是由c|b和b|c可知c|a,即c是a的因数,又有1cb,这与假设b是a的大于1的最小因数相矛盾故b不是合数而是素数因此，a的大于1的最小因数b是素数,7.2素数和合数,本定理说明了:任何大于1的整数均可被一素数整除,或者说都至少有一素因数.观察一正整数a是否素数,要用小于a大于1的整数一一来试除吗？不要.,7.2素数和合数,定理7.2.2若a是大于1的整数而所有小于或等于人的素数都不能整除a,则a是素数.证明首先证明,若a不能被大于1且小于或等于人的整数整除,则a是素数.假设是合数且abe,其中b和c都是大于1的整数,由于a不能被大于1且小于或等于的整数整除,所以b,c,于是,可得bc.=a,这与bc=a矛盾.因此,若a不能被大于三且小于或等于的整数整除，则是素数,7.2素数和合数,由上可知,若a是合数,则a一定有大于1且小于或等于人的因数.由定理7.2.1知,a的大于1的最小因数一定是素数,故本定理得证.素数有多少？公元前三世纪,古希腊数学家欧几里德Euclid就证明了素数有无穷多个.,7.2素数和合数,定理7.2.3(Euclid)素数有无穷多个.证明(反证法)假设素数是有限多个,共有n个,令它们是p1,p2,pn,并令a=p1p2pn+1.若a是素数,则因api;其中1in,故素数个数最少是n+1个,这与假设素数个数为n个矛盾.若a不是素数,则由定理7.2.2知,l的大于1的最小因数b是素数.由于pi|p1p2pn,但pi不能整除1,故pi不能整除a,因此bpi,其中1in,那么a也为素数.所以在p1,p2,pn,还有素数,这也与已知共有n个素数矛盾.,7.2素数和合数,下面给出关于合数的两个定理定理7.2.4若a是合数,则a有一因数d满足:1da1/2证明由于a是合数，故存在整数b和c使abc,其中:1ba,1ca.若b和c均大于a1/2,则abca1/2a1/2a,这是不可能的.因此b和c中必有一个小于或等于a1/2.,7.2素数和合数,定理7.2.5若a是合数,则a必有一素因数小于或等于a1/2.证明由定理7.2.4知a有一个因数,令它为d，满足1b,a=bq+r00,则存在整数x和y,使得(a,b)=ax+by.显然有下面推论推论a和b的公因数整除(a,b).定理7.3.3也可用归纳法证之,作为思考题.,7.3最大公因数和最小公倍数,例7.3.1用欧几里德算法求(1997,57).用1997和57的线性组合表示(1997,57)求1997和57的所有公因数解用下划线标识余数19975735+257228+12l2+0因此,(1997,57)=l,即1997和57是互素的.,7.3最大公因数和最小公倍数,1=57-228=57-(1997-5735)28=-281997+(57+573528）=-281997+98157由于1997和57是互素的,公因数只有1.,7.3最大公因数和最小公倍数,定义7.3.2设a1,a2,an和m都是正整数,n2.若ai|m,1in,则称m是a1,a2,an的公倍数.在a1,a2,an所有公倍数中最小的那一个,称为a1,a2,an的最小公倍数,记为lcma1,a2,an(leastcommonmultipler)或者a1,a2,an.,7.3最大公因数和最小公倍数,定理7.3.4设a和b是正整数,且a,b=m.若m是a和b的公倍数,则m|m.证明显然1mm,利用带余除法得:m=mq+r,0r1,q为整数.令maa,m=aa”,m=bb,mbb”,其中a,a”,b,b”都是整数.假设:1rm，则由于:m-mq=r得到:a(a”-aq)=r,b(b”-bq)=r因为a”-aq和b”-bq都是整数,故a|r,b|r,即r是a和b的公倍数.但由于:1rm与m是a和b的最小公倍数发生矛盾,故:r=0,即:m”mq.,7.3最大公因数和最小公倍数,定理7.3.5设a和b是正整数,且(a,b)=d,a,b=m,则abmq.证明因ab是a和b的公倍数而m=a,b,故由定理7.3.4有ab=mq,其中q为正整数.于是得到:a/q=m/b,b/q=m/a.由于m/b和m/a都是正整数,所以a/q和m/q也都是正整数,即q|a,q|b,因而q是a和b的公因数.,7.3最大公因数和最小公倍数,令g是a和b的另一公因数,m=ab/g.由于a/g和b/g都是正整数和m=a(b/g)=(a/g)b,所以m是a和b的公倍数.由定理7.3.4知,叫m|m,即m/m是一个正整数.又由m/m=(ab/g)/(ab/g)=q/g得到g是q的因数.由于q是a和b的公因数,而a和b的任一公因数g都整除q,故q是a和b的最大公因数.,7.4整数分解唯一性定理,整数分解唯一性定理也称算术基本定理,在给出并证明该定理前,先介绍预备定理.定理7.4.1若p为素数,则a不能被p整除当且仅当:(p,a)=1证明因p为素数,故p只有二个正因数,即1和p.若(p,a)1,则只有(p,a)=1.反之,若(p,1)=1,则p和a是互素的,故a|c.,7.4整数分解唯一性定理,定理7.4.2设a,b,c都是正整数,若a|bc且a|bc,则a|c.证明因为b|bc和a|bc,故bc是a和b的公倍数.由于(a,b)=1和定理7.3.5知,a,b=ab,又由定理7.3.4得ab|bc,即bc/ab=c/a是一整数,故a|c.定理7.4.3设a,b,c都是正整数,且(a,b)=1,c|a,则:(b,c)=1证明假设(b,c)=d,且d1.于是d|b,d|c.由d|c,c|a有d|a.由于d|a,d|b,故d是a和b的公因数,但是dl,这与(a,b)=1矛盾,故:(b,c)=1.,7.4整数分解唯一性定理,定理7.4.4若a和b是正整数,且(a,b)=1,则(a,bc)=(a,c).证明假设(a,c)=d1;(a,bc)=d2.则d1|a,d1|c,d2|bc,由于dl|c得到d1|bc.由d1|a,d1|bc得d1也是a和bc的公因数,但d2=(a,bc),故d1d2.另外,由d2|a,(a,b)=1和定理7.4.3得到(d2,b)=1.由(d2,b)=1,d2|bc和定理7.4.2得到d2|c.由d2|a,d2|c得到d2也是a和c的公因数,但d1=(a,c),故d2d1.综上可知d1=d2,即(a,bc)=(a,c).,7.4整数分解唯一性定理,定理7.4.5设a和b1,b2,bn都是正整数,n2.若(a,b1)=(a,b2)=(a,bn)=1,则(a,b1b2bn)=1.证明由(a,b1)=1和定理7.4.4得到(a,b1b2bn)=(a,b2b3bn),再由(a,b2)=1和定理7.4.4得到(a,b2b3bn)=(a,b3b4bn),故:(a,b1b2bn)=(a,b2b3bn)=(a,b3b4bn)=(a,bn),7.4整数分解唯一性定理,定理7.4.6设a1,a2,an都是正整数,且p是素数.若p|a1a2an,则至少有一个ar,使得p|ar,其中1rn.证明假设ai不能被p整除,1in.从p是一素数和定理7.4.1得到(p,a1)=(p,a2)=(p,an)=1.所以由定理7.4.5得到(p,a1a2an)=1,据此和定理7.4.l得到a1a2an不能被p整除.这与题设p|a1a2an矛盾,故必有一ar,使得p|ar,其中1rn.,7.4整数分解唯一性定理,定理7.4.7设p1,p2,pn和p都是素数,n2.若p|p1p2pn,则至少有一个pr,使得p=pr.证明由p|p1p2pn和定理7.4.6知,至少存在一个pr,使得p|pr.由于pr是素数,故它只有二个正因数1和pr.由p1和p|pr,所以:p=pr.,7.4整数分解唯一性定理,定理7.4.8(整数分解唯一性定理)每个大于1的正整数a均可分解成有限个素数之积,并且若不计素因数的次序,其分解是唯一的.证明先证分解式的存在性.若a=2,则2为素数,从而2即所求分解式.现在假设小于a的每个正整数均可分解成有限个素数之积.考虑a,若a是素数,则证毕.否则a便有真因数d,而a=cd,其中c和d均是大于1的正整数,并且c和d均小于a.由归纳假设,c和d均有分解式c=p1p2pk和d=q1q2ql,其中p1,p2,pk,ql,q2,ql均是素数.因此a=cd=p1p2,pkqlql;即为所求的分解式,7.4整数分解唯一性定理,再证唯一性.当a=2时,分解式显然是唯一的.现设比a小的正整数其分解式均是唯一的.考虑正整数a,假设a有两个分解式a=plp2pk和a=q1q2ql,其中pl,p2,pk和q1,q2,ql都是素数.于是p1|q1q2ql,根据定理7.4.7知