第2節(jié)　解一次同余方程

26

根據(jù)條目24，當(dāng)模和a互質(zhì)時(shí)，一次同余方程ax＋b≡c總是有解。假定v是x的一個(gè)合適的值，也就是說，同余方程的一個(gè)根，可知：所有對(duì)于模與v同余的數(shù)都是方程的根（參考條目9），所有的根都必須與v同余。因?yàn)椋绻?span id="1yqdlzw" class="kindle-cn-italic">t是另一個(gè)根，av＋b≡at＋b，那么，av≡at并且v≡t（參考條目22）。我們總結(jié)：同余式x≡v（mod m）給出了同余方程ax＋b≡c的所有解。

因?yàn)橥ㄟ^互余的x的值解同余方程，得出的解總是伴隨在一起的，而且就因?yàn)檫@一點(diǎn)同余的數(shù)可以按照等價(jià)考慮，我們將這種解看作同余方程的唯一的、相同的解。因?yàn)橥喾匠?span id="uwpty4d" class="kindle-cn-italic">ax＋b≡c沒有其他解，所以，我們就說它有且僅有一個(gè)解，或說它有且僅有一個(gè)根。例如，同余方程6x＋5≡13（mod 11）除了那些與5同余（mod 11）的數(shù)沒有別的根。這個(gè)結(jié)論不適用于高次同余方程或未知數(shù)被乘以一個(gè)與模非互質(zhì)的數(shù)的一次同余方程。

27

現(xiàn)在剩下的事是補(bǔ)充一些關(guān)于如何求解同余方程的知識(shí)。首先我們觀察到：假設(shè)模與a互質(zhì)，形如ax＋t≡u的同余方程的解依賴于ax≡±1；因?yàn)槿绻?span id="a3b34xc" class="kindle-cn-italic">x≡r滿足后者，x≡±（u-t）r就滿足前者。因?yàn)橥喾匠?span id="1g9kgnc" class="kindle-cn-italic">ax≡±1（mod b）等價(jià)于不定方程ax＝by±1，并且我們現(xiàn)在已經(jīng)熟悉如何求解這種方程，所以我們只要寫出求解不定方程的算法即可。

假設(shè)數(shù)A，B，C，D，E，…按照下述方式依賴于α，β，γ，δ，…

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

為了簡便，按照如下方式記錄

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

現(xiàn)在討論不定方程ax＝by±1。式中a，b是正數(shù)，我們可以假設(shè)a≮b。現(xiàn)在，就像求兩個(gè)數(shù)的最大公約數(shù)的算法一樣，我們通過通常的除法形成等式

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

使得α，β，γ，…，c，d，e，…都是正整數(shù)，并且b，c，d，e一直遞減直到得到等式m＝μn＋1，這是必然的。結(jié)果就是

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

如果我們?nèi)?span id="lwhtpfo" class="kindle-cn-italic">x＝［μ，…，γ，β］，y＝［μ，…，γ，β，α］，當(dāng)α，β，γ，…，μ，n項(xiàng)數(shù)為偶數(shù)，我們就有ax＝by＋1；當(dāng)α，β，γ，…，μ，n項(xiàng)數(shù)為奇數(shù)，ax＝by-1。證明完畢。

28

歐拉是提出這種類型的不定方程的通解的第一人。在他的方法中，他用其他變量代替x，y，現(xiàn)在這個(gè)方法大家很熟悉。拉格朗日處理這個(gè)問題的方法有些不同。正如他指出的，從連分?jǐn)?shù)的理論可知，如果分?jǐn)?shù)可以變換為連分?jǐn)?shù)

并且，如果把最后部分刪去，結(jié)果就變回普通分?jǐn)?shù)。當(dāng)a和b互質(zhì)，即ax＝by±1。而且，從兩種方法可以推導(dǎo)出同樣的算法。拉格朗日的研究出現(xiàn)在Hist. Acad. Berlin（1767）第173頁，以及他為歐拉的《代數(shù)》法語譯本所寫的附錄上。

29

