第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，…中的一个。现在我们来证明：同余方程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互质。

但是，如果v＝n-1，即，如果t能够被pn-1整除，或者被p的更高次幂整除，则对于模p，满足同余方程xt≡1的每一个值A也将对于模pn满足这个同余方程。因为，如果令t＝pn-1τ，则有t≡τ（mod p-1）；又因为At≡1（mod p），所以Aτ≡1（mod p）。因此，令Aτ＝1＋hp，我们就有Aτ＝（1＋hp）pn-1≡1（mod pn）（参考条目87）。

89

我们在条目57以及以后的条目中，借助定理“同余方程xt≡1不能有多于t个不同的根”所推出的一切结论，对于模是质数的方幂的情况来说都是成立的，并且，如果我们把那些属于指数pn-1（p-1）的数，也就是那些在周期中包含了所有不被p整除的数，称为原根，那么，对于模是质数的方幂的情况来说就存在原根。进而，我们所讨论的关于指标以及它们的应用，以及关于同余方程xt≡1的解的全部结论都可以应用于这种情况。因为证明没有什么困难，重复这些证明就是多余的。我们之前已经演示过如何从模p的同余方程xt≡1的根去求得模pn的这个同余方程的根。现在，我们必须补充上文中所排除的当模为2的方幂的情况的讨论。