第2章　一次同余方程（第13～44条）

第2章　一次同余方程 第13～44条）

第1节　关于质数、因数等的初步定理

13

定理

两个正数如果都小于某个质数，则它们乘积不能被这个质数整除。

设p为质数，若正数a＜p，则找不到任何小于p的正整数b，使得ab≡0（mod p）。

证明

若定理错误，则存在数b，c，d，…，都小于p，使得ab≡0，ac≡0，ad≡0，…（mod p）。令b为其中最小的数，比b更小的数都不具备这个性质。显然b＞1，因为如果b＝1，则ab＝a＜p（通过假设）并且无法被p整除。既然p是质数，则它不能被b整除，但p处于b的两个连续倍数之间，即mb和（m＋1）b。令p-mb＝b′，b′是正数且b′＜b。现在，因为假设ab≡0（mod p），有mab≡0（参见条目7）。使ap≡0减去之，则a（p-mb）＝ab′≡0，即b′为数b，c，d，…中的某个数，且比它们中最小的数更小，这是荒谬的，证明完毕。

14

如果a和b都不能被质数p整除，则乘积ab也不能被p整除。

设α，β是数a，b对于模p的最小正剩余。它们都不是0（通过假设）。如果ab≡0（mod p），则αβ≡0，因为ab≡αβ。但这与前一条定理矛盾。

欧几里得已经在他的《几何原本》（第7章，32页）中证明了这则定理。但是我们不想忽略这条定理，因为很多现代作者对这条定理要么论证不充分，要么完全忽略了这条定理；而且这个简单的案例可以让我们理解方法的本质，以后要用同样的方法解决更加艰深的问题。

1570年的《几何原本》首版英译本 　　《几何原本》全书共13章，由欧几里得于约公元前300年写成，书中主要讨论了平面几何（第1—6章）、数论（第7—9章）、无理数（第10章）和立体几何（第11—13章）。此书是现代数学的基础，在西方，它是仅次于《圣经》而流传最广的书籍。

15

如果数a，b，c，d，…都不能被质数p整除，则它们之积也不能被p整除。

根据前一条定理，ab不能被p整除；因此abc也不能被p整除；类似地，abcd，…也不能被p整除。

16

定理

一个合数只能用一种方式拆分为质因数的乘积。

证明

由基本知识知道，任何合数可以拆分为质因数的乘积，但是，它一般被错误地、理所当然地认为这种拆分不能通过几种不同的方式。假设一个合数A＝aαbβcγ…，其中a，b，c，…为不相等的质数，除此之外还可以用其他方式拆分为质因数。首先，在第2种质因数体系中，不可能出现除了a，b，c，…之外的任何其他质数，因为由质数a，b，c，…组成的合数A不可能被任何其他质数整除。类似地，在第2种质因数体系中任何质因数a，b，c，…都不能缺失，否则就不能整除A（参见条目15）。那么这两种将合数A拆分为质因数的方式的不同只在于某些质因数出现的次数比另外质因数多。令其中某个质因数为p，在第1种因数分解中出现m次，在第2种因数分解中出现n次，令m＞n。现在从每个质因数体系中去掉n次p，结果p在一个系统中出现m-n次，在另一个出现0次。即，对合数A/pn有两种因数分解的方式，其中一种不含因数p，另外一种含m-n个因数p，这与上面的结论矛盾。

17

因此，如果合数A是合数B，C，D，…的乘积，可知B，C，D，…的所有质因数，全都是A的因数，而且每个因数在A的因数分解中出现的次数和在B，C，D，…的因数分解中出现的总次数是相等的。因此，可得一种可以判定B是否整除A的方法。B能够整除A的条件是，在A和B的因数分解中，B中所含的质因数在A中都有，且B中质因数出现的次数不超过在A中出现的次数。如果这两者任意一条不能满足，则B不能整除A。

从组合演算中可知，如上文a，b，c，…是不同质数，A＝aαbβcγ…，则A有（α＋1）（β＋1）（γ＋1）…个不同的除数，包括1和它自己。

18

如果A＝aαbβcγ…，K＝kκlλmμ…，质数a，b，c，…，k，l，m，…都各不相同，那么A和K没有除了1之外的公约数。换句话说，它们之间互质。

