第13節　模是質數方冪

82

到目前為止，我們所探討的內容都以質數模為前提。接下來討論當模是合數的情況。然而，這里出現的定理不像前面的情況那么優美，也無須使用微妙的技巧去發現這些定理（因為使用前面講過的原理就可以推導出這里幾乎所有的定理），那么詳盡地討論所有的情況是沒有必要也是煩瑣枯燥的。所以，我們只討論哪些情況與之前有相同的性質，哪些情況有它們自己獨特的性質。

83

針對一般情況，條目45到48的定理已經得到證明。但是條目49的定理必須做如下更改：

如果f表示與模m互質且小于m的數的個數，即f＝φm（參考條目38），且如果a是與m互質的一個給定的數，那么a的對于模m同余于1的最小方冪的指數t就等于f或者是f的一個因數。

如果我們用m替換p，用f替換p-1，并且取與m互質且小于m的數來代替1，2，3，…，p-1，條目49中定理的證明在這種情況下是成立的。所以讀者自己可以回到條目49來做這個證明。但是，條目50和51里面討論的其他那些定理在這里不能直接應用，必須采用迂回的方式。關于條目52和后面的那些定理，就模是質數冪和模可以被多于一個質數整除的不同情況，它們的區別是非常大的。因此，我們單獨討論后一種情況。

84

如果p是質數，且模m＝pn，那么我們有f＝pn-1（p-1）（參考條目38）。現在，如果我們將條目53和54中的定理用于這個情況下，并按照前一條目做出必要的改變，我們就會發現，只要我們首先證明形如xt-1≡0（mod pn）的同余方程不可能有多于t個不同的根，那兩個條目中的定理在這種情況下依然成立。我們在條目43中通過使用更加一般的結論證明了對于指數模它是成立的；但這條定理僅針對質數模成立，在合數模的情況下不適用。然而，我們會用一種特殊的方法證明在這種情況下這條定理是成立的。在第8章我們會更加容易地證明它。

85

我們現在證明這條定理：

如果數t和pn-1（p-1）的最大公約數為e，那么同余方程xt≡1（mod pn）就有e個不同的根。

令e＝kpv，式中k不包含因數p。因此，k整除數p-1。那么，對于模p，同余方程xt≡1就有k個不同的根。如果我們分別用A，B，C，…表示這些不同的根，那么，對于模pn的同樣的同余方程的每個根一定對于模p同余于數A，B，C，…中的一個?，F在我們來證明：同余方程xt≡1（mod pn）有pv個根對于模p同余于A，有相同多個根對于模p同余于B，…。由此推出，正如我們之前所說的，所有的根的個數等于kpv，也就是e。下面我們首先證明：如果α是對于模p同余于A的根，那么

也是該同余方程的根。然后，我們證明：在對于模p同余于A的數中，只有形如α＋hpn-v（h表示任意整數）的數是該同余方程的根。因此，顯然只有pv個不同的根。對于同余于B，C，…的根，這個結論也成立。最后，我們證明：總是能夠找到一個對于模p同余于A的根。

86

定理

如果按照上一條目，t是一個被pv整除，但不能被pv＋1整除的數，我們有（α＋hpμ）t-αt≡0（mod pμ＋v）并且同余于αt-1hpμt（mod pμ＋v＋1）。

當p＝2且μ＝1時，定理的第二部分不成立。

通過展開二項式可以證明這條定理，前提是我們能證明第2項以后所有的項都能被pμ＋v＋1整除。但是，因為討論系數的分母會陷入爭論，我們選擇下面的方法。

我們首先假設μ大于1且v等于1，那么我們就有

但是

α＋hpμ≡α（mod p2）

所以，（α＋hpμ）t-1，α（α＋hpμ）t-2，…中的每一項都同余于αt-1（mod p2），并且，它們的和就同余于tαt-1（mod p2）；那么它就是tαt-1＋Vp2的形式，式中V是某個整數。那么，（α＋hpμ）t-αt就有如下的形式：

αt-1hpμt＋Vhpμ＋2

即同余于αt-1hpμt（mod pμ＋2）且同余于0（mod pμ＋1）。

因而，對于這種情況，定理得證。

如果現在仍假定μ＞1，但對于另外的一些v值定理不成立，那么，就一定應該有一個界限值，在到達這個界限之前，此定理總是成立的。超出這個界限之后，此定理就不成立。令使定理不成立的v的最小值等于φ。顯然，如果t能夠被pφ-1整除，但不能被pφ整除，則定理就仍然成立。反之，如果我們用tp代替t，定理就不成立。那么，我們有

或者等于αt＋αt-1hpμt＋upμ＋φ，其中，u是整數。但是，因為對于v＝1，定理已經得證，我們有

因而

即，如果用tp代替t，定理成立，因為v＝φ。但是這與假設矛盾，因此，定理對于v所有的值都成立。

87

現在，還剩下μ＝1的情況沒有討論。通過使用完全類似于上個條目的方法，我們可以不用二項式定理證明以下各式

因此，由它們的和得到的多項式（項數為t）就同余于下式

但是，因為t可以被p整除，所以，除了當p＝2的情況外（上一條目提到了這個情況），（t-1）t/2就都可以被p整除。然而，在其他的情況下，我們有（t-1）tαt-2hp/2≡0（mod p2），并且像上一條目一樣，多項式和同余于tαt-1（mod p2）。剩下的證明按照同樣的方式進行。

除了p＝2的情況之外，一般的結果就是

（α＋hpμ）t≡αt（mod pμ＋v）

并且，對于任何模為比pμ＋v更高次的p的方冪，（α＋hpμ）t就不同余于αt，前提是h不能被p整除且pv是整除t的p的最高次冪。

由此我們可以立即推導出在條目85中提出的兩條定理：

第一，如果αt≡1，我們同樣有（α＋hpn-v）t≡1（mod pn）。

第二，如果某個數α′對于模p同余于A，因而也同余于α，但對于模pn-v不同余于α，并且如果α′滿足同余方程xt≡1（mod pn），我們就令α′＝α＋lpλ使得l不能被p整除。由此推出，λ＜n-v，因而（α＋lpλ）t就對于模pλ＋v同余于αt，但對于模p的更高次冪的模pn則不同余于αt。因此，αt不可能是同余方程xt≡1的根。

88

第三，我們曾經提出求同余方程xt≡1（mod pn）的某個同余于A的根。我們這里只演示在已經知道這個方程對于模pn-1的一個根的情況下，我們怎樣求解。顯然，知道這一點就足夠了；因為，當模為p時，A是這個同余方程的一個根，我們可以從模p推到模p2，進而依次推到后面所有連續的方冪。

因而，我們假設α是同余方程xt≡1（mod pn-1）的一個根。我們現在求同一個同余方程對于模pn的根。我們假設這個根等于α＋hpn-v-1。從上一條目知，這個根一定有這種形式（我們單獨考慮v＝n-1的情況，但是要注意v不可能大于n-1）。因此，我們得到

但是

因此，如果這樣選擇h，使得1≡αt＋αt-1htpn-v-1（mod pn）或者使得（αt-1）/pn-1＋αt-1ht/pv被p整除［因為，根據假設，1≡αt（mod pn-1）并且t能夠被pv整除］，那么，我們就求得了想要的根。從上一章可知，這是能夠做到的，因為我們預先假設t不能被比pv更高次的p的方冪整除，因而αt-1 t/pv就與p互質。