有关一元一次同余方程组的若干基本定理（或说若干基本内容）

梁自温

摘要：鉴于诸多文献（如文献[1]～[5]）中对于一元一次同余方程（组）的解的有关内容（如如何定义其解与解数及解所属同余类的模等等问题）或与之关联较近的其它有关内容，或说法不规范（也即不统一），或其说无定理根据，甚至定理错误（如文献[2]中的p128中的定理5.2.4的陈述与证明均错误），从而认为很有必要提出这些问题，并加以澄清。

关键词：一元一次同余方程组;基本定理

中图分类号：O156.1     文献标识码：A

1两个定义

定义1：设为一元一次同余方程，，，则称模的同余类中的是同余方程的解（简称是同余方程的解），而称是同余方程关于模的一个解（即中的任意数均使得）。若在的一个完全剩余系中只有整数时，中任两数关于模不同余才是同余方程的解，则称其关于模有个解（以后规定所言一元一次同余方程的解数均是指模而言的）。

注意：可仿上类似定义关于模的解及解数等问题。同时我们约定以后凡提一元一次同余方程的解或解数均是关于模而言的。

定义2：设为一元一次同余方程组，，则称模的同余类中的是同余方程组的解，（简称是同余方程组的解），而称是同余方程组关于模的一个解（即中的任一数均使得），若在模的一个完全剩余系中只有整数才是同余方程组的解，则称其关于模有个解，即等（以后规定所言一元一次同余方程组的解及解数均是关于模而言的）。

注意：可仿上类似定义关于模的解及解数等问题。

2七个引理

引理1：若整数，这里，，，则且该式唯一。

证：设则，由于，，那么即得，且易知该式唯一。现设，则，由于，且，那么，那么，即得且易知该式唯一。由上即知定理成立。

推论1：若整数则，这里证 若，命题成立。设命题对成立，即得到当，，，时，则且该式唯一。由于，则，且该式唯一。由于，于是即得，那么，且该式唯一。

推论2：若整数是一元一次同余方程组的解，则必属于

证：是一元一次同余方程组的解，则得，那么必属于于是据引理得结论。

推论3：若两两互素，则

证：易证而略。

引理2：若为模的一个同余类，则，且当时;当时

证：只证的情况。

，又，那么当取遍时，则不能取遍，那么，由于，那么，由于，那么，即得，由于，那么，于是得，证毕。

引理3：若为模的一组完全剩余系，则存在使

证：，又因为为模的一组完全剩余系，那么存在使，由于，即得，那么

推论：若为模的一组完全剩余系，为模的一个同余类，则

证：由定理可知，当时，存在使中的任一数即存在使中的任一数，即得，毕。

引理4：若为模的一组完全剩余系，，则，且时，为模的个互不相同的同余类

证：只证上半部分，且只证的情况，据设及引理2得，由于，那么                                                                               （1）

又据引理3之推论得 （2）

于是由（1），（2）式得，证毕。

推论：若是个两两不同的正整数，，则

证：据定理得，

，

，

由于，中任两数对模不同余，于是本推论成立。从上易知，这个推论与引理1之推论是完全相同的，另外顺便说一句，上引理之上半部分可见于文献[1]，但其证法不可取。

引理5：一元一次同余方程组有解的充要条件是

证：先证必要性。因为同余方程组有解，则有解，那么存在整数使，即得

同理又可得

上式中的为存在的整数。于是由（1），（2）两式得，即得

（3）

由于，那么

，于是由 （3）式得

下证充分性：

，那么由不定方程性质知存在使，这时若结论不成立，则不存在使，也就是说当为任意整数时恒有，即恒有，便与（4）式矛盾，证毕。

引理6：若是一元一次同余方程的解，，则亦是的解

证：是一元一次同余方程的解，得，，即得，由于，则，那么，由于，那么，即得

推论：若是一元一次同余方程的解，则是同余方程关于模的一个解

证：略。

引理7：若是一元一次同余方程组的解，，则亦是同余方程组的解

证：一元一次同余方程组的解，则得，即得 ，由于，则，那么，由于，那么，即得，同理可得，于是亦是方程组的解。

推论：若是一元一次同余方程組的解，则是方程组关于模的一个解

证：略。

3十一个定理

有解，便可设                                     （4）

上式中的，那么是同余方程组（3）的一个解。

于是由（2）（4）得                               （5）

由（5）的                                    （6）

这是若，则由（6）式得       （7）那么由（7）式得                                    （8）

由于，据引理4得

（9）

同理可得

（10）

于是由（8），（9），（10）式得

（11）

于是由（11）式知中的一个与中的一个一一对应相等（即一个只能与一个对应相等）

现在我们证明（为证明方便，先可令及）若结论不成立，则据（11）式知存在正整数使，即得，矛盾，那么据得

（12）

由于，则由引理4得

（利用同余类之表达式亦可得此结论）                                                          （13）

同理可得               （14）

于是當时，由引理7之推论及（2），（4），（12），（13），（14）得，这就证明了时命题成立。

下只证之情况

若，就可把划为，于是由与的解完全相同知同余方程组与同余方程组的解完全相同，再据及有解

有解时，即得证明（注意上面第一个等价号可用反证法证明而得）

推论1：一元一次同余方程组有解的充要条件是

证：略。

推论2：若，则一元一次同余方程组有解。

证：略。

容易看出上面的推论2的应用范围较文献中p128之定理5.2.4的应用范围要广得多，因此本推论可以完全取代它。

定理10：若又有解，则一元一次同余方程组有解。

证：因为一元一次同余方程组有解，，则可设为的一个解，由于，则由不定方程性质知有关于的整数解，那么，即说明有解，于是可设其解为，由于，则，那么，于是仍由不定方程性质知，即知有解，这样继续下去，定理得证。

定理11：若是个非零整数，，，，则同余方程组有唯一解，其中

证：据引理1之推论1及定理5可证。

很容易看出，中国剩余定理就是上定理之一特殊情况，因此可把这一定理称为第二中国剩余定理罢了。

很多文献在中国剩余定理的证明中根本没有证出其解所属同类的模（其它一些定理的证明也有类似情况），倘要难求出其模，而易找到其解，则，即为一元一次同余方程组的一个解。

参考文献

[1]潘承洞，潘成彪.初等数论[M].北京大学出版社，1997：111.

[2]阎满富，王朝霞.初等数论及其应用[M].中国铁道出版社，1999：123+128.

[3]于秀源，翟维建.初等数论[M].山东教育出版社，2004：133.

[4]乐茂华.初等数论[M].广东高等教育出版社，2003：102.

[5]陈景润.初等数论1[M].科学出版社，1978：84.