信安数学

2．1证明：若a是整数，则a3-a能被3整除。证明：a3-a=a(a2-1)=a(a+1)(a-1)又∵3个连续整数必有一个能被3整除∴命题成立2．2设(u,v)=1，试证(u+v,u-v)=1或2证明：设(u+v,u-v)=p有u+v=psu-v=pt(s,t∈z)∴u=p(s+t)p/2v=(s-t)p/2且(u,v)=1,则p=2或p=1∴(u+v,u-v)=2或1，即证2.3设f(x)=anxn+an-1-xn-1+…..a1x+a0是整系数多项式，证明若d｜b-c，则d｜f(b)-f(a)证明：f(b)-f(a)=an（bn-cn）+an-1（bn-1-cn-1）+…..a1(b-c)又bn-cn=(b-c)(bn-1+bn-2a+….+an-1)∴(b-c)|bn-cn∴b-c|f(b)-f(c)又d|b-c∴d|f(b)-f(a)2.4用Eratasthenes筛选法求出200以内的所有素数解：不超过14的素数有2，3，5，7，11，13，在2到200内依次删去2，3，5，7，11，13的倍数后，可求出所有200内的素数：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，5359，61，67，71，73，79，83，89，97，101，103，107，109，113123，127，129，131，133，137，139，141，149，151，157，161167，173，179，181，187，191，193，197，1992.5（1）证明2d-1≡a-1(moda)不存在∴2d-1(moda)的剩余类只能是0～a-2共a-1个数d取1～a-1也有a-1个数，故得证(2)289.377解：377=289*1+88289=88*3+2588=25*3+1325=13*1+1213=12*1+1则：(289，377)=1[289，377]=289*377/1=108953(3)20785，44350解：44350=20785*2+278020785=2780*7+13252780=1325*2+1301325=130*10+25130=25*5+525=5*5+0则(20785,,44350)=5[20785,44350]=20785*44350/5=184362950(4)20041,37516解：37516=20041*1+1747520041=17475*1+256617475=2566*6+20792566=2079*1+4872079=487*4+91487=91*5+3291=32*2+2732=27*1+527=5*5+25=2*2+12=2*2+0则(20041,37516)=1[20041,37516]=20041*37516/1=751858156(5)108,144,264,420,780解：144=108+36108=36*3+0(108,144)=36264=36*7+1236=12*3+0(36,264)=12420=12*35+0(12,420)=12同理(12,780)=12(108,144,264,420,780)=12[108,144,264,420,780]=108*144*264*420*780/36*12*12*12=81081002．7求下列各数的最大公因子和最小公倍数（1）621，437解：621=437﹡1+184437=184*2+69184=69*2+4669=46*1+2346=23*2+0∴（621，437）=23［621，437］=621*437/23=117992.8计算下列各数的正因子的个数，并求其所有正因子之和。(1)675解：675=33*52i(675)=(3+1)*(2+1)=12a(675)=30*51+3*5+32*5+33*5+31*52+30*52+32*52+33*52+30*50+31*50+32*50+33*50=1240(2)4704解：4704=25*3*72i(4704)=6*2*3=36a(4704)=(1+2+4+8+16+32)*(1+3)*(1+7+49)=14364(3)5544解：5544=23*32*7*11i(5544)=4*3*2*2=48a(5544)=(1+2+4+8)*(3+9+1)*(1+7)*(1+11)=218402.9求7^2046写成十进制数时的个位数。解：72≡-1(mod10)→(72)1022≡1(mod10)→72046≡9(mod10)2.10证明：正整数n(十进制)能被3整除的充要条件时将n的各位数字相加所得和能被3整除。证明：n可写为十进制表示式：N=10kak+10k-1ak+……+10a1+a0(0≤ai≤10)因为10i≡1(mod3),0≤i≤k,故10kak+10k-1ak-1+……+10a1+a0≡ak+ak-1+……+a1+a0(mod3)所以n≡0(mod3)的充要条件是ak+ak-1+……+a1+a0≡0(mod3)∴命题得证2.11证明641|22^5+1证明：22^5=232(mod641)∵211≡125(mod641)∴232=222·210≡1252·210(mod641)又∵5×29≡-4(mod641)125*5=-16(mod641)∴1252·210≡(125*5)*5*(5*29)*2≡(-16)*5*(-4)*2(mod641)≡640(mod641)∴22^5≡-1(mod641)∴22^5+1≡0(mod641)∴641|22^5+12.13(1)27x≡12(mod15)先求解方程：9x≡4(mod5)φ(5)=4,x≡93*4≡1(mod5)∴x≡1+5t(mod15)∴解为x≡1,6,11(mod15)(2)24x≡6(mod81)先求解方程：8x≡2(mod27)φ(27)=18,∴x≡817*2≡7(mod27)∴x≡7+27t(mod27)∴解为x≡7,34,61(mod81)(3)91x≡26(mod169)先解方程：7x≡2(mod13)φ(13)=12,∴x≡711*2≡4(mod13)∴x≡4+13t(mod13)∴x≡4,17,30,43,56,69,82,95,108,121,134,147,160(mod169)2.14(1)解：25t≡9(mod12),φ(12)=4∴t≡9*253≡9(mod12)12t≡6(mod25),φ(25)=20∴t≡1219*6≡13(mod25)∴x=25*9+12*13=381（2）15*22t≡5(mod7)∴t≡155*225*5≡5(mod7)7*22t≡12(mod15)∴t≡77*227*12≡3(mod15)7*15t≡18（mod22）∴t≡79*159*18≡14(mod22)∴x=15*22*5+3*7*22+7*15*14=12722.15求相邻的4个正整数,它们依次可被,,,整除.解:设这四个正整数依次为x,x+1,x+2,x+3则.则m=44100,==11025=4900=1764=900.49001764900X)2.16解:设先将化为首一多项式:145,由多项式性质(定理2.2.30),存在整系数多项式q(x)和r(x),使得,其中degr(x)5.由多项式辗转相除法:(/()=，余∴f(x)≡x3+2x2+2x(mod5)∴f(x)≡0(mod5)的解为x≡0，1，2(mod5)2.17解：由定理2.2.35，将f(x)(mod5)化为首一多项式：f(x)(mod5).辗转相除法得：()/(=，余∴=由定理2.2.35，知f(x)0(mod5)有三解而a的阶与a的阶相等。所以，任何元素a的阶可以整除|a|2.18因为47为奇素数，所以有原根因为５５不是２，４，pl,2pl,所以５５无原根因为５９为奇素数，所以有原根对于47,因为∮(47)=46=2*23所以１2≡１(mod47),22≡4(mod47),32≡9(mod47),42≡16(mod47),52≡25(mod47),62≡36(mod47),223≡1(mod47),323≡1(mod47),4为原根,3为47的一个原根所以,当t遍历46的缩系时,3遍历47的原根,对于５９，因为∮（５９）＝５８＝２*２９因为55不是2,4,P,,所以55无原根因为59为奇素数,所以有原根所以１1≡１（mod59）,22≡4(mod59),229≡58(mod59)所以，当t遍历５８的缩系时，２遍历５９的原根所以，２1≡２，２3≡８，２5≡３２，２7≡１０，２9≡４０，２11≡４２，２13≡５０，２15≡２３，２17≡３３，２19≡１４，２21≡５６，２23≡４７，２25≡１１，２27≡４４，２31≡５５233≡43235≡54237≡39239≡38241≡34243≡18245≡13247≡52249≡31251≡6253≡24255≡37257≡302.19解：φ（41）=40，d=(40,22)=2,查模41的指数表可得indg5=22所以根据2|22知方程有解且个数为2又原方程与22indgX≡indg5(mod40)等价，即indgX≡1或21（mod40）可解得X≡6或35（mod41）2.20．解：X2≡191(mod397)（191/397）=（-1）（191-1）/2*(397-1)/2(397/191)=(15/191)=（-1）（15-1）/2*(191-1)/2(191/15)=-（11/15）=-（-1）（11-1）/2*(5-1)/2(15/11)=(4/11)=1所以该同余方程有解2.21．解：（11,511）=1,所以不必考虑511是否为素数即可计算雅可比符号。（11/511）=（-1）（11-1）/2*(511-1)/2(511/11)=-(5/11)=-（-1）（5-1）/2*(11-1)/2(1/5)=-1所以同余方程无解。2.22解：x2≡3（modp）有解，∴（3/p）=(p/3)*(-1)p-1/2∴(p/3)*(-1)p-1/2,p必不为3。①p≡1(mod3)则（p/3）=1∴(-1)p-1/2=1∴p=4i+1且p=3k+1②p≡2(mod3)则（p/3）=-1,∴(-1)p-1/2=-1∴p=4i+3且p=3k+2又p为奇素数∴p＝12j+1或p=12j+11,且p为奇素数2.23[3,1,1,2,3,1,1]2.24[2,4]（4循环上划线打不来了）！3.2证明：先证方程ax=b有唯一解反证：若有两解x1,x2,则ax1=b=ax2由消去律得x1=x2若无解，即对任意x∈G,有ax≠b则设a的阶为n,x有n个取值因为存在ax≠b所以有n-1个取值所以由抽屉原理存在x1≠x2使ax1=ax2与消去律矛盾所以有唯一解同理，y*a=b也有唯一解由定理3.2.8（G，*）构成群3.3证明：必要性：因为（H，*）为一个群，所以满足封闭性所以必有对任意a,b∈H,有a*b∈H充分性：因为对a,b,c∈H若有ab=ac则因为a,b,c∈G所以有B=C所以(H,*)满足左消去律同理(H,*)满足右消去律所以由2题结论(H,*)为(G,*)的子群3.4证明：设存在子群（H，*）,H∈G则由拉格朗日定理|H|整除|G|而|G|为质数所以|H|=1或|G|(H,*)必为(G,*)的平凡子群再证（a,·）为循环群反设所有a∈a且a≠ea的阶为kk≠|a|则以a为生成元可构成一个循环群a则a包含于a于a无非平凡子群矛盾所以，a≠e时，a的阶为|a|所以，（a,·）＝a为循环群3.5证明：设该循环群为a，a为生成元则对任何b，c∈a任何k1,k2,使b=ak1,c=ak2所以bc=ak1·ak2=ak1+k2=cb所以循环全必为交换群3.6证明：设该群为a，对任何a∈a设a的阶为k，所以ak=e,即a·ak-1=e下面证不存在k1k使（ak-1）k1=e反证设所有k1k,使（ak-1）k1