给定许多个数A，B，C，…，它们的最大公约数可以按如下方式找到。使所有的数分解为它们的质因数，从这些质因数中提取出A，B，C，…共有的质因数（如果一个都没有，则这些数没有公约数）。然后记下每个质因数在A，B，C，…中出现的次数，或者说记下每个质因数在A，B，C，…中的方幂数。最后给每个质因数赋予其在A，B，C中出现的最小方幂之后，它们的乘积就是要求的最大公约数。

求最小公倍数时，方法如下：先收集能整除A，B，C，…中任何一个数的所有质数；再给它们赋予在A，B，C，…中最大的方幂；最后求它们的乘积，其结果为要求的最大公倍数。

例如：令A＝504＝23×32×7，B＝2880＝26×32×5，C＝864＝25×33。对于A，B，C，有公共因数2，3，最小方幂分别为3，2，则最大公约数为23×32＝72；所有质数分别为2，3，5，7，最大方幂分别为6，3，1，1，则最小公倍数为26×33×5×7＝60480。

因为证明简单，所以此处省略。而且，从基本知识可知如何将数A，B，C，…进行因数分解。

19

如果数a，b，c，…都和某个数k互质，则它们的乘积abc…也和k互质。

因为数a，b，c，…与k都没有公共的质因数，而且因为乘积abc…中没有属于a，b，c，…的质数之外的质数，因此乘积abc…与k没有公共质因数。因此从前文知，k与abc…互质。

如果数a，b，c，…互质，且每个数都可以整除数k，则它们的乘积能整除k。

从条目17、18可以容易得出这条结论。因为，如果p是乘积abc…中出现了π次的质除数，可知，数a，b，c，…中的某个数必定含有相同的质除数π次。因此k也包含p——这个整除k的数——π次。相似地，对乘积abc…的所有其他质除数也成立。

因此，如果两个数m和n都对于几个模a，b，c，…同余，且这几个模互质，那么，这两个数也对于模的乘积同余。因为m-n能够被a，b，c，…中的每一个整除，m-n也可以被它们的乘积整除。

最后，若a和b互质，且ak能被b整除，则k也能被b整除。因为ak既能被a整除，又能被b整除，它也能被ab整除，即：

为整数。

20

假设a，b，c，…为互不相等的质数，且A＝aαbβcγ…，如果A是某个方幂，例如kn，那么，所有的指数α，β，γ，…都能被n整除。

因为数k没有除a，b，c，…外的质因数。令k含α′次因数a，则kn或A含nα′次因数a，因此nα′＝α并且

是整数。与此类似，

，…也是整数。

21

当a，b，c，…互质，而且乘积abc…是方幂，例如kn，那么a，b，c，…每个数都是n次方幂。

令a＝lλmμpπ，…，其中，l，m，p，…都是不同的质数，由假设知，它们都不是数b，c，…的因数。因此乘积abc…含有λ次因数l，μ次因数m，…。由前一条知，λ，μ，π，…都可以被n整除，因此

是整数。对b，c，…同样成立。

我们的研究从这些关于质数的结论开始，现在转而探讨更接近我们目的的主题。

22

假设数a，b都能够被另一个数k整除。若它们关于模m同余，且m与k互质，则

和

关于相同的模同余。

由假设可知，a-b可以被k整除，也可以被m整除，因此（参见条目19）

可以被m整除，即

（mod m）。

如果让其他假设不变，令m和k有最大公约数e，则

。因为

和

互质，且a-b可以被k和m整除，所以

可以被

和

整除，因此可以被

整除，即

可以被

整除，也就意味着

。

23

若a和m互质，e和f相对于模m非同余，则ae，af相对于模m非同余。

这里只是条目22的逆定理。

显然，如果把a与0到m-1中的每个整数相乘，并把每个乘积简化为对于模m的最小剩余，那么这些最小剩余都不相等。并且，因为一共有m个剩余，所有剩余都不大于m，所以，从0到m-1的数都出现在这些剩余中。

24

给定数a，b；x为不确定数或者是变量。表达式ax＋b对于模m可以与任何数同余，其条件是m与a互质。

令与表达式ax＋b同余的数为c，令c-b对于模m的最小正剩余为e。从前一条定理可知，必定有一个值x＜m使得乘积ax对于模m的最小剩余为e；令这个值为v，则有av≡e≡c-b，因此av＋b≡c（mod m）。这就是需要做的。

25

