线性同余方程组的解学生：罗腾，江汉大学数计学院（数学与应用数学系） 指导老师：许璐，江汉大学摘要“孙子算经”一书中写于公元前三世纪，这个谜题如下：有堆东西不知道有多少，如果三个三地数，最后余下两个；五个五个的数，最后余下三个；七个七个的数，最后余下二个，问这堆东西共有多少？我们可以把这个问题用数学符号表示成同余式的形式：()()().7m od 3,5m od 2,3m od 1≡≡≡x x x定理1 设,,,,,a b c d e f 和m 均为整数，0m >，若(,)1m ∆=，其中ad bc ∆=-.则线性同余方程组(mod )(mod )ax by e m cx dy f m +≡⎧⎨+≡⎩，有唯一一组关于模m 的解为()(mod )()(mod )x de bf m y af ce m ⎧≡∆-⎪⎨≡∆-⎪⎩， 其中∆是∆关于模m 的逆，即1(mod )m ∆∆≡.证 首先，将同余式(mod )ax by e m +≡两边都乘以d ，将同余式(mod )cx dy f m +≡两边都乘以b ，得到(mod )(1)(mod )(2)adx bdy de m bcx bdy bf m +≡⎧⎨+≡⎩()()12-得到()()mod ad bc x de bf m -≡-令ad bc ∆=-，则()mod x de bf m ∆⋅≡-.下面我们把同余式两边都乘以∆，其中1(mod )m ∆∆≡∴()()mod x de bf m ≡∆-同理，将同余式(mod )ax by e m +≡两边都乘以c ，将同余式(mod )cx dy f m +≡两边都乘以a ，得到(mod )(3)(mod )(4)acx bcy ce m acx ady af m +≡⎧⎨+≡⎩()()43-得到()()mod ad bc y af ce m -≡-即()mod y af ce m ∆⋅≡-∴()()mod y af ce m ≡∆-关键词孙子定理；中国剩余定理；同余；线性；方程组AbstractSuch systems arose in ancient Chinese puzzles such as the following problem, which appears in Master Sun ’s Mathematical Manual , written late in the third century c.e.. Find a number that leaves a remainder of 1 when divided by 3, a remainder of 2 when divided by 5, and a remainder of 3 when divided by 7. This puzzle leads to the following system of congruences:()()().7m od 3,5m od 2,3m od 1≡≡≡x x xTheorem 4.15. Let a,b,c,d,e,f, and m be integers, m>0, such that (),1m ∆=, where.ad bc ∆=- Then the system of congruences()()mod mod ax by e m cx dy f m +≡+≡has a unique solution modulo m, given by()(mod )()(mod ),x de bf m y af ce m ≡∆-≡∆-where ∆ is an inverse of ∆ modulo m.Proof. We multiply the first congruence of the system by d and the second by b, to conclude that(mod )(mod ),adx bdy de m bcx bdy bf m +≡+≡Then we subtract the second congruence from the first, to tind that()()mod ad bc x de bf m -≡-,or, since ad bc ∆=-，()mod x de bf m ∆≡-.Next, we multiply both sides of this congruence by ∆, an inverse of ∆ modulo m, to conclude that()()mod x de bf m ≡∆-In a similar way, we multiply the first congruence by c and the second by a, to obtain(mod )(mod ),acx bcy ce m acx ady af m +≡+≡We subtract the first congruence from the second, to find that()()mod ad bc y af ce m -≡-or()mod y af ce m ∆≡-Finally, we multiply both sides of this congruence by ∆ to see that()()mod y af ce m ≡∆-.keywordMaster Sun ’s Mathematical Manual ；The Chenese Remainder Theorem ；congruences ；Linear ；Equations目录绪论 (1)线性同余方程组解的判定及其结构 (5)1.二元一次同余方程组解的判定及其结构 (5)2.三元一次同余方程组的解 (12)3.线性同余方程组的解在n元中的推广 (18)致谢 (24)参考文献 (25)绪论（一）研究问题的背景数论中的同余式理论，以我国古代的研究为最早，当二整数之差能被正整数m除尽时，便称这两个数对于“模”m同余。

《孙子算经》（公元四世纪）中计算一次同余式组的“求一数”有“中国剩余定理”之称。

公元十三世纪秦九韶已建立了比较完整的同余式理论——“大衍求一术”。

《孙子算经》出现在4—5世纪，其具体的成书年代与作者姓名已不可考，这是继《九章算术》之后有一部重要的数学著作。

