第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页）中证明了这则定理。但是我们不想忽略这条定理，因为很多现代作者对这条定理要么论证不充分，要么完全忽略了这条定理；而且这个简单的案例可以让我们理解方法的本质，以后要用同样的方法解决更加艰深的问题。

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

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