第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互质的任意模；现在我们专门讨论质数模，在此基础上我们做更一般的研究。