第2节解一次同余方程_文化伟人代表作图释书系：算术研究-QQ阅读男生武侠网

上QQ阅读APP看书，第一时间看更新

第2节　解一次同余方程

26

根据条目24，当模和a互质时，一次同余方程ax＋b≡c总是有解。假定v是x的一个合适的值，也就是说，同余方程的一个根，可知：所有对于模与v同余的数都是方程的根（参考条目9），所有的根都必须与v同余。因为，如果t是另一个根，av＋b≡at＋b，那么，av≡at并且v≡t（参考条目22）。我们总结：同余式x≡v（mod m）给出了同余方程ax＋b≡c的所有解。

因为通过互余的x的值解同余方程，得出的解总是伴随在一起的，而且就因为这一点同余的数可以按照等价考虑，我们将这种解看作同余方程的唯一的、相同的解。因为同余方程ax＋b≡c没有其他解，所以，我们就说它有且仅有一个解，或说它有且仅有一个根。例如，同余方程6x＋5≡13（mod 11）除了那些与5同余（mod 11）的数没有别的根。这个结论不适用于高次同余方程或未知数被乘以一个与模非互质的数的一次同余方程。

27

现在剩下的事是补充一些关于如何求解同余方程的知识。首先我们观察到：假设模与a互质，形如ax＋t≡u的同余方程的解依赖于ax≡±1；因为如果x≡r满足后者，x≡±（u-t）r就满足前者。因为同余方程ax≡±1（mod b）等价于不定方程ax＝by±1，并且我们现在已经熟悉如何求解这种方程，所以我们只要写出求解不定方程的算法即可。

假设数A，B，C，D，E，…按照下述方式依赖于α，β，γ，δ，…

A＝α，B＝βA＋1，C＝γB＋A，D＝δC＋B，E＝εD＋C，…

为了简便，按照如下方式记录

A＝［α］，B＝［α，β］，C＝［α，β，γ］，D＝［α，β，γ，δ］，…^[1]

现在讨论不定方程ax＝by±1。式中a，b是正数，我们可以假设a≮b。现在，就像求两个数的最大公约数的算法一样，我们通过通常的除法形成等式

a＝αb＋c，b＝βc＋d，c＝γd＋e，…

使得α，β，γ，…，c，d，e，…都是正整数，并且b，c，d，e一直递减直到得到等式m＝μn＋1，这是必然的。结果就是

a＝［n，μ，…，γ，β，α］，b＝［n，μ，…，γ，β］

如果我们取x＝［μ，…，γ，β］，y＝［μ，…，γ，β，α］，当α，β，γ，…，μ，n项数为偶数，我们就有ax＝by＋1；当α，β，γ，…，μ，n项数为奇数，ax＝by-1。证明完毕。

28

欧拉是提出这种类型的不定方程的通解的第一人。在他的方法中，他用其他变量代替x，y，现在这个方法大家很熟悉。拉格朗日处理这个问题的方法有些不同。正如他指出的，从连分数的理论可知，如果分数可以变换为连分数

并且，如果把最后部分删去，结果就变回普通分数。当a和b互质，即ax＝by±1。而且，从两种方法可以推导出同样的算法。拉格朗日的研究出现在Hist. Acad. Berlin（1767）第173页，以及他为欧拉的《代数》法语译本所写的附录上。

29

模与a不互质的同余方程ax＋t≡u容易简化为上述情况。令模为m，δ为a和m的最大公约数。可知，满足模为m的同余方程的x的值也满足模为δ的同余方程（参考条目5）。但是由于δ整除a，则ax≡0（modδ），因此，除非t≡u（modδ），即t-u能够被δ整除，否则同余方程无解。

现在，令a＝δe，m＝δf，t-u＝δk，那么e与f互质。又，ex＋k≡0（mod f）与δex＋δk≡0（modδf）等价，即满足两者中一个的x值也一定满足另一个，反之亦然。因为，当δex＋δk能够被δf整除时，ex＋k就能够被f整除，反之亦然。我们在上面已经看到了怎样求解同余方程ex＋k≡0（mod f），因此可知，如果v是x的一个值，那么x≡v（mod f）给出了同余方程的全部解。

30

当模为合数时，有时运用下面的方法更加简便。

令模为mn，同余方程为ax≡b。首先，求对于模为m的同余方程，并且假设x≡v（mod m/δ）满足方程，式中δ是数m和a的最大公约数，显然，满足模为mn的同余方程ax≡b的x的任何值也满足模为m的同余方程ax≡b，而且x的表达式为v＋（m/δ）x′，式中x′是未知数，但是反过来却不对，因为不是所有的形如v＋（m/δ）x′的数都满足模为mn的同余方程。确定x′的值，使得v＋（m/δ）x′是同余方程ax≡b（mod mn）的解，可以从解同余方程（am/δ）x′＋av≡b（mod mn）或解等价的同余方程（a/δ）x′≡（b-av）/m（mod n）得到。那么，求解任何模为mn的一次同余方程可以简化为求解两个模分别为m和n的同余方程。显然，如果n又是两个因数的乘积，求解这个模为n的同余方程就在于求解模分别为n的两个因数的两个同余方程。总之，求解模为合数的同余方程在于求解模为这个合数的因数的同余方程。如果需要，这些因数可以取质数。

例：假如要求解19x≡1（mod 140）。首先对模为2求解，得到x≡1（mod 2）。令x＝1＋2x′，方程就变成38x′≡-18（mod 140）或者等价方程19x′≡-9（mod 70）。如果再次对于模为2求解这个方程，就有x′≡1（mod 2），再令x′≡1＋2x″，方程就变成38x″≡-28（mod 70）或者19x″≡-14（mod 35）。对模为5求解，得到x″≡4（mod 5）。令x″＝4＋5x‴，方程就变成95x‴≡-90（mod 35）或19x‴≡-18（mod 7）。由此解出x‴≡2（mod 7），并且令x‴＝2＋7x''''，得到x＝59＋140x''''，因此，x≡59（mod 140）是同余方程19x≡1（mod 140）的全部解。

31

等式ax＝b的根可以表示为，类似地，我们用表示同余方程ax≡b的根，并加上同余方程的模来与等式的根相区分。例如，（mod 12）表示任何对于模12同余11^[2]的数。我们前面的研究表明，当a和c的最大公约数不能整除b时，（mod c）没有任何实际意义（或者你更愿意用这个假想的表达式）。除此之外，表达式（mod c）总有真实值且有无限多个。当a与c互质时，它们都和c同余，或者当δ是c和a的最大公约数时，它们都和同余。