线性同余方程组的解

线性同余方程组的解学生：罗腾，江汉大学数计学院（数学与应用数学系）指导老师：许璐，江汉大学摘要“孙子算经”一书中写于公元前三世纪，这个谜题如下：有堆东西不知道有多少，如果三个三地数，最后余下两个；五个五个的数，最后余下三个；七个七个的数，最后余下二个，问这堆东西共有多少？我们可以把这个问题用数学符号表示成同余式的形式：定理1设和均为整数，，若，其中.则线性同余方程组，有唯一一组关于模的解为，其中是关于模m的逆，即.证首先，将同余式两边都乘以，将同余式两边都乘以，得到得到令，则.下面我们把同余式两边都乘以，其中同理，将同余式两边都乘以，将同余式两边都乘以，得到得到即关键词孙子定理；中国剩余定理；同余；线性；方程组AbstractSuchsystemsaroseinancientChinesepuzzlessuchasthefollowingproblem,whichappearsinMasterSun’sMathematicalManual,writtenlateinthethirdcenturyc.e..Findanumberthatleavesaremainderof1whendividedby3,aremainderof2whendividedby5,andaremainderof3whendividedby7.Thispuzzleleadstothefollowingsystemofcongruences:Theorem4.15.Leta,b,c,d,e,f,andmbeintegers,m>0,suchthat,whereThenthesystemofcongruenceshasauniquesolutionmodulom,givenbywhereisaninverseofmodulom.Proof.Wemultiplythefirstcongruenceofthesystembydandthesecondbyb,toconcludethatThenwesubtractthesecondcongruencefromthefirst,totindthat,or,since，.Next,wemultiplybothsidesofthiscongruenceby,aninverseofmodulom,toconcludethatInasimilarway,wemultiplythefirstcongruencebycandthesecondbya,toobtainWesubtractthefirstcongruencefromthesecond,tofindthatorFinally,wemultiplybothsidesofthiscongruencebytoseethat.keywordMasterSun’sMathematicalManual；TheCheneseRemainderTheorem；congruences；Linear；Equations目录绪论………………………1线性同余方程组解的判定及其结构……………………51.二元一次同余方程组解的判定及其结构…………52.三元一次同余方程组的解…………123.线性同余方程组的解在n元中的推广……………18致谢………………………24参考文献…………………25PAGE26PAGE26绪论（一）研究问题的背景数论中的同余式理论，以我国古代的研究为最早，当二整数之差能被正整数m除尽时，便称这两个数对于“模”m同余。《孙子算经》（公元四世纪）中计算一次同余式组的“求一数”有“中国剩余定理”之称。公元十三世纪秦九韶已建立了比较完整的同余式理论——“大衍求一术”。《孙子算经》出现在4—5世纪，其具体的成书年代与作者姓名已不可考，这是继《九章算术》之后有一部重要的数学著作。《孙子算经》分上、中、下三卷，卷上叙述度量衡制度、筹算记数和筹算乘除运算方法；卷中举例说明筹算分数算法和开平方算法，以及简单的面积、体积计算；卷下是各种应用问题，涉及田域、仓窖、营建、赋役、军旅等。从其内容特色来看，它以实际应用为主，注重计算技术，题目通俗有趣，解法巧妙简便，在中国古代数学著作中是很有代表性的。《孙子算经》还记载了举世闻名的“孙子问题”，这就是卷下第26题，也即全书的最后一题。原文是这样的：“今有物不知数。三三数之剩二；五五数之剩三；七七数之剩二，问物几何？”【1】其意思是：有堆东西不知道有多少，如果三个三地数，最后余下两个；五个五个的数，最后余下三个；七个七个的数，最后余下二个，问这堆东西共有多少？有一首口诀“孙子歌”就描述了孙子问题的解法：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百令五便得知。孙子算法的关键，在于70、21和15这三个数的确定。后来流传的《孙子歌》中所说“七十稀”、“廿一枝”和“正半月”，就是暗指这三个关键的数字。《孙子算经》没有说明这三个数的来历。【2】虽然《孙子算经》记载的“孙子问题”似乎是一个数字游戏，但古代产生这一问题的背景却是非常深刻的。据研究，早在公元2世纪时，我国就已研究过需要一次同余式才能解决的天文问题。这类问题在中国古代数学中是经常遇到的，不过由于问题的提法不同而赋予不同的名称，如“鬼谷算”、“秦王暗点兵”、“剪管术”、“隔墙算”等等。我们今天主要研究的课题——线性同余方程组的解——也是以“孙子问题”中的同余理论做为基础。（二）国内研究状况和研究成果研究状况数论有三千余年的历史，产生于四大文明古国（埃及、巴比伦、印度和中国）。古代中国对于整数的同余性质有相当深刻的认识，在《孙子算经》中载有“物不知数”问题，给出一次同余方程组的解法。这种方法在近代已被推广成非常一般的形式，但仍被世人称为“中国剩余定理”。将“孙子问题”【1】用现代的数学符号表示，等价于解下列一次同余式组：，，中国剩余定理从发现（孙子问题）到理论形成（求一术），经失传而后重新挖掘，虽然历时1000多年的时间，但在世界上一直处于领先地位，迟至1801年高斯（K.P.Gauss，德国，1777-1855）的《算术研究》才作出了与秦九韶相同的结果。由此可见，中国剩余定理确实充分展现出了中国古代数学的独特魅力，以至于康托尔也不得不承认：“发明这一定理的中国数学家是最幸运的天才”。【3】研究成果有文献记载，早在公元前2世纪，我国就将同余理论应用于天文领域。一次同余问题的研究，明显地受到天文、历法需要的推动，特别是和古代历法中所谓“上元积年”的计算密切相关。大家知道，一部历法，需要规定一个起算时间，我国古代历算家把这个起点叫做“历元”或“上元”，并且把从历元到编历年所累积的时间叫做“上元积年”。上元积年的推算需要求解一组一次同余式。以公元三世纪三国时期魏国施行的《景初历》做例，这部历法规定以冬至、朔旦（朔日子夜）和甲子日零时会合的时刻作为历元。设a是一回归年日数，b是一朔望月日数，当年冬至距甲子日零时是R1日，离平朔时刻是R2日，那么《景初历》上元积元数N就是同余组aN≡Ri（mod60）≡R2（modb）的解。到了南北朝时期，祖冲之《大明历》（公元462年）更要求历元必须同时是甲子年的开始，而且“日月合璧”、“五星联珠”（就是日、月、五大行星处在同一方位），月亮又恰好行经它的近地点和升交点。这样的条件下推算上元积年，就相当于要求解十个同余式了。【4】（三）国外研究状况和研究成果研究状况直到19世纪，数论还只是一系列孤立的结果，虽然这些结果常常是光辉的，一个新的纪元是从Gauss的《算术探讨》（DisquisitionesArithmeticae）开始的，这部书史从他20岁时写的。这部伟大的著作曾在1800年寄到法国科学院而被拒绝，但Gauss自己把它发表了。在这部书中，他把记号标准化了，把现存的定理系统化并推广了，把要研究的问题和攻题的已知方法进行了分类，还引进了新的方法。在Gauss关于数论的著作中有三个主要思想：同余的理论，代数数的引进，以及作为Diophantine分析的指导思想的型理论。【5】我们所要研究的课题也是以这三个主要思想之一的同余理论为基础的。虽然同余的概念不是从Gauss开始的——它出现在Euler，Lagrange和Legendre的著作中——但是Gauss在《算术探讨》【5】的第一节引进了同余的记号，并在此后系统的应用了它。研究成果高斯不仅在自己的著作中处理了一次同余式，并在其中得出了很多结论。此外，他还开始处理幂的同余式。在这里他用同余式的术语给了Fermat小定理一个证明，Fermat小定理用同余式叙述就是：若p是素数而a不是p的倍数，则【5】这个定理从他对高次同余式，即对的研究中推出。在证明了一些关于同余式的次要定理之后，高斯给出了二次方转定律的第一个严密证明。这个题目被高斯之后的许多人继续研究着。在同余理论的研究用高斯还讨论平方剩余、多项式的同余式等。在19世纪20年代高斯着手研究可应用于高次同余式的反转定律。可以说在一系列的研究中，高斯对于数论中同余的理论在今后的发展乃至现在的研究成果的贡献是功不可没的。（四）数论发展史的启示和意义从历史的角度来看，由于深刻的文化内涵附着于数之上，使得看似枯燥的数字蕴藏着丰富的思想内容，所以如果既能从思想文化的角度去认识数，又能从数字本身挖掘出隐藏其背后的人文特征，则不仅能改变数学的“公众形象”，而且也能使学生体会到，学习数学就是了解人类的思想文化，从而建立起数学与现实社会密不可分的观念。数学被认为是枯燥的、乏味的和无用的这种“形象危机”已经存在，而造成这一严重后果的原因，我们认为既不在于数学本身，更不在于外界对数学的“无知”，而在于我们漠视数学与文化的一体性，不屑数学与其他学科的横向联系，怠于展示数学的思想内涵。因此，作为数学工作者，特别是数学教育工作者应对此进行深刻的反省。（五）课题的研究方法本课题的研究主要采取逻辑推理和论证法，并借助实例验算法。本课题的基本研究程式为：课程学习→阅读资料→逻辑推理→实例验证→总结行文。（六）课题构成及研究内容课题主要是在孙子定理的基础上研究二元一次同余方程组的解的结构和判定，进而把这个结论在多元上进行推广。课题采用逐层深入的形式，首先探讨最基本的二元一次同余方程组，进而讨论三元的情况，最后在多元的空间中将结论推广。在这个扩展的过程中会用到很多我们熟知的定理，例如克拉默法则、同余的性质定理等，这些定理在多元同余方程组中的推广起了不小的作用。线性同余方程组解的判定及其结构引言：中国剩余定理（孙子定理）在数论及近代代数领域是非常重要的理论，起着基础作用，且有着广泛的应用。本文是在中国剩余定理的基础上，讨论一般的线性同余方程组的解和解的结构问题。有着很重要的意义。1.二元一次同余方程组解的判定及其结构定理1设和均为整数，，若，其中.则线性同余方程组，有唯一一组关于模的解为，其中是关于模m的逆，即.【6】证首先，将同余式两边都乘以，将同余式两边都乘以，得到得到令，则.下面我们把同余式两边都乘以，其中同理，将同余式两边都乘以，将同余式两边都乘以，得到得到即证毕为了便于记忆我们也可以把上述的结论写成行列式的形式，其中，且例1.1解同余方程组解：这里，，，，，，所以且.由于，故由定理1知方程组有一解为所以方程组的解为引理1一次同余式有解的充分与必要条件是若一次同余式有解，则解数（对模m来说）是.【7】证因为该一次同余式有解的充分与必要条件是有解。若有一组整数解，设为，即.但整除及，因而整除，故条件的必要性获证。反之，若，则，其中是整数。所以存在两个整数满足下列等式令，即得，故有整数解.从而有解的充分必要条件是.设.若一次同余式有解，则由二元一次不定方程解的性质【8】知一次同余式的一切整数可以表成此式对模m来说，可以写成但是对模m两两不同余的，故一次同余式有个解。证毕上面提到的二元一次不定方程解的性质定理【8】内容如下设二元一次不定方程有解，是它的一组解。那么，它的所有解为【8】定义1形如①，其中为整数，m为正整数的方程称为二元一次同余方程组。定理2对于方程组①，记，当，且同时时，则①有解，且解数为d.证将两边乘以得②两边乘以得③②③得记，所以④根据引理1，若④有解，则其充分必要条件为，且解数为.同理，两边乘以得⑤两边乘以得⑥⑥⑤得⑦根据引理1，若⑦有解，则其充分必要条件为，且解数为.因为要使得方程组①有解，那么均要有解，所以必须满足上述两个条件。写成行列式的形式，即且.对于方程组①的解数而言，我们知道因为（或）有个解，那么将（或）的每一个解对应可得到一个（或），故共有d组解。综上所述，对于二元一次同余方程组①解的情况我们可以归纳为下面几个情况：Ⅰ、记，若，二元一次同余方程组①有唯一一组解。根据定理1知其解为，其中，这里我们把称为是对模m的逆。Ⅱ、记，若，且时，①式关于模m有个解。Ⅲ、记，若，不能整除或者不能整除，①式关于模m无解。例1.2解同余方程组解：，，因为不能整除和，所以方程组无解。例1.3解同余方程组解：，，根据定理2知因为，所以方程组有解，且有5组解。根据定理1通过消元法可将方程组转化为解得的5个解为0，1，2，3，4，（关于模5）解得的5个解为0.，1，2，3，4，（关于模5）将其带入方程（1）（2）式中可以看出方程组的5组解为,,,,上面我们讨论的都是模相同的形式，那么对于模m不同的情况，那么结论又会是怎样一个情形呢？这种情况也是我们主要探讨的核心内容，下面我们来看一下如果模m不同，方程组应该如何求解。引理2同余方程有解的必要且充分条件为.若此条件适合，则其解数为.【9】证由引理1知此对n=1为真.今用归纳法以证之.命及，则.由引理1知有个解.对此式之一解，命由归纳法假定，之解数为故总解数为证必定理3线性同余方程组，记，且，，，记，存在是对模m的逆，使得，其中，线性同余方程组有m组解，其解的形式为，。证明：因为，所以，因此，根据引理2，故（1）有解。同理，因为我们可以推出（2）有解。因为，根据同余的性质将（1）式两边同时乘以，可转化为即（2）式左右两边同时乘以，可转化为即所以线性同余方程组可化为那么我们就将线性同余方程组模不同的情况转变为了一个模相同的情况，解的方法就跟定义1的方法一样，首先判断解的情况。记因为，所以且线性同余方程组有解，由定理1知其解的形式为其中例1.4解同余方程组解：，且，所以方程组有组解（1）式左右两边乘以3，（2）式左右两边乘以2，方程组化为因为，，所以通过消元法方程组可化简为解得的6个解为0，1，2，3，4，5（关于模6）解得的6个解为0，1，2，3，4，5（关于模6）将其代入方程（1）（2）中，我们可以得到满足原方程组的6组解为，，，，，.2.三元一次同余方程组的解以上我们探讨了二元一次同余方程组关于模m不相同的情况，那么对于有三个未知数的三元一次同余方程组的情况，二元的结论是否适用？这个规律能否在三元一次同余方程组中推广？为了回答这个问题，下面我们来探讨一下三元一次同余方程组关于模m不同的情况。为了更加方便的得到结论，我们先看一下三元一次同余方程组关于模m相同的情形。定义2形如，其中为整数，m为正整数的方程称为三元一次同余方程组。定理4上述三元一次同余方程组，记，若，方程组有唯一一组解若，且均能整除，，.那么方程组有组解；否则方程组无解。证明：首先利用消元法，将三元转化为二元，二元转化为一元的思想。将得得将得得联立（6）（9）式得到一个二元一次同于方程组所以我们可以直接用到定理1的结论记，其中所以上式联立消去可得到即同理通过相似的方法消去得到消去得到因为，所以根据引理1，都只有一个解，因此方程组有唯一一组解其中是关于模m的逆，使得成立。若，要使得原方程组有解，必须都要有解，所以根据引理1要均能整除，，.对于方程组的解数而言，每一个都对应一个，所以方程组有d组解；否则方程组无解。所以通过定理4所讨论的内容，我们很容易得出三元一次同余方程组关于模m不相同的结论。定理5线性同余方程组，记，且，，，令,记，存在使，是对模m的逆，线性同余方程组有解，其解的形式为,.证明：，所以，则，根据引理2故（10）式有解；同理，因为根据引理2知（11）（12）有解。因为，（10）式乘以，（11）式乘以，（12）式乘以，方程组化为我们通过变形就将方程转化为了定义2的形式，那么我们就可以直接利用定义2得到的结论。，，，，均可被整除，所以线性同余方程组有解。根据上面定理4知，线性同余方程组的解的形式为,，其中是对模m的逆。对于模m不相同这类问题，其解的个数比较特殊，本文只讨论其解的形式。例2.1解同余方程组.解：因为，，所以方程组有唯一一组解。根据定理4的结论，通过消元我们可以得到（13）解（13）式得同理可以解得方程组的解为，，解同余方程组.解：因为，所以，另外求得，，，它们均能被2整除，所以方程组有2组解。根据定理4消元我们得到（14）解（14）式得同理解得将解代入原方程组，通过验算可以知道方程组有2组解为；.3.线性同余方程组的解在n元中的推广前面两个章节我们讨论了二元线性同余方程组和三元线性同余方程组解的情况，我们从中可以发现，其结论是有规律可寻的，可以说三元线性同余方程组其实就是二元线性同余方程组的一个推广。在数学这门学科当中二元的结论推到三元中，进而推广到n元的例子也有很多。那么是否我们前面所证明和论证的结论也可以在n元空间中作推广呢？这个也是我们本节所要讨论的核心内容。在前面我们解决线性同余方程组的所用到的方法就是消元法，这个和线性方程组的解法有些类似，所以我们可以设想，如果一个n元线性方程组的每个解都可以用其未知数的系数表示出来，那么n元线性同余方程组的解的结构就迎刃而解了。下面我们先引出一个定理，这个定理叫做克拉默（Cramer）法则，刚好能够解决上面的问题。引理3（Cramer法则）如果线性方程组（1）的系数矩阵（2）的行列式，那么线性方程组（1）有解，并且解是唯一的，解可以通过系数表为（3）其中是把矩阵A中第j列换成方程组的常数项所成的矩阵的行列式，即（4）【10】定理中包含着三个结论：1o方程组有解；2o解是唯一的；3O解由公式（3）给出。这三个结论是有联系的，因此证明的步骤是：证1.把方程组（1）简写为（5）首先来证明（3）的确是（1）的解。把（3）代入第i个方程，左端为（6）因为，所以.那么我们有这与第i个方程的右端一致。换句话说，把（3）代入方程使它们同时变成恒等式，因而（3）确为方程组（1）的解。2.设（）是方程组（1）的一个解，于是有n个恒等式（7）为了证明，我们取系数矩阵中第k列元素的代数余子式用它们分别乘（7）中n个恒等式，有这还是n个恒等式。把它们加起来，即得（8）等式右端等于在行列式d按第k列的展开式中把分别换成（），因此，它等于把行列式d中第k列换成所得的行列式，也就是.再来看（8）的左端。即因为所以于是，（8）即为也就是这就是说，如果（）是方程组的一个解，它必为（），因而方程组最多有一组解。证完有了这个引理，下面的n维线性同余方程组的解的问题就好解决了。定义3其中为整数，m为正整数的方程组称为n维线性同余方程组。首先，记（9）（10）我们可以直接用到克拉默（Cramer）法则的结论，方程组可以化成（11）若方程组有唯一一组解（12）其中是对模m的逆。若，且能整除，方程组有解，解数为；反之，方程组无解综上我们就得到了n维线性同余方程组的解（12）.同样的我们也可以把这种情况推导到模m不相同的情形。定理6n维线性同余方程组其中为整数，为正整数。记，其中，且两两互质，，记.记，方程组的解可以写成的形式.证明：，所以，故由引理2知方程组中的每一式都有解。将（13）乘以，（14）乘以，······，（15）乘以，原方程组化为这样我们就把n维线性同余方程组模m不同的情况转化为模m相同的情况，我们可以直接用到定义3的结论。因为能整除.所以方程组有解，其解的形式为其中是对模m的逆.致谢2010年5月一个阳光明媚的下午，我在窗前那张略显陈旧的书桌上，写下论文最后一个字，随之意识到，又是一段时间随着这摞厚厚的稿件划上了休止符。为论文做的工作还是很多的，从选定论文题目那天起，便开始了查找资料和撰写论文的工作。从黄叶满地的初冬到高枝蝉噪的盛夏，工作历经数月，虽然辛苦，但终于完成了这篇论文。四年的大学生活一晃而过，回首走过的岁月，心中倍感充实，论文完成之日，感慨良多。首先诚挚的感谢我的论文指导老师许璐老