第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）?？芍驗閿?，2，3，…p-1是有限的，最終會被取完。所以數p-1是t的倍數，t是數p-1的因數。證明完畢。