第2节 对于模p （质数），数列周期的项数是数p -1的因数
49
定理
如果p 是不能整除a 的质数，那么对于模p 同余于1的a 的最小次幂a t ，指数t 要么等于p -1，要么是p -1的因数。
参考条目45 中的例子。
证明
我们已经看到，t 要么等于p -1要么小于p -1，那么，剩下的只要证明在后一种情况下t 总是p -1的因数。
1．取所有项1，a ，a 2 ，…，a t -1 的最小正剩余，并记作α ，α ′，α ″，…。因此α ≡1，α ′≡a ，α ″≡a 2 ，…。显然，所有这些剩余都互不相同，因为如果两项a m ，a n 有相同的剩余，我们就会有（假设m ＞n ） a m -n ≡1，而m -n ＜1，这是不可能的。因为根据假设，比a t 小的任何方幂都不同余于1。而且，所有的数，α ，α ′，α ″，…都属于数列1，2，3，…，p -1，但并没有将数列中全部的数取尽，因为t ＜p -1。令（A ）表示所有数，α ，α ′，α ″，…的整体。因此（A ）一共有t 项。
2．从1，2，3，…p -1中任取一个不属于（A ）的数β ，以之乘以所有的数α ，α ′，α ″，…，并以β ，β ′，β ″，…表示这些乘积的最小剩余，它们的个数也等于t 。所有这些剩余不仅本身是互不相同的，而且也和所有的数α ，α ′，α ″，…是互不相同的。如果前一个结论不成立，我们就有βa m ≡βa n ，两边除以β ，有a m ≡a n ，这和我们已经证明的矛盾。如果后一个结论不成立，我们有βa m ≡a n ；因此当m ＜n ，β ≡a n -m （β 与α ，α ′，α ″其中一个数同余，与假设矛盾） 。如果最后m ＞n ，两边同时乘以a t -m ，我们有βa t ≡a t ＋n -m ，或者因为a t ≡1，β ≡a t ＋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个结论，如果我们有γa m ≡βa n ，则γ ≡βa n -m 或者γ ≡βa t ＋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的因数。证明完毕。
