您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 商业计划书 > 中科大夏令营――整数与多项式
1整数与多项式一整数记正整数集(自然数集)、整数集、有理数集、实数集、复数集分别为*,,,,.数集,,分别对数的加、减、乘、除法(除数不为0)封闭,分别称为有理数域、实数域、复数域.而整数集对加法、减法、乘法封闭,即整数的和、差、积仍是整数;但对于除法不封闭,也称为整数环.1.整除带余除法设,ab,0b.若存在c,使得abc,则称b整除a,记作|ba;且称b为a的约数(或因数,因子),a为b的倍数.若不存在c,使得abc,则称b不整除a,记作|ba.整除具有以下性质:1)||,(0)abacbcc2)|,||,abbcac3)|()|()abab,4)|,0||||abbab.定理1(带余除法)设,ab,0b.则存在唯一的,qr,使得abqr,且0||rb;其中q叫做a除以b的商,r叫做a除以b的余数.于是,|baa除以b的余数为0.习题1(1)对实数x,定义[]x为不大于x的最大整数,即1[]xxx.证明:当整2数0b时,整数a除以b的商q等于[]ab.当0b时,试给出商q的表达式.(2)设整数1q.证明:(i)每个正整数n可唯一地表示为10kknaqaqa,其中整数ia是满足01iaq,1,2,,ik;称这一表示为n的q进表示,ia称为q进表示中的数码.(ii)1[][],0iiinnaikqq.(3)设,,xyz是整数,且11整除725xyz,证明:11整除3712xyz.2.最大公约数与最小公倍数设,ab,称整数d是a与b的最大公约数,记作(,)ab,如果d满足:(1)d是a与b的公(共)约数,即|,da|,db且(2)d是a与b的所有公约数中最大的一个.若(,)1ab,则称,ab是互素的.设,ab,称D是a与b的最小公倍数,记作[,]ab,如果D满足:(1)D是a与b的公(共)倍数,即|,aD|,bD且(2)D是a与b的所有正公倍数中最小的一个.最大公约数(,)ab的欧几里德算法(辗转相除法):用b除a:00abqr,且00||rb;用0r除b:011brqr,且100rr;用1nr除2nr:21nnnnrrqr,且10nnrr;用nr除1nr:11nnnrrq.3由于0110nrrr,有限步后,余数1nr必为0.于是有000011(,)(,)(,)(,)(,)nnnabbqrbrbrrrrr.注意到,由上算法还可得到不定方程(,)axbyab的一组整数解,xy:由上算法的倒数第二步得21(,)nnnnabrrrq,再用倒数第三步中的1321nnnnrrrq代入上式,得213(,)(1)nnnnnabrqqrq,如此进行下去可得方程(,)axbyab一组整数解,xy.即有定理2(Bezout)设(,)abd,则存在,xy,使得axbyd;特别的,若(,)1ab,则存在,xy,使得1.axby例0120132356621263630961323015303020qabqqrrqrr201201220122120122120122(,)2(1)()(1)(1)((1))11314((1))(541)21662412621264826462abrrrqrqqbqabqqqbqaqqbqqqqxqqyqqqqaxby类似的,可定义多个整数,,,abc的最大公约数、最小公倍数,及互素,分4别记作(,,,)abc,[,,,]abc,(,,,)1abc.由于(,,,)((,),,)abcabc,求两个以上的整数的最大公约数归于求两个整数的最大公约数,且有定理3若(,,,)abcd,则存在,,,xyz,使得.axbyczd特别的,若(,,,)1abc,则存在,,,xyz,使得1axbycz.习题2(1)证明:(i)(,,,)((,),,)abcabc.(ii)[,,,][[,],,]abcabc.(iii)(,)[,]||ababab.(2)证明:整数,ab的任一公约数整除它们的最大公约数,它们的最小公倍数整除它们的任一公倍数.(3)设a,b是不为0或1的整数.证明,存在整数x,y,使得(,)axbyab,且0||||,0||||xbya.(4)设不全为零.证明:(i)方程axbyc有整数解x,y的充要条件是(,)|abc;(ii)若00,xxyy是不定方程axbyc的一组解(叫做特解),则方程的全部解(叫做通解)为00,,(,)(,)baxxtyyttabab.(5)设,ab为正整数且(,)1ab.证明:当nabab时,方程axbyn有非负的整数解;当nabab时,方程没有非负的整数解;当nabab时呢?5(6)设J是的非空子集,称J是的理想,如果它具有性质:(i)对于任意,abJ,有abJ;(ii)对于任意aJ和c,有acJ.证明:理想J或者为{0},或者存在唯一的正整数,d使得{|}Jdcc;此时,称J为由d生成的理想,记作()Jd.(7)设()Ic,()Jd是的理想,记{|,},{|,}IJIJIJIJ.证明:(i)|IJdc,(ii)((,))IJcd,(iii)([,])IJcd,(iv)(1)(,)1IJcdIJIJ.习题2.(6)的应用(纸币):设2,5ab.当3nabab时,有非负的整数解:12345678910x12031420y00101012用1元,2元,5元的纸币,至多3张即可支付1-10元的货币.整系数不定方程axbyc有整数解的几何意义是平面直线axbyc过整点(,),xy其中,xy.2011年高考安徽理科数学卷的(15)题涉及这一问题,但较上问题容易.(15)在平面直角坐标系中,如果x与y都是整数,就称点(x,y)为整点。下列命题中正确的是.(写出所有正确的编号)。①存在这样的直线,既不与坐标轴平行又不经过任何整点②如果k与b都是无理数,则直线y=kx+b不经过任何整点6③直线l经过无穷多个整点,当且仅当l经过两个不同的整点④直线y=kx+b经过无穷多个整点的充分必要条件是:k与b都是有理数⑤存在恰经过一个整点的直线解:①对:0.5xy,②错:2(1)yx过整点(1,0),③对:以整点为顶点的矩形的对角线,④错:0.5xy,⑤对:2yx.3.素数与合数设正整数1p.若p的正约数只有1和p自身,则称p是素数(或质数),否则称p是合数.定理4(欧几里德,公元前3世纪)素数有无穷多个.证明:反证.假设素数只有有限个,设为12,,,tppp.考虑121tnppp,必有素约数,设为某个ip.于是|ipn,从而|1ip,这矛盾.记()x为不超过x的素数的个数.关于素数的分布状况有以下结果:a)(),x素数有无穷多个;b)()0,xx素数与正整数相比几乎为0;c)()1/lnxxx,()x与lnxx相比几乎相等.x()xlnxx10316814510412291086(引自华罗庚《数论导引》)105959286861067849872382107664579620417定理5设p为素数,,.ab则1)(,)1pa,或|.pa2)若|,pab则|pa,或|.pb7证明1)因(p,a)是p的正约数,从而(p,a)=1或p,即(p,a)=1,或|.pa2)否则,由1),(,)1pa,且(,)1pb.由定理,存在,,,xyzw,使得1axpy,1.bzpw两式相乘得()1abxzpaxzbyzpyw,于是,(,)1abp,这与|pab矛盾.定理6(唯一因子分解定理,算术基本定理)(1)每个大于1的整数n都可分解为有限个素数的积:12tnppp,其中12,,,tppp是素数.(2)若不计素因子在乘积中的次序,(1)中的分解方式是唯一的.证明(1)n至少有一个大于1的约数,其中最小一个必是素数,记为1p.设11npn.对1n用第二型归纳即得.(2)又若12snqqq,其中12,,,sqqq是素数,则1p整除12sqqq,由定理4,可设1p整除1q,从而11pq.消去11pq,得22tsppqq.用第二型归纳法即得.于是,任一整数n可唯一的表示为1212,teeetnppp其中1,12,,,tppp是互不相同的素数,12,,,teee为正整数.上式称为整数n的(素因子)标准分解式.定理7设,ab是正整数,1212,seeesappp81212,sfffsbppp其中12,,sppp是互不相同的素数,12,,,,seee12,,,sfff为非负整数.则1122121),ssefefefsabppp1122122)/,ssefefefsabppp1122min{,}min{,}min{,}123)(,),ssefefefsabppp4)(,)100,1,,iiabefis或1122max{,}max{,}max{,}125)[,],ssefefefsabppp11226)|,,,.ssabefefef推论8设整数1n.记()n为n的正约数的个数,()n为n的所有正约数的和.1212teeetnppp是n的标准分解式.则(1)12()(1)(1)(1)tneee,1111111()11teettppnpp;(2)(积性)若(,)1mn,则()()()mnmn,()()()mnmn.证明只证11212111111212000111111001()()11()().11ttiiiittttetteeititeeeetttnpppppppppppp习题3(1)证明:设整数2n.若n不被不超过n的素数整除,则n是素数.(2)设整数1n.证明n与!n之间必有素数,由此证明素数有无穷多个.(3)证明{43|}mm中有无限个素数.(4)设,,,abcd是正整数,满足abcd.证明4444abcd不是素数.(5)证明:(,[,])[(,),(,)]abcabac,[,(,)]([,],[,])abcabac.94.同余、同余式设m是一个固定的非零整数,,ab,若|()mab,则称a与b模m同余(或a模m同余于b),记作(mod)abm;称为(模m)的同余式.若|()mab;则称a与b模m不同余,记作(mod)abm.由于(mod)(mod())abmabm,以下只考虑m为正整数的情形.同余具有以下性质:1)(mod),aam(反身性)2)(mod)(mod),abmbam(对称性)3)(mod),(mod)(mod),abmbcmacm(传递性)4)(mod),(mod)(mod),(mod),abmcdmacbdmacbdm5)(mod)(mod),(,)macbcmabcm6)(mod),|(mod),abmdmabd7)(mod)(mod),abmadbdmd其中0d,18)(mod),1,,,(mod[,,])ikabmikabmm.例1设122010,,,xxx都是1或1.证明:122010220100.xxx解改写为12201011222010201012201022010(||)2(||)2010(||)(||2||2010||).xxxxxxxxxxxx由于||iixx等于0或2,故1122
本文标题:中科大夏令营――整数与多项式
链接地址:https://www.777doc.com/doc-5503298 .html