第2节　对于模p（质数），数列周期的项数是数p-1的因数

49

定理

如果p是不能整除a的质数，那么对于模p同余于1的a的最小次幂at，指数t要么等于p-1，要么是p-1的因数。

参考条目45中的例子。

证明

我们已经看到，t要么等于p-1要么小于p-1，那么，剩下的只要证明在后一种情况下t总是p-1的因数。

1．取所有项1，a，a2，…，at-1的最小正剩余，并记作α，α′，α″，…。因此α≡1，α′≡a，α″≡a2，…。显然，所有这些剩余都互不相同，因为如果两项am，an有相同的剩余，我们就会有（假设m＞n）am-n≡1，而m-n＜1，这是不可能的。因为根据假设，比at小的任何方幂都不同余于1。而且，所有的数，α，α′，α″，…都属于数列1，2，3，…，p-1，但并没有将数列中全部的数取尽，因为t＜p-1。令（A）表示所有数，α，α′，α″，…的整体。因此（A）一共有t项。

2．从1，2，3，…p-1中任取一个不属于（A）的数β，以之乘以所有的数α，α′，α″，…，并以β，β′，β″，…表示这些乘积的最小剩余，它们的个数也等于t。所有这些剩余不仅本身是互不相同的，而且也和所有的数α，α′，α″，…是互不相同的。如果前一个结论不成立，我们就有βam≡βan，两边除以β，有am≡an，这和我们已经证明的矛盾。如果后一个结论不成立，我们有βam≡an；因此当m＜n，β≡an-m（β与α，α′，α″其中一个数同余，与假设矛盾）。如果最后m＞n，两边同时乘以at-m，我们有βat≡at＋n-m，或者因为at≡1，β≡at＋n-m，这同样是荒谬的。令（B）表示所有数β，β″，β″，…的整体，它的项数为t。所以我们现在从1，2，3，…，p-1已经有了2t个数。并且，如果（A）和（B）包含了所有这些数，那么（p-1）/2＝t，从而定理得到证明。

3．但是如果有些数遗漏了，令其中一个数为γ。将所有的数α，α′，α″，…乘以γ，令这些乘积的最小剩余为γ，γ′，γ″，…，并把这些最小剩余的整体用（C）表示。因此，（C）就有t个互不相同的数1，2，3，…，p-1，它们与（A）和（B）中的数也各不相同。前两个结论可以用第2部分中的同样的方法来证明。对于第3个结论，如果我们有γam≡βan，则γ≡βan-m或者γ≡βat＋n-m，分别对应于m＜n或者m＞n。在这两种情况下，γ都与（B）中的一个数同余，这与假设矛盾。所以我们有数列1，2，3，…，p-1中的3t个数，如果不再有数遗漏，则有t＝（p-1）/3，定理得证。

4．但是如果还有数遗漏，我们进一步构造第4组数的整体（D）。可知因为数1，2，3，…p-1是有限的，最终会被取完。所以数p-1是t的倍数，t是数p-1的因数。证明完毕。