第3節(jié)　對于給定模求與給定剩余同余的數(shù)的方法

32

從上面的結(jié)論，解決問題“對于給定的模，求與給定剩余所同余的數(shù)的方法”是很容易的，在下面的討論中也會(huì)很有用。指定模A，B，我們求數(shù)z，對于模A，B分別與數(shù)a，b同余。所有z的值都形如Ax＋a，x是未知數(shù)，而且要滿足Ax＋a≡b（mod B）?，F(xiàn)在如果數(shù)A，B的最大公約數(shù)是δ，同余方程的完整解的形式為x≡v（mod B/δ）或者用等價(jià)的等式表達(dá)，x＝v＋kB/δ，k為任意整數(shù)。因此，公式Av＋a＋kAB/δ包括了z的所有值，即z≡Av＋a（mod AB/δ）是這個(gè)問題的完整解。如果我們在模A，B的基礎(chǔ)上再加一個(gè)模C，并且對于模C，z≡c，我們可以按照同樣的方式開展，因?yàn)橄惹皟蓚€(gè)條件已經(jīng)合并為一個(gè)。因此，如果AB/δ和C的最大公約數(shù)為e，并且假設(shè)同余方程（AB/δ）x＋Av＋a≡c（mod C）的解為x≡w（mod C/e），那么問題的解完全可以通過同余方程z≡ABw/δ＋Av＋a（mod ABC/δe）解得。我們觀察到AB/δ是A和B的最小公倍數(shù)，ABC/δ是數(shù)A，B和C的最小公倍數(shù)，那么容易推出不論有多少個(gè)模A，B，C，…，如果它們的最小公倍數(shù)是M，全部的解都可以用z≡r（mod M）來表示。但是當(dāng)并非所有的輔助同余方程都可解時(shí)，我們斷定這個(gè)問題存在不可解的情況。但是顯然，當(dāng)所有的數(shù)A，B，C，…互質(zhì)時(shí)，這種情況是不可能發(fā)生的。

例如，令數(shù)A，B，C，a，b，c分別為504，35，16，17，-4，33。這里的兩個(gè)條件z≡17（mod 504）和z≡-4（mod 35）等價(jià)于一個(gè)條件z≡521（mod 2520），加上條件z≡33（mod 16），我們最終得到z≡3041（mod 5040）。

33

當(dāng)所有數(shù)A，B，C，…都互質(zhì)，可知它們的乘積是它們的最小公倍數(shù)。在這種情況下，多個(gè)同余式z≡a（mod A），z≡b（mod B），z≡c（mod C）…合起來就與單個(gè)同余式z≡r（mod R）等價(jià)，式中R是數(shù)A，B，C，…的乘積。反過來，單個(gè)條件z≡r（mod R）也可以分解為多個(gè)條件，即如果R以任意方式分解為互質(zhì)的因數(shù)A，B，C，…，那么條件z≡a（mod A），z≡b（mod B），z≡c（mod C），…就把原始條件全部涵蓋。這條結(jié)論不僅提供了一個(gè)發(fā)現(xiàn)方程無解的快捷的方法，也是一種令人滿意的、優(yōu)雅的運(yùn)算方式。

34

如上，令z≡a（mod A），z≡b（mod B），z≡c（mod C）。將所有模都分解為互質(zhì)的因數(shù)：A分解為A′A″A?，…；B分解為B′B″B?，…；使得數(shù)A′，A″，…，B′，B″，…要么都是質(zhì)數(shù)，要么都是質(zhì)數(shù)冪。如果數(shù)A，B，C，…中的任何一個(gè)數(shù)已經(jīng)是質(zhì)數(shù)或質(zhì)數(shù)冪，則不用分解?？芍?，上述條件可以用下面的條件來代替：z≡a（mod A′），z≡a（mod A″），z≡a（mod A?），…；z≡b（mod B′），z≡b（mod B″），…；…?，F(xiàn)在如果不是所有的數(shù)A，B，C，…都互質(zhì)（例如A和B非互質(zhì)），顯然A，B的所有質(zhì)除數(shù)并非都各不相同。在因數(shù)A，A″，A?，…中必定有一個(gè)因數(shù)在B′，B″，B?，…能夠找到等于它，或是它的倍數(shù)，或是它的除數(shù)的因數(shù)。假設(shè)第一個(gè)可能性是A′＝B′。那么條件z≡a（mod A′）和條件z≡b（mod B′）必定相同，即a≡b（mod A′或B′），因此其中一個(gè)可以忽略。但是如果z≡a（mod A′）不成立，這個(gè)問題就無解。其次，假設(shè)B′是A′倍數(shù)，那么條件z≡a（mod A′）就一定包含在條件z≡b（mod B′）中，即從后者推出的z≡b（mod A′）必須與前者相同。由此可以推出條件z≡a（mod A′）可以忽略，除非它與其他條件矛盾（如果這樣問題便無解）。當(dāng)所有多余的條件都忽略以后，因數(shù)A′，A″，A?，…；B′，B″，B?，…；…中剩下的模就都是互質(zhì)的。然后我們就能確定問題是否可解，并按照上文描述的方法求解。

35