任何用类似等式的方式提出两个同余的量的表达式，称为同余式。如果它包含一个未知数，当能够求出一个值（根）满足同余式时，这个同余式是可解的。现在我们明白了同余式的可解与不可解的含义。提到等式的一些区分方法，也可以对同余方程使用。超越同余方程的例子会在下文中出现；关于代数同余方程，按照未知数的最高次幂，可以分为一次，二次和更高次的同余方程。类似地，对于含几个未知数的同余方程组，我们可以探讨如何对其进行消元。

第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的最大公约数时，它们都和

同余。

人们可以对这些表达式做类似于简分数的运算。我们这里指出一些可以轻易地从前面讨论中推导出来的性质。

1．如果对于模c，a≡α，b≡β，那么表达式

（mod c）和

（mod c）等价。

2．

（mod cδ）和

（mod c）等价。

3．当k和c互质时，

（mod c）和

（mod c）等价。

我们还可以引用很多类似的定理，但是它们都很简单，对后续的讨论也不太有用，我们继续进行其他讨论。

第3节　对于给定模求与给定剩余同余的数的方法

32

从上面的结论，解决问题“对于给定的模，求与给定剩余所同余的数的方法”是很容易的，在下面的讨论中也会很有用。指定模A，B，我们求数z，对于模A，B分别与数a，b同余。所有z的值都形如Ax＋a，x是未知数，而且要满足Ax＋a≡b（mod B）。现在如果数A，B的最大公约数是δ，同余方程的完整解的形式为x≡v（mod B/δ）或者用等价的等式表达，x＝v＋kB/δ，k为任意整数。因此，公式Av＋a＋kAB/δ包括了z的所有值，即z≡Av＋a（mod AB/δ）是这个问题的完整解。如果我们在模A，B的基础上再加一个模C，并且对于模C，z≡c，我们可以按照同样的方式开展，因为先前两个条件已经合并为一个。因此，如果AB/δ和C的最大公约数为e，并且假设同余方程（AB/δ）x＋Av＋a≡c（mod C）的解为x≡w（mod C/e），那么问题的解完全可以通过同余方程z≡ABw/δ＋Av＋a（mod ABC/δe）解得。我们观察到AB/δ是A和B的最小公倍数，ABC/δ是数A，B和C的最小公倍数，那么容易推出不论有多少个模A，B，C，…，如果它们的最小公倍数是M，全部的解都可以用z≡r（mod M）来表示。但是当并非所有的辅助同余方程都可解时，我们断定这个问题存在不可解的情况。但是显然，当所有的数A，B，C，…互质时，这种情况是不可能发生的。

例如，令数A，B，C，a，b，c分别为504，35，16，17，-4，33。这里的两个条件z≡17（mod 504）和z≡-4（mod 35）等价于一个条件z≡521（mod 2520），加上条件z≡33（mod 16），我们最终得到z≡3041（mod 5040）。

33

当所有数A，B，C，…都互质，可知它们的乘积是它们的最小公倍数。在这种情况下，多个同余式z≡a（mod A），z≡b（mod B），z≡c（mod C）…合起来就与单个同余式z≡r（mod R）等价，式中R是数A，B，C，…的乘积。反过来，单个条件z≡r（mod R）也可以分解为多个条件，即如果R以任意方式分解为互质的因数A，B，C，…，那么条件z≡a（mod A），z≡b（mod B），z≡c（mod C），…就把原始条件全部涵盖。这条结论不仅提供了一个发现方程无解的快捷的方法，也是一种令人满意的、优雅的运算方式。

34

如上，令z≡a（mod A），z≡b（mod B），z≡c（mod C）。将所有模都分解为互质的因数：A分解为A′A″A‴，…；B分解为B′B″B‴，…；使得数A′，A″，…，B′，B″，…要么都是质数，要么都是质数幂。如果数A，B，C，…中的任何一个数已经是质数或质数幂，则不用分解。可知，上述条件可以用下面的条件来代替：z≡a（mod A′），z≡a（mod A″），z≡a（mod A‴），…；z≡b（mod B′），z≡b（mod B″），…；…。现在如果不是所有的数A，B，C，…都互质（例如A和B非互质），显然A，B的所有质除数并非都各不相同。在因数A，A″，A‴，…中必定有一个因数在B′，B″，B‴，…能够找到等于它，或是它的倍数，或是它的除数的因数。假设第一个可能性是A′＝B′。那么条件z≡a（mod A′）和条件z≡b（mod B′）必定相同，即a≡b（mod A′或B′），因此其中一个可以忽略。但是如果z≡a（mod A′）不成立，这个问题就无解。其次，假设B′是A′倍数，那么条件z≡a（mod A′）就一定包含在条件z≡b（mod B′）中，即从后者推出的z≡b（mod A′）必须与前者相同。由此可以推出条件z≡a（mod A′）可以忽略，除非它与其他条件矛盾（如果这样问题便无解）。当所有多余的条件都忽略以后，因数A′，A″，A‴，…；B′，B″，B‴，…；…中剩下的模就都是互质的。然后我们就能确定问题是否可解，并按照上文描述的方法求解。