《孙子算经》分上、中、下三卷，卷上叙述度量衡制度、筹算记数和筹算乘除运算方法；卷中举例说明筹算分数算法和开平方算法，以及简单的面积、体积计算；卷下是各种应用问题，涉及田域、仓窖、营建、赋役、军旅等。

从其内容特色来看，它以实际应用为主，注重计算技术，题目通俗有趣，解法巧妙简便，在中国古代数学著作中是很有代表性的。

《孙子算经》还记载了举世闻名的“孙子问题”，这就是卷下第26题，也即全书的最后一题。

原文是这样的：“今有物不知数。

三三数之剩二；五五数之剩三；七七数之剩二，问物几何？”【1】其意思是：有堆东西不知道有多少，如果三个三地数，最后余下两个；五个五个的数，最后余下三个；七个七个的数，最后余下二个，问这堆东西共有多少？有一首口诀“孙子歌”就描述了孙子问题的解法：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百令五便得知。

孙子算法的关键，在于70、21和15这三个数的确定。

后来流传的《孙子歌》中所说“七十稀”、“廿一枝”和“正半月”，就是暗指这三个关键的数字。

《孙子算经》没有说明这三个数的来历。

【2】虽然《孙子算经》记载的“孙子问题”似乎是一个数字游戏，但古代产生这一问题的背景却是非常深刻的。

据研究，早在公元2世纪时，我国就已研究过需要一次同余式才能解决的天文问题。

这类问题在中国古代数学中是经常遇到的，不过由于问题的提法不同而赋予不同的名称，如“鬼谷算”、“秦王暗点兵”、“剪管术”、“隔墙算”等等。

我们今天主要研究的课题——线性同余方程组的解——也是以“孙子问题”中的同余理论做为基础。

（二）国内研究状况和研究成果研究状况数论有三千余年的历史，产生于四大文明古国（埃及、巴比伦、印度和中国）。

古代中国对于整数的同余性质有相当深刻的认识，在《孙子算经》中载有“物不知数”问题，给出一次同余方程组的解法。

这种方法在近代已被推广成非常一般的形式，但仍被世人称为“中国剩余定理”。

将“孙子问题”【1】用现代的数学符号表示，等价于解下列一次同余式组：N≡N≡，2(mod7)2(mod3)N≡，3(mod5)中国剩余定理从发现（孙子问题）到理论形成（求一术），经失传而后重新挖掘，虽然历时1000多年的时间，但在世界上一直处于领先地位，迟至1801年高斯（K.P.Gauss，德国，1777-1855）的《算术研究》才作出了与秦九韶相同的结果。

由此可见，中国剩余定理确实充分展现出了中国古代数学的独特魅力，以至于康托尔也不得不承认：“发明这一定理的中国数学家是最幸运的天才”。

【3】研究成果有文献记载，早在公元前2世纪，我国就将同余理论应用于天文领域。

一次同余问题的研究，明显地受到天文、历法需要的推动，特别是和古代历法中所谓“上元积年”的计算密切相关。

大家知道，一部历法，需要规定一个起算时间，我国古代历算家把这个起点叫做“历元”或“上元”，并且把从历元到编历年所累积的时间叫做“上元积年”。

上元积年的推算需要求解一组一次同余式。

以公元三世纪三国时期魏国施行的《景初历》做例，这部历法规定以冬至、朔旦（朔日子夜）和甲子日零时会合的时刻作为历元。

设a是一回归年日数，b是一朔望月日数，当年冬至距甲子日零时是R1日，离平朔时刻是R2日，那么《景初历》上元积元数N就是同余组aN≡Ri（mod60）≡R2（modb）的解。

到了南北朝时期，祖冲之《大明历》（公元462年）更要求历元必须同时是甲子年的开始，而且“日月合璧”、“五星联珠”（就是日、月、五大行星处在同一方位），月亮又恰好行经它的近地点和升交点。

这样的条件下推算上元积年，就相当于要求解十个同余式了。

【4】（三）国外研究状况和研究成果研究状况直到19世纪，数论还只是一系列孤立的结果，虽然这些结果常常是光辉的，一个新的纪元是从Gauss的《算术探讨》（Disquisitiones Arithmeticae）开始的，这部书史从他20岁时写的。

这部伟大的著作曾在1800年寄到法国科学院而被拒绝，但Gauss自己把它发表了。

在这部书中，他把记号标准化了，把现存的定理系统化并推广了，把要研究的问题和攻题的已知方法进行了分类，还引进了新的方法。

在Gauss关于数论的著作中有三个主要思想：同余的理论，代数数的引进，以及作为Diophantine分析的指导思想的型理论。