《数论 第三章 同余式02》由会员分享，可在线阅读，更多相关《数论 第三章 同余式02（31页珍藏版）》请在金锄头文库上搜索。
1、数论基础|茨祀章-同余式E2中国制余定理一中国剩余定理及其证明0二中国剩余定理的应用0三小结Date政池中国制余定理及其证明司刹余定理)设m,.m,是k个两两互素的正墓数,则对任意的整数b,.,b,同余式组X世b(modam)(D)=b,(mod“Im)一定有解,且解是唯一的.中国制余定理及其证明冬m=m,.m,m二mM.i=1.k则同余式绍(的MMb+.+MMb(modIm)共中M井IImimnMM=1Gmodmjui=12.小(iD苹后N=m.m.i=l.k-1则同余式细(0)的解可表示为x三sk(modm“.mk).其中,NN=1(modm,)i=12.k-1.而x是同余式组中国制余定理
2、及其证明的鲜.行1.k三b(modm)井X,+N(b一Ki)(modim行2万汪明一首先,证明解的唯一性.设ss都是滩足同余式(1)式的鲜,则丶三bi三x(mod“mi).训1心因为,m,.m,是两两互素的正整数,根猝2.13我们得到x东x“(mod“m)Date政沥5理12,中国制余定理及其证明明解的存在性明直接构盗同余R探传设条体v硕震帕给定的i1Siki粤木趸据3二l人仁2,或接运蒯义欧几得除法,可分别求出整数MFSFss2.k,使得TM=1modm邦12中国制余定理及其证明。我们就构造出一个形为(2)式的整数,即MMb,+.+M.M,b,.(modm)水m=m,.M及m1M:15jSk
3、,j子i所以这个整数x溱足司余式x世MAMb,世b(modm).i=12.k击就是说,形为(2)式的整数是同余式(1)式的解.中国制余定理及其证明证明二,归纳构造同余式组的解.k1时,同余式x三b(modm)的鲜为xk=2时,原吉余式组等价哥x三b(modN)X世b(modmu)吊一小文世b,(modm,)(4)式的第一个同余式有解x三&三b(modMN,).我们E中国制余定理及其证明寺同余式组的解表示为(y侍定参数)5云5十切y将节代入同余式组(4)式的第二个同余式,我们有x,+NY=b(modm,)或N,y,=b,-x(modm,)(5)运用广义欧儿里得除法,丈整数Nl及模m。,可求出整数N使得NN=1(modm)中国制余定理及其证明$式组(4)的解为又=x,=X,+N,(N,(b,-X)(modm,)(modmm)偶设i-1(i艾2)时,哥题成立,即5世D(modin)X世b,GmodIm)有鲜爻世X(modtm0n)