35

例如，如果按照上文（参考条目32），z≡17（mod 504），z≡-4（mod 35）和z≡33（mod 16），那么这些条件可以分解为下面的条件：z≡17（mod 8），z≡17（mod 9），z≡17（mod 7），z≡-4（mod 5），z≡-4（mod 7），z≡33（mod 16）。在这些条件中，z≡17（mod 8）和z≡17（mod 7）可以忽略，因为前者已经包含在条件z≡33（mod 16）中，后者同于条件z≡-4（mod 7）。还剩条件

并且从这些条件我们有z≡3041（mod 5040）。显然，通常这样做会比较方便：把从同一个条件推导出的剩下的条件分别重新组合：例如，当条件z≡a（mod A′），z≡a（mod A″），…中的一些被去掉之后，剩下的全部条件可以用z≡a取代，它的模是A′，A″，A‴，…中所有剩下的模的乘积。因此，在我们的例子中，条件z≡-4（mod 5），z≡-4（mod 7）都被条件z≡-4（mod 35）所取代。进一步可知，就简化计算来说，去掉多余的条件并不是无关紧要的。但是，讨论这些内容或其他具体的技巧并不是我们的目的，这些方法的学习通过自己实践比听他人讲述更加容易。

36

当所有的模A，B，C，D，…都彼此互质，通常采用下面的方法更好。确定一个数α，它对于模A同余于1，而对于剩余所有模的乘积同余为0，即α是BCD…乘以表达式1/BCD…（mod A）的一个值（优先选取最小值）（参考条目32）。类似地，令β≡1（mod B）及β≡0（mod ACD…），γ≡1（mod C）及γ≡0（mod ABD…），…。因此，如果我们求z使得它对于模A，B，C，D，…分别同余于a，b，c，d，…，我们可以取

z≡αa＋βbγc＋δd＋…（mod ABCD…）

因为，显然αa≡a（mod A）且剩下所有的数βb，γc，δd，…都对于模A同余为0，所以z≡a（mod A）。对于其他的模可以做类似证明。当我们解几个同样类型的问题，它们中的所有的模A，B，C，…的值保持不变，那么这种解法要优于前一种解法，因为α，β，γ，…取同样的值。在年代学中有这样的问题：给定某年的小纪，黄金数以及太阳活动周，确定它的儒略年份。在这里可以取A＝15，B＝19，C＝28；因为表达式1/（19×28）（mod 15）或1/532（mod 15）的值是13，所以α＝6916，按照同样的方法可得β＝4200和γ＝4845。因此，我们要求的数是6916a＋4200b＋4845c的最小剩余，其中a是小纪，b是黄金数，c是太阳活动周。

第4节　多元线性同余方程组

37

关于一元一次同余方程我们已经阐述得比较充分，下面讨论多元同余方程组。如果我们完整地讨论每一项内容，本章就会没完没了地继续下去。因此，我们建议只讨论值得我们注意的一些问题，并且只探讨这些问题的某几个方面，以后有机会再充分讨论。

1．如同求解方程组一样，同余方程的个数必须和待求未知数的个数相同。

2．因此，我们提出同余方程组

方程组中方程的个数与未知数x，y，z，…的个数是一样的。

现在我们确定数ξ，ξ′，ξ″，…，使得

并且，所有这些数都是整数，没有公约数。显然，从线性方程理论可知这是可能的。类似地，我们确定数v，v′，v″，…；ζ，ζ′，ζ″，…；…，使得

3．显然，如果同余方程A，A′，A″，…，乘以ξ，ξ′，ξ″，…，然后乘以v，v′，v″，…；…然后相加，我们就得到如下的同余方程组

为了简便，我们按如下形式记录

Σ（aξ）x≡Σ（fξ），Σ（bv）y≡Σ（fv），Σ（cζ）z≡Σ（fζ），…

