第3章　冪剩余
（第45～93條）

第1節　首項為1的幾何數列各項的剩余構成周期序列

45

定理

在任何幾何數列1，a，a2，a3，……中，除了首項1之外，還有另外一項at對于與a互質的模p同余于1，且指數t＜p。

證明

因為模p是與a互質的數，因此模p與a的任何次冪都互質，此數列中沒有一項被p整除，但是每一項將同余于數1，2，3，…，p-1中的一個。因為這些數的個數是p-1，顯然，如果我們考慮這個數列的項數比p-1多時，它們的最小剩余不會完全不同。所以，在項1，a，a2，a3，…，ap-1中，至少可以找到兩項彼此同余。因此令am≡an，且m大于n。兩邊除以an，我們得到am-n≡1（參考條目22），這里0＜m-n＜p。證明完畢。

例：在數列2，4，8，…中，對于模13同余于1的第一項是212＝4096。但是還在這個數列中，對于模23，我們有211＝2048≡1。類似地，數5的6次冪15625對于模7同余于1，而對模11則是3125，即數5的5次冪。因此在一些情況下指數小于p-1的方冪就已經同余于1，但是在其他情況下必須達到p-1次冪。

46

當繼續考察此數列中同余于1的項后面的項時，則從開始起的同樣的那些余數將會再次出現。因此，如果at≡1，則有at＋1≡a，at＋2≡a2，…，直到項a2t，它的最小剩余又是1，并且剩余的周期重新開始。因此形成由t個剩余構成的周期，一個周期結束之后就會從第1項重復開始；除出現在周期里的項之外，任何其他項都不可能出現在整個數列中。一般地，我們有amt≡1和amt＋n≡an。根據我們的符號可以用下式表達：如果r≡ρ（mod t），那么ar≡aρ（mod p）。

47

這則定理幫助我們求得不論指數多大的方冪的剩余，只要我們找到了同余于1的方冪。例如，如果我們要求31000被13去除后所得的剩余，因為33≡1（mod 13）得出t≡3；所以從1000≡1（mod 3），得出31000≡3（mod 13）。

48

當at是同余于1的最小次冪（除了a0＝1，這種情況我們不在這里考慮），構成剩余周期的所有的t項都是彼此不同的，這一點從條目45的證明可知。在這種情況下，條目46的逆定理也成立：如果am≡an（mod p），我們有m≡n（mod t）。因為如果m，n對于模t不同余，那么它們的最小剩余μ，v就不同。但是，如果aμ≡am，av≡an，則aμ≡av，即并非所有小于at的方冪都不同余，這與我們的假設矛盾。

因此，如果ak≡1（mod p），那么k≡0（mod t），即k可以被t整除。

到目前為止，我們僅討論了與a互質的任意模；現在我們專門討論質數模，在此基礎上我們做更一般的研究。