模與a不互質(zhì)的同余方程ax＋t≡u容易簡化為上述情況。令模為m，δ為a和m的最大公約數(shù)。可知，滿足模為m的同余方程的x的值也滿足模為δ的同余方程（參考條目5）。但是由于δ整除a，則ax≡0（modδ），因此，除非t≡u（modδ），即t-u能夠被δ整除，否則同余方程無解。

現(xiàn)在，令a＝δe，m＝δf，t-u＝δk，那么e與f互質(zhì)。又，ex＋k≡0（mod f）與δex＋δk≡0（modδf）等價(jià)，即滿足兩者中一個(gè)的x值也一定滿足另一個(gè)，反之亦然。因?yàn)椋?dāng)δex＋δk能夠被δf整除時(shí)，ex＋k就能夠被f整除，反之亦然。我們?cè)谏厦嬉呀?jīng)看到了怎樣求解同余方程ex＋k≡0（mod f），因此可知，如果v是x的一個(gè)值，那么x≡v（mod f）給出了同余方程的全部解。

30

當(dāng)模為合數(shù)時(shí)，有時(shí)運(yùn)用下面的方法更加簡便。

令模為mn，同余方程為ax≡b。首先，求對(duì)于模為m的同余方程，并且假設(shè)x≡v（mod m/δ）滿足方程，式中δ是數(shù)m和a的最大公約數(shù)，顯然，滿足模為mn的同余方程ax≡b的x的任何值也滿足模為m的同余方程ax≡b，而且x的表達(dá)式為v＋（m/δ）x′，式中x′是未知數(shù)，但是反過來卻不對(duì)，因?yàn)椴皇撬械男稳?span id="xqi1nus" class="kindle-cn-italic">v＋（m/δ）x′的數(shù)都滿足模為mn的同余方程。確定x′的值，使得v＋（m/δ）x′是同余方程ax≡b（mod mn）的解，可以從解同余方程（am/δ）x′＋av≡b（mod mn）或解等價(jià)的同余方程（a/δ）x′≡（b-av）/m（mod n）得到。那么，求解任何模為mn的一次同余方程可以簡化為求解兩個(gè)模分別為m和n的同余方程。顯然，如果n又是兩個(gè)因數(shù)的乘積，求解這個(gè)模為n的同余方程就在于求解模分別為n的兩個(gè)因數(shù)的兩個(gè)同余方程。總之，求解模為合數(shù)的同余方程在于求解模為這個(gè)合數(shù)的因數(shù)的同余方程。如果需要，這些因數(shù)可以取質(zhì)數(shù)。

例：假如要求解19x≡1（mod 140）。首先對(duì)模為2求解，得到x≡1（mod 2）。令x＝1＋2x′，方程就變成38x′≡-18（mod 140）或者等價(jià)方程19x′≡-9（mod 70）。如果再次對(duì)于模為2求解這個(gè)方程，就有x′≡1（mod 2），再令x′≡1＋2x″，方程就變成38x″≡-28（mod 70）或者19x″≡-14（mod 35）。對(duì)模為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的根，并加上同余方程的模來與等式的根相區(qū)分。例如，（mod 12）表示任何對(duì)于模12同余11^[2]的數(shù)。我們前面的研究表明，當(dāng)a和c的最大公約數(shù)不能整除b時(shí)，（mod c）沒有任何實(shí)際意義（或者你更愿意用這個(gè)假想的表達(dá)式）。除此之外，表達(dá)式（mod c）總有真實(shí)值且有無限多個(gè)。當(dāng)a與c互質(zhì)時(shí)，它們都和c同余，或者當(dāng)δ是c和a的最大公約數(shù)時(shí)，它們都和同余。

人們可以對(duì)這些表達(dá)式做類似于簡分?jǐn)?shù)的運(yùn)算。我們這里指出一些可以輕易地從前面討論中推導(dǎo)出來的性質(zhì)。

1．如果對(duì)于模c，a≡α，b≡β，那么表達(dá)式（mod c）和（mod c）等價(jià)。

2．（mod cδ）和（mod c）等價(jià)。

3．當(dāng)k和c互質(zhì)時(shí)，（mod c）和（mod c）等價(jià)。

我們還可以引用很多類似的定理，但是它們都很簡單，對(duì)后續(xù)的討論也不太有用，我們繼續(xù)進(jìn)行其他討論。