4．不同的情况必须区分清楚。

首先，当所有系数Σ（aξ），Σ（bv），Σ（cζ），…都和同余方程的模m互质时，我们可以按照已经总结的结论求解，完整解可以通过同余式x≡p（mod m），y≡q（mod m），…给出。[3]

例如，给定同余方程组

x＋3y＋z≡1，4x＋y＋5z≡7，2x＋y＋z≡3（mod 8）

我们求得ξ＝9，ξ′＝1，ξ″＝-14，所以有-15x≡-26和x≡6（mod 8）。同理求得15y≡-4，15z≡1，所以有y≡4，z≡7（mod 8）。

5．其次，当并非所有系数Σ（aξ），Σ（bv），Σ（cζ），…都与模互质时，令α，β，γ，…，分别为模m和Σ（aξ），Σ（bv），Σ（cζ），…的最大公约数。可知除非这些数能够分别整除Σ（fξ），Σ（f v），Σ（fζ），否则这个问题是无解的。但是，如果这些条件得到满足，则第3部分中的同余方程可以由下列形如x≡p（mod m/α），y≡q（mod m/β），z≡r（mod m/γ），…的同余式完全解出；或者，也可以这样表达，有α个不同的x的值［与m不同余，例如p，p＋m/α，…，p＋（α-1）m/α］，β个不同的y的值，…满足这个同余方程组；显然，所给的这组同余方程的所有解（如果有解）将在它们中求得。但是，这个结论不可逆，因为，一般地，不是x的所有值，y的所有值，z的所有值，…的全部组合都给出了问题的解，而只是它们中的某些满足了一个或更多的限制性同余条件的组合给出了问题的解。但是，因为下面的讨论并不需要这个问题的所有解，我们将不做进一步讨论，这里只举一个例子来演示一下。

给定这个同余方程组

3x＋5y＋z≡4，2x＋3y＋2z≡7，5x＋y＋3z≡6（mod 12）

这里ξ，ξ′，ξ″；v，v′，v″；ζ，ζ′，ζ″分别等于1，-2，1；1，1，-1；-13，22，-1。由此可得4x≡-4，7y≡5，28z≡96。由此我们可以得出x有4个值，即x≡2，5，8，11；y有1个值，即y≡11；z有4个值，即z≡0，3，6，9（mod 12）。为了知道x的值和z的值的哪些组合可以使用，我们在所给的这组同余方程中用2＋3t，11，3u分别替代x，y，z，同余方程组变成

57＋9t＋3u≡0，30＋6t＋6u≡0，15＋15t＋9u≡0（mod 12）

它们等价于

19＋3t＋u≡0，10＋2t＋2u≡0，5＋5t＋3u≡0（mod 4）

由于其中的第一式应有u≡t＋1（mod 4），当把这个值代入其他2个同余方程，也能满足这2个同余方程。我们总结，x的值2，5，8，11（分别令t≡0，1，2，3得到）必须分别与z≡3，6，9，0结合，我们一共可以得到4组解

x≡2，5，8，11（mod 12）

y≡11，11，11，11（mod 12）

z≡3，6，9，0（mod 12）

那么我们就结束了本章的讨论内容。不过我们还要补充几条根据相似的原理得出的定理，这些定理我们以后经常要用到。

第5节　一些定理

38

问题

求小于给定正数A，且与A互质的正数的个数。

为了简便，我们在给定的数前面加上前缀φ来表示与之互质且小于它的正数的个数。因此，我们求φA。

1．当A为质数，显然所有从1到A-1的数都与A互质，那么在这种情况下

φA＝A-1

2．当A是质数幂，例如A＝pm，所有能被p整除的数都与A不互质，但是其他的数都与A互质。所以在pm-1个数中，必须摒弃这些数：p，2p，3p…（pm-1-1）p。因此剩下的数有pm-1-（pm-1-1）个，即pm-1（p-1）个。则

φA＝pm-1（p-1）

3．剩下的情况可以通过以下定理简化为前两种情况：如果A分解为互质的因数M，N，P，…，则

