第4节　有多少数对应于某个项数为p-1的因数的周期

52

现在，我们讨论一些通过升幂而同余于1的数。我们知道，在每种情况下所产生的最小指数必须是p-1的因数。问题来了，是不是所有p-1的因数都以这种方式出现？而且，如果取出所有不能被p整除的数，并将它们按照使其方幂同余于1的最小指数来归类，那么对应于每个指数有多少个数？首先，我们只考虑从1到p-1的所有正数就足够了；因为，显然地，彼此同余的数必须升到相同的方幂才能同余于1。因此，每个数和它的最小正剩余的指数相同。我们必须搞清楚，就这一点上，数1，2，3，…，p-1是如何依照数p-1的每个因数来分布的。如果d是数p-1的一个因数（这些因数包括1和p-1本身），为了简便，用ψd表示小于p且在它所有同余于1的方幂中d次幂是最小的正数的个数。

53

为了便于理解，举一个例子。对于p＝19，依照18的因数1，2，3，6，9，18的分布如下

因此，在这种情况下，ψ1＝1，ψ2＝1，ψ3＝2，ψ6＝2，ψ9＝6，ψ18＝6。不难看出，每个指数所对应的数的个数等于不大于这指数且与它互质的数的个数。换句话说，在这种情况下（如果沿用条目39的符号），ψd＝φd。下面证明这里的结论在一般情况下都成立。

假设有属于指数d的一个数a（它的d次幂同余于1而所有的低次幂都不同余于1），那么它的所有方幂a2，a3，a4，…，ad或者它们的最小剩余将具备第1个性质（它们的d次幂都同余于1）。这一点还可以这样来表述：数a，a2，a3，a4，…，ad的最小剩余（它们是各不相同的）都是同余方程xd≡1的根，而这个同余方程不能有多于d个根。因此可知，除了数a，a2，a3，a4，…，ad的最小剩余外，从1到p-1之间的其他的数的d次幂一定不同余于1。因此，所有属于指数d的数可在数a，a2，a3，a4，…，ad的最小剩余中来找出。其中哪些数是，有多少，可以按照如下方法来求。如果k是与d互质的数，那么ak的所有指数小于d的方幂都不能同余于1。因为，令1/k（mod d）≡m（参考条目31），就有akm≡a；并且，如果ak的e次幂同余于1且e＜d，也有akme≡1，因而ae≡1，与假设相矛盾。因此，明显有ak的最小剩余属于指数d。但是，如果k与d有公约数δ，ak的最小剩余就不会属于指数d。因为，这时它的次幂已经同余于1［因为kd/δ可以被d整除，即kd/δ≡0（mod d），所以akd/δ≡1］。我们推断，属于指数d的数的个数等于1，2，3，…，d中与d互质的数的个数。但是，必须要记住：这个结论的基础是已经存在一个数a属于指数d。于是，问题停留在是否存在一些指数，使得没有任何数属于它们。因此，本结论局限于要么ψd＝0，要么ψd＝φd。

54

令d，d′，d″，…，是数p-1的全部因数。因为所有的数1，2，3，…p-1是依据这些除数来归类的，所以

ψd＋ψd′＋ψd″＋…＝p-1

但是条目40中已经证明了φd＋φd′＋φd″＋…＝p-1，并且从上一条可以推出，ψd≤φd，但是ψd不会大于φd。对于ψd′和φd′，ψd″和φd″，…，也有类似的结论。所以，如果在ψd，ψd′，ψd″，…中有一项或者几项是分别小于相应的φd，φd′，φd″，…中的项，那么上面第一个和就不可能等于第2个和。因此，我们最终推断出ψd总是等于φd，这与p-1的大小无关。

55

上面的定理的一个特殊情况值得我们注意。总是存在这样的数，它的同余于1的最小次幂是p-1，而且这样的数的个数等于1到p-1中的与p-1互质的数的个数。因为这个定理的证明不像乍看起来那么简单，而且因为这则定理的重要性，我们须要补充一种与上面不太一样的证明。这种方法的多样性可以帮助我们理解更加深奥的问题。将p-1分解为它的质因数，那么p-1＝aαbβcγ…，其中a，b，c…都是不相等的质数。我们分两步来进行证明：

1．总是可以找到一个数A（或者几个数），它属于指数aα，类似地，可以找到数B，C，…，分别属于指数bβ，cγ，…。

2．所有数A，B，C，…的乘积（或者乘积的最小剩余）属于指数p-1。

证明如下：

1．令g为1，2，3，…p-1中的某个数，它不满足同余方程x（p-1）/a≡1（mod p），因为这个同余方程的次数小于p-1，所以这些数不可能都满足它。那么，如果g的（p-1）/aα次幂≡h，那么h或者它的最小剩余属于指数aα。

显然，h的aα次幂同余于g的（p-1）次幂即它不同余于1。因此，h的aα-2，aα-3，…次幂更不可能同余于1。但是，同余于1的h的最小次幂的指数（h所属的指数）必须能够整除aα（参考条目48），又因为aα只可能被它自身和a的更低的方幂整除，所以aα一定是h所属的指数。证明完毕。用类似的方法可证明存在这样的一些数，它们分别属于bβ，cγ，…。

2．假设所有数A，B，C，…的乘积不属于指数p-1而属于更小的数t，那么t整除p-1（参考条目48），也就是说，（p-1）/t是一个大于1的整数。显而易见的是，这个商一定要么是质数a，b，c，…中的一个，要么至少被它们中的一个整除（参考条目17）。例如，假设（p-1）/t被a整除（对于b，c，…，证明都是一样的），那么t整除（p-1）/a，因此乘积ABC…的（p-1）/a次幂同余于1（参考条目46）。但是，因为每一个指数bβ，cγ，…都整除（p-1）/a，所以所有的数B，C，…（A除外）的（p-1）/a次幂都显然将同余于1。因此，我们得出

那么，可以推出，A所属的指数应当能够整除（p-1）/a（参考条目48），即（p-1）/aα＋1是个整数。但是（p-1）/aα＋1＝（bβcγ…）/a不可能是整数（参考条目15）。因此，可以推断我们的假设是矛盾的，也就是说，ABC…的乘积确实属于指数p-1。证明完毕。

第2个证明似乎比第1个长，但第1个没有第2个来得直接。

56

这则定理有力地证明了，在数论研究中必须小心谨慎，不能把还未证明的定理当作已经证明的定理来使用。兰伯特先生在我们前文引述的论文（见Nova acta erudit.第127页）中提到了这则定理，但是没有提到证明这则定理的必要性。除了欧拉先生在Novicomm. Acad Petrop上的论文Demostrationes circa residua ex divisione potestatum per numeros primos resultantia之外，还没有人尝试过给出证明。尤其是在他论文的第37条中，他花了大量的篇幅讨论证明的必要性。但是这位最精细的人给出的证明有两处缺陷。一处是在论文第31条，他默认同余方程xn≡1（用我们的符号翻译他的论证）确实只有n个不同的根，但是之前并没有证明这个方程不能有多于n个根；另一处是论文第34条的公式仅仅是通过归纳法推导出的。