第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

任何用類似等式的方式提出兩個同余的量的表達式，稱為同余式。如果它包含一個未知數，當能夠求出一個值（根）滿足同余式時，這個同余式是可解的。現在我們明白了同余式的可解與不可解的含義。提到等式的一些區分方法，也可以對同余方程使用。超越同余方程的例子會在下文中出現；關于代數同余方程，按照未知數的最高次冪，可以分為一次，二次和更高次的同余方程。類似地，對于含幾個未知數的同余方程組，我們可以探討如何對其進行消元。