为证明之，令与M互质且小于M的数为m，m′，m″，…，所以它们的个数为φM。类似地，令分别与N，P，…互质且小于N，P，…的数为n，n′，n″，…；p，p′，p″，…；…，所以每组数的个数分别为φN，φP，…，显然，所有与乘积A互质的数一定分别对于单独的因数M，N，P，…互质，并且反之亦然（参见条目19）；而且，所有对于模M与m，m′，m″，…中的任何一个数同余的数都与M互质，并且反之亦然。对于N，P，…也有类似的结论。那么问题就可以简化如下：确定有多少小于A的，且对于模M与m，m′，m″，…中的其中一个数同余，且对于模N与n，n′，n″，…中的其中一个数同余，…。但是从条目32条可知，对于模M，N，P，…中的每一个都有给定剩余的所有的数一定是对它们的乘积A同余的。因此，小于A且对于模M，N，P，…都有给定剩余的数有且只有一个。因此，我们要求的个数就等于m，m′，m″，…的各个值，n，n′，n″，…的各个值，p，p′，p″，…的全部组合个数。从组合理论，组合的个数为

或者，更优雅地表示为

例：令A＝60＝22×3×5，那么φA＝（1/2）×（2/3）×（4/5）×60＝16。与60互质的数有1，7，11，13，17，19，23，29，31，37，41，43，47，49，53，59。

这个问题的第一个解法出现在欧拉的论文Theorema arithmetica nova methodo demonstrata中。这个解法在另一篇名为Speculationes circa quasdam insignes proprietates numerorum的论文中重复出现。

39

如果我们把函数φ定义为：φA表示不大于A且与A互质的数的个数。显然，φ1不等于0，而等于1。在其他情况下没有任何变化。采用这个定义后，我们得到如下定理

如果a，a′，a″，…都是A的因数（包括1和A），那么φa＋φa′＋φa″＋…＝A。

例：令A＝30，那么φ1＋φ2＋φ3＋φ5＋φ6＋φ10＋φ15＋φ30＝1＋1＋2＋4＋2＋4＋8＋8＝30。

证明

将所有与a互质且不大于a的数乘以A/a；同样地，将所有与a′互质且不大于a′的数乘以A/a′…，我们就会得到（φa＋φa′＋φa″＋…）个都不大于A的数。但是：

1．所有这些数都不相等。因为显然由同一个除数A所生成的数都不相等。现在如果由两个不同的除数M和N以及两个与M和N互质的数μ和v得出两个相等的数，即，如果（A/M）μ＝（A/N）v，就有μN＝vM。假设M＞N，因为M与μ互质，又因为M可以整除μN，所以M必须整除N，那么一个较大的数就整除一个较小的数，这是不可能的。

2．所有的数1，2，3，…A，都包含在这些数中。令t为不大于A的任意正整数，δ是A和t的最大公约数。那么A/δ就是A的除数且与t/δ互质。显然，这个数t可以在由除数A/δ生成的数中找到。

3．由此可以推出这些数的个数为A，所以

φa＋φa′＋φa″＋…＝A

证明完毕。

40

令数A，B，C，D，…的最大公约数为μ。我们总是可以确定数a，b，c，d，…，使得：aA＋bB＋cC＋…＝μ。

证明

首先只考虑两个数A和B，并且令它们的最大公约数为λ。那么同余方程Ax≡λ（mod B）是可解的（参考条目30）。令同余方程的根x≡α（λ-Aα）/B＝β。那么我们可以得到αA＋βB＝λ。

如果有第三个数C，令λ′是λ和C的最大公约数，并且确定数k，γ使得kλ＋γC＝λ′，那么kαA＋kβB＋γC＝λ′。

显然，λ′是数A，B，C的公约数，实际上是它们的最大公约数，因为如果有更大的公约数θ，我们就能得到

是整数，这是不可能的。

所以我们令kα＝a，kβ＝b，γ＝c，λ′＝μ就完成了证明。

如果有更多的数，我们可用同样的方式展开。并且，如果数A，B，C， D，…没有公约数，显然我们能得到aA＋bB＋cC＋…＝1。

41

如果p是质数且我们有p个元素，其中可以有任意多个元素相同，但不能全部相同，那么这些元素的所有不同的排列个数可以被p整除。

例：5个元素A，A，A，B，B可以以10种不同的方式排列。

这个定理的证明可以轻松地从大家熟悉的排列理论推导出。因为，如果在这些元素中有a个元素是A，b个元素是B，c个元素是C，…（数a，b，c，…中的任何数均可为1），那么a＋b＋c＋…＝p。并且排列的个数将会是

