还剩6页未读,继续阅读
文本内容:
基本概念及一次1同余式基本概念及一次同余式1定义设其中心…川是整数,又设则“X=c/+%++g,OMii=0,L m0,/x三0nKd41叫做模机的同余式若耳声〃叫做同余式⑴的次数如果满足了%Omodm,贝IJ M三则三七⑼叫做同余式的解不同余的解指互不同余的解Bmodm,X mod1当机及〃都比较小时,可以用验算法求解同余式如例同余式1A5+24+x3+2x2-2+3=0mod7A JV仅有解x=l,5,6mod
7.例同余式2A勺三0modl6有个解8A=l,3,5,7,9,11,13,15mod16例同余式3无解Xo+3三Oniod5定理一次同余式av三OInOd〃?M RO mod/H2JH一左=x=x+mod w,01,…,d-14Qd证易知同余式⑵有解的充要条件是不定方程ax-tny+b5有解而不定方程⑸有解的充要条件为,〃7二一叫〃.当同余式⑵有解时,若是满足⑵的一个整数,则A-in A一切刈,攵=a XQ+k modO,L…,d-L Nd下证犯,攵「,』T对模,〃两两部同余设a+=0,1••axo+-k三xo+-kmodnj,0k d-l,kf d-l ddmi mi m//tn A.i mff,则一三一A Amod—f7A=k modcA=ha ala再证满足⑵的任意一个整数看都会与某一个对模,〃同X0+2M0df Cl余由COC三bmod/X,aY]三,,InOd?得Q为三七沅Cixi=cix mod〃,Xi三二/modgQa aa「〜d.故存在整数/使得由带余除法,存在整数/我使得X=于是号号i=dq+hOk.Xi-XO+dq+k=Xo+k modin.故⑵有解时,它的解数为〃?以及若不是满足⑵的一个整d=a,数,则它的,〃?个解是〃7/X三X+—mod w,Z=0,1d-1d例求同余式19x三12mod156的解解对如下的整数矩阵作初等列变换故.又因故同余式有解,且由三个解由以上初等变换9,15=33|12,6还可知9x2+15x4=3,9x2x4+15x[-lx4]=12,9x8=12modl
5.故同余式⑹的三个解为X三8+mod15,〃=0,1,
2.A三3,8;13InOdI
5.例求同余式264x=83mod1057的角心解对作辗转相除法64,105105=64x1+41,64=41x1+23,41=23x1+18,23=18x1+5,18=5x3+3,5=3x1+2,3=2x1+1,2=1x2,故同余式⑺有唯一解由以上过程还可知64,105=1,1=3+2x-1=3+5-3xlx-l=5x-1+3x2=5x-1+18-5x3x2=18x2+5x-7=18x2+23-18xlx-7=23x-7+18x9=23x-7+41-23x1x9=41x9+23x-16=41x94-64-41x1x-16=64x-16+41x25=64x-16+105-64x1x25二105x25+64x-41故105x25+64x-41=1,105x25x83+64x-41x83=83,64x-340383modl
05.故同余式⑺的解为X三-3403mod105即x=62modl
05.习题.求下列同余式的解
11256.r=179mod
337.ii1215元三560QnOd
2755.1111296X三1125mod
935.解因i匕56337’25681,8111-14-110011-3I;O\
3、
3、10111044-25-25_*T104119-79H「79故于是该同余式有解,且对模有唯一解并且256,337=1,337256x104+337x-79=1,256x104x179+337x[-60xl791=179,256x104x179三179mod337,但是故于是该同余式的唯一104x179=18616三81mod337,256x81三
179337.解为X=81mod
337.由辗转相除法,可得故该同余式有解.ii1215,2755=5,5|560,由辗转相除法,还可得.在这个等式两边同时乘以1215・-195+2755・86=5得
112.古攵1215--21840+2755-9632=5601215•―21840=560mod
2755.因故.故该同余式的全部解为一21840三200111012755,1215-200三560mod27552755x三200+-I mod2755,=0,1,••
4.即X三200,751,13021853,2404mod
2755..求联立同余式2A+4y-29三0InOd143,2A-9y+84三0mod143的解解由同余式得x+4y-29三0modl43X=-4y+29mod143代入同余式2A-9y+84三0i8dl43得2-
4.y+29-9y+84三0modl43,-17y+142三0modl43,17y=-lmodl
43.对做辗转相除法17,143因143=17x8+7,17=7x2+3,7=3x2+1,3=1x3,故且17,143=1,1=7+3x-2=7+17-7x2x-2=17x-2^7x5=17x-20143-17x8x5二143x5+17x-
42.故143x5+17x-42=1,17x-42三lmodl43,17乂42三-lmodl
43.故由可得17y三-lmodl43y三42mod
143.由及得y三42Inodl43x+4y-29三OInOdl43A-+4x42-29三0modl43,A=4mod
143.于是可得,该联立同余式的解为A三4mod143,y=42Inod
143.设,〃是正整数,氏〃证明
3.i7=1,产X=be mod是同余式刈的解Cix=/mod设是质数,证明ii POvavp,尸~X三好17-…QnOdp是同余式的解ox三伏modp证因,〃是正整数,二故同余式有唯一解由欧拉定理i,M LOr三〃mod〃得abc/HIT=bcpd三Zjmod/.故是同余式〃]的解X三屁产C ov三bmod因是质数,尸,故同余式有惟一解ii P0”aP=L Ov三bmodp因故t7-l!|p-l-p-6/+1,-laA,P-I...p-a+lH«-l!modfl-l!.易知一IfTp-l---p-a+l-a-l1=-1WA1-
1...-«-1=CZ.1!mod p.因此㈠尸产-T dp.因故/〃.于是a!|ppT・・・p-a+l,4!,p=L T・・・〃-〃+1ab-iylP-D.・.Pel二伙T AIP-I・・.p-4+1三伙mod p.4!fl!因此是同余式的解X三伙-1a-1p-1…P二+1P ov三6niod Pmoda\。