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） ，那么它的所有方幂a 2 ，a 3 ，a 4 ，…，a d 或者它们的最小剩余将具备第1个性质（它们的d 次幂都同余于1） 。这一点还可以这样来表述：数a ，a 2 ，a 3 ，a 4 ，…，a d 的最小剩余（它们是各不相同的） 都是同余方程x d ≡1的根，而这个同余方程不能有多于d 个根。因此可知，除了数a ，a 2 ，a 3 ，a 4 ，…，a d 的最小剩余外，从1到p -1之间的其他的数的d 次幂一定不同余于1。因此，所有属于指数d 的数可在数a ，a 2 ，a 3 ，a 4 ，…，a d 的最小剩余中来找出。其中哪些数是，有多少，可以按照如下方法来求。如果k 是与d 互质的数，那么a k 的所有指数小于d 的方幂都不能同余于1。因为，令1/k （mod d ）≡m （参考条目31） ，就有a km ≡a ；并且，如果a k 的e 次幂同余于1且e ＜d ，也有a kme ≡1，因而a e ≡1，与假设相矛盾。因此，明显有a k 的最小剩余属于指数d 。但是，如果k 与d 有公约数δ ，a k 的最小剩余就不会属于指数d 。因为，这时它的次幂已经同余于1［因为kd /δ 可以被d 整除，即kd /δ ≡0（mod d ），所以a kd /δ ≡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条，他默认同余方程x n ≡1（用我们的符号翻译他的论证） 确实只有n 个不同的根，但是之前并没有证明这个方程不能有多于n 个根；另一处是论文第34条的公式仅仅是通过归纳法推导出的。