现在可知此分数的分子可以被分母整除，因为排列数必须是整数。但是，分子能被p整除，然而由小于p的因数构成的分母不能被p整除（参考条目15）。因此，排列数可以被p整除（参考条目19）。

但是我希望仍会有些读者欢迎下面的证明。

考虑相同元素的两种排列。假设元素的顺序的区别仅在于一个排列中第1个元素出现在另一个排列的不同的位置上，而其余所有元素仍按照相同的顺序排列在它前后两边。进一步假设，如果我们考虑一个排列中的第1个和最后1个元素，看到这两个元素在另外一个排列中第1个元素紧随着最后1个元素出现，这两种排列我们称之为相似排列。[4]因此，在我们的例子中，排列ABAAB和ABABA是相似排列，因为，在前一个排列中位于第1，第2，…的位置的元素，在后一个排列中占据了第3，第4，…的位置，所以

它们是按照相同的接替顺序排列。现在因为任意排列包含p个元素，明显我们能够找到p-1个排列与其相似，只需将第1个排列中的第1的位置的元素向后移到第2，第3，…的位置。显然，如果这些排列都不相同，排列数可以被p整除，因为排列数是所有不相似的排列的p次整数倍。假设我们有两组排列PQ…TV…YZ；V…YZPQ…T，其中一组是通过另一组的元素向前移动得出的。进一步假设两组排列是相同的，即P＝V，…，令前一组排列中排第1位的元素P在后一组排列中为第n＋1个。那么在后一组排列中第n＋1个元素就与前一个排列中的第1个元素相等，第n＋2个元素就与第2个相等，第2n＋1个就与第1个相等，第3n＋1个就与第1个相等，…。一般地，后一个排列的第kn＋m个元素等于前一个排列的第m个元素（前提是当kn＋m大于p，我们或者考虑排列V…YZPQ…T是不断地从头开始重复，或者可以把它看作从kn＋m中减去小于它且数值上是最接近它的p的倍数之差）。因此，如果确定数k使得kn≡1（mod p），这是可以做到的。因为p是质数，那么一般可以得到第m个元素与第m＋1元素相同，或每一项都与后一项相同，即，所有元素都相同，这与假设矛盾。

42

如果两个函数形如

它们的系数A，B，C，…N；a，b，c，…n都是有理数但不都是整数，并且如果（P）和（Q）的乘积为

，

那么，不是所有的系数

都能为整数。

证明

将所有系数A，B，…，a，b，…用最简分数表示，任意选择一个质数p，它整除这些分数中的一个或多个分母。假定p能够整除（P）中一个分数系数的分母，如果我们用（Q）除以p，可知在（Q）/p中至少有一个分数系数的分母以p作为它的因数（例如，第一项的系数1/p）。不难看出，在（P）中总是有一项的分数系数的分母含有的p的方幂大于所有在它前面的分数系数的分母所含有的p的方幂，且不小于所有在它后面的项的分数系数的分母所含有的p的方幂。令这一项为Gxg，并且令G的分母中p的方幂等于t。在（Q）/p中可以找到相似的一项。令这一项为Γxy，并且令Γ的分母中p的方幂等于τ。显然，t＋τ的值至少等于2。现在我们证明在（P）和（Q）的乘积中的项xg＋y的系数是分数，分母含p的t＋τ-1次幂。

令（P）中在Gxg前面的项分别为′ Gxg＋1，″ Gxg＋2，…，在Gxg后面的项分别为G′xg-1，G″xg-2，…；类似地，令Γxy前面的项为′Γxy＋1，″Γxy＋2，…，在Γxy后面的项为Γ′xy-1，Γ″xy-2，…。显然，在（P）和（Q）/p的乘积中，项xg＋y的系数为GΓ＋′GΓ′＋″GΓ″＋…＋′ΓG′＋″ΓG″＋…

项GΓ是一个分数，如果用最简分数的形式表达，它的分母中会含有p的t＋τ次幂。如果其他任意一项为分数，那么，它的最简形式中的分母一定只能含有较低次的p的幂。因为，这些分母中的每一项都是两个因数的乘积，而这两个因数，要么是其中的一个含有的p的方幂不大于t，而另一个含有的p的方幂则小于τ；要么是其中的一个含有的p的方幂不大于τ，而另一个含有的p的方幂则小于t。因此，GΓ可表示为e/（fpt＋τ），而其他所有的项都可以表示为e′/（f′pt＋τ-δ），式中δ是正数，e，f，f′都不含因数p，这些项的和式为

