同余式及一次同余式的解法

学院学术论文题目:同余式及一次同余式的解法学号：学校：专业：班级：姓名：指导老师：时间：同余式及一次同余式的解法摘要：一元一次同余式的解法,是我们不易掌握的问题,在《初等数论》中，我们所学的是运用孙子定理来对一次同余式组求解，应用孙子定理的前提条件是(i=1，2，…，k)两两互素。换言之，在未知(i=1，2，…，k)两两互素时，一次同余式组未必有解，另外，我们也可以运用其他的解法，当(a,m)=1时,若a,b＜m,(a,b)=1,且模数较大,可取余;若a,b＜m,(a,b)=1,且模数较小,用欧拉定理;若(a,b)=1,且a,b中至少有一个数大于m,利用同余知识,将a,b化小;若(a,b)≠1,约去两端的公因数;当(a,m)=d＞1时,用d去除同余式,再按(a,m)=1的情况去解.。关键字：同余同余式一次同余式的解法孙子定理欧拉定理Summary：Onedollaracongruenceofthesolution,isnoteasytograsptheproblem,elementarynumbertheory,wehavelearnedistousetheChineseRemainderTheoremtoonthefirstcongruencetosolvetheapplicationRemainderTheorempresupposes(i=1,2,...,k)primetoeachother.Inotherwords,theunknown(i=1,2,...,k)primetoeachother,thefirstofcongruencemaynotbeasolution,Inaddition,wecanalsousetheothermethod,when(a,m)=1whenIfa,bm,(a,b)=1,andthemoduluslargerthandesirable;ifa,bm,(a,b)=1,andthesmallermodule,usingEuler'stheorem;if(a,b)=1,anda,binatleastonegreaterthanm,advantagewithmorethanknowledge,willbea,bofsmall;if(a,b)≠1,isabouttogoacrossthecommonfactor;When(a,m)=d1,theremovalofcongruencewithd,then(a,m)=1casehadgoneto..Keyword：gongruencegongruencesolutionofagongruenceremaindertheoremEuler’stheroem引言在《初等数论》中，我们对一次同余式组的求解应用的是孙子定理。这是我们所学过的解一次同余式组的唯一一种方法。应用孙子定理的前提条件是(i=1，2，…，k)两两互素。换言之，在未知(i=1，2，…，k)两两互素时，一次同余式组未必有解，而当(i=1，2，…，k)很大时，判断它们两两互素也并非易事，需要作大量的计算工作，由此需要找到一种合理可行的方法解决此类问题。数论经过千百年的发展，已经有了长足的进步，要让数论与时俱进，这就要求认真研究，找到新规律，得出新方法。下面将对同余、同余式的基本概念以及一次同余式的解法等相关知识做一些概述：一、基本概念定义1设f(x)=anxna1xa0是整系数多项式，称f(x)0(modm)(1)是关于未知数x的模m的同余式，简称为模m的同余式。若an(modm)，则称为n次同余方程。定义2设x0是式(1)成立的一个整数，即f(x0)0(modm)则称xx0(modm)是同余方程(1)的解。凡对于模m同余的解，被视为同一个解。同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。由定义2，同余方程(1)的解数不超过m。二、同余式解的相关定理定理1由同余的性质易知下面的结论成立：(ⅰ)设b(x)是整系数多项式，则同余方程(1)与f(x)b(x)b(x)(modm)等价；(ⅱ)设b是整数，(b,m)=1，则同余方程(1)与bf(x)0(modm)等价；(ⅲ)设m是素数，f(x)=g(x)h(x)，g(x)与h(x)都是整系数多项式，又设x0是同余方程(1)的解，则x0必是同余方程g(x)0(modm)或h(x)0(modm)的解。（由整除的性质）下面，我们来研究一次同余方程的解。定理2设a，b是整数，a0(modm)(保证了（2）是一次同余式)。则同余方程axb(modm)(2)有解的充要条件是(a,m)b。若有解，则恰有d=(a,m)个解。证明显然，同余方程(2)等价于不定方程axmy=b，(3)若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，此时，一次不定方程(3)的全部解是，tZ。(4)由式(4)所确定的x都满足方程(2)。记d=(a,m)，以及t=dqr，qZ，r=0,1,2,,d1，则x==x0qm(modm)，0rd1。容易验证，当r=0,1,2,,d1时，相应的解对于模m是两两不同余的，所以同余方程(2)恰有d个解。证毕。定理3（孙子定理）：设m1,m2,…,mk是k个两两互质的正整数，m=m1m2…mk,m=miMi,i=1,2,3,……,k,则同余式组xb1(modm1),xb2(modm2),…,xbk(modmk)的解是xM'1M1b1+M'2M2b2+…+M'kMkbk（modm）,其中，M'iMi1（modmi）,i=1,2,…,k.[1]在定理的证明中，同时给出了解方程(2)的方法，即解不定方程4的方法去解。但是，对于具体的方程(2)，常常可采用不同的方法去解，我们通过例题来说明。三、同余式的解法例1设(a,m)=1，又设存在整数y，使得abym，则x(modm)是方程axb(modm)的解。解直接验算，有axbymb(modm)。1、例1说明，因为由abym知bym0(moda)，从而求方程aaaxxxbbb(((mmmooodddmmm)))的解可以转化为求方程mmmyyybbb(((mmmooodddaaa)))(5)的解，再把y代入x(modm)便得到x。2、这样解的好处：A：将一个对于大模m的同余方程转化为一个对于小模a的同余方程，因此有可能通过对模a的完全剩余系进行逐个验证（比较容易），以求出方程(5)和(2)的解，如求2y1(mod3)的解；B:进一步，设mr(moda)，ra，从而myb(moda)进一步化为ryb(moda)，又可继续转化成一个对于更小的模r的同余方程。例2解同余方程6x7(mod23)依次得到6x7(mod23)5x732(mod23)3x248(mod23)2x8710(mod23)x-10115(mod23)。例3设(a,m)=1，并且有整数0使得a1(modm)，则同余方程(2)的解是xba1(modm)。证明由axaba1bab(modm)知xba1(modm)是（2）的解。注：由例3及Euler定理可知，若(a,m)=1，则xba(m)1(modm)总是同余方程(2)的解。例4解同余方程81x324x25x230(mod7)。解原同余方程即是3x33x22x20(mod7)。用x=0，1，2，3逐个代入验证，得到它的解是x11，x22，x32(mod7)。[2]参考文献：[1]闵嗣鹤，严士键编.初等数论.3版--北京：高等教育出版社，2003.12，第74页，第77页[2]四川师范大学同余式讲解课程