它的分子不能被p整除，所以这个分数不可能经过简化使其分母所含的p的方幂比t＋τ低。因此，在（P）和（Q）的乘积中，项xg＋y的系数为

即，这是一个分母含有p的t＋τ-1次幂的分数。证明完毕。

43

m次同余方程Axm＋Bxm-1＋Cxm-2＋…＋Mx＋N≡0，它的模是不能整除A的质数p，不能有多于m种不同的解法，即，它不能有多于m个对于p不同余的根（参考条目25和26）。

假如这条定理不成立，那么我们就有不同次数m，n，…的同余方程分别有多于m，n，…个根。设其中最低的次数是m，那么所有类似的较低次的同余方程都符合我们的定理。因为我们已经讨论过一次同余方程（参考条目26），这里的m会大于或等于2。令同余方程

Axm＋Bxm-1＋Cxm-2＋…＋Mx＋N≡0

至少有m＋1个根x＝α，x＝β，x＝γ，…。我们假定（这是合理的）所有的数α，β，γ，…都是正的且小于p，并且α是其中最小的。现在在这个同余方程中令y＋α替换x，结果就是

A′ym＋B′ym-1＋C′ym-2＋…＋M′y＋N′≡0

显然，如果y≡0，y≡β-α或y≡γ-α，…都能满足同余方程，那么，所有这些根都各不相同，它们的个数为m＋1。但是因为y≡0是方程的根，N′能够被p整除。因此，m个值β-α，γ-α，…中的每一个都将满足同余方程

y（A′ym-1＋B′ym-2＋…＋M′）≡0（mod p）

由于这m个值都大于0小于p，所以它们也都将满足

A′ym-1＋B′ym-2＋…＋M′≡0（mod p）（参考条目22）

即m-1次同余方程有m个根。而这与我们的定理矛盾（显然A′＝A，所以满足不能被p整除的要求），因为，我们已经假定对所有次数小于m的这样的同余方程定理是成立的。

44

我们这里假定模p不能整除最高次项的系数，但定理并不限于这种情况。因为，如果首项系数，或者还有其他项的系数被p整除，可以安全地忽略这些项，原先的同余方程简化为较低次的同余方程，除非这个同余方程的全部原系数均被p整除，否则首项系数将不被p整除，这同余方程就将是一个恒等的同余式，其未知数的值则完全不确定。

这个定理首先由拉格朗日提出和证明（Hist. Acad. Berlin，1768，第192页）。此定理也出现在勒让德的论文Recherches d，Analyse indeterminée中。在Novi comm. Acad. Petrop中，欧拉证明了同余方程xn-1≡0不存在多于n的不同的根。尽管这只是一种特例，但这位著名数学家使用的方法可以很容易应用于所有同余方程。他之前在Novi comm. acad. Petrop.上解决了一个更加特殊的情形，但这种方法不能应用于一般情形。在第8章[5]，我们会演示证明这则定理的另一种方法。尽管乍一看来这些方法似乎不同，想要对这些方法做比较的专家会发现它们的原理都是一样的；但是，因为这则定理在这里仅仅是作为一个引理来讨论，并且对其完整阐述与本章的关系不大，因此我们不会停下来专门讨论合数模。

[1] 这种关系可以更加普遍地讨论，我们可能在其他情况下讨论。这里我们只给出两种对目前的探讨有用的命题： 　　1）［α，β，γ，…，λ，μ］·［β，γ，…，λ］-［α，β，γ，…，λ］·［β，γ，…，λ，μ］＝±1，其中α，β，γ，…，λ，μ的项数为偶数时取＋号，项数为奇数时取-号。 　　2）数的顺序可以颠倒：［α，β，γ，…，λ，μ］＝［μ，λ，…，γ，β，α］。证明简单，这里略去。

[2] 它同样可以表示为

（mod 12）。

[3] 这条结论需要证明，但我们这里没有给出。从我们的分析只能得出未知数x，y，…，的其他值一定不能解这个同余方程组，但我们并没有证明这些值能够满足方程，因为这组方程可能是无解的。在处理线性方程组时也常出现类似错误。

[4] 如果把相似排列设想为表示在一个圆周上，使得最后一个元素与第一个元素相连，那么这些排列就完全一样了，因为在圆周上没有什么位置可以成为第一个或者最后一个。

[5] 第8章没有发表。