问题
证明：
求解
容易知道，数列$a^0, a^1, a^2, …, a^x,…$一定有一段长度不超过$c$的循环节。设这段循环节从$r$开始，长度为$l$，那么$a^r \equiv a^{r+l} \pmod c$。
而定理中有一个$\mod \phi(c)$，这提示我们考虑循环的性质。根据定理，我们不妨猜想$\phi(c)$就是一个循环节的长度的倍数，即$l\mid \phi(c)$，并且从数列的前$\phi(c)$项中的某一项开始就已经开始循环了。
首先对于$r$有2个性质：
- 数列前$r$项和后面所有项分别处于两个不同的集合中。因为如果两个集合相交，那么说明可以改变$r$的大小使得两个集合不相交，这样就不符合循环从$r$开始。
- 前$r$项没有重复的项。因为如果有，说明循环在$r$之前就已经开始，这也不符合$r$的定义。
对于$\gcd(a, c) = 1$的情况，由于欧拉定理，该式子显然成立。对于其他更为平凡的情况，则有：
- $a$是质数，则$a\mid c$。则设$c=ka^e$，则$\phi(c)=\phi(k) \times a^{e-1}\times (a-1)$。则$a^{\phi(k)} \equiv 1 \pmod k$，则$a^{\phi(c)} \equiv 1 \pmod k$。令$a^{\phi(c)}=sk + 1$，则$a^{\phi(c)+e}=ska^e+a^e=sc+a^e$，即$a^{e+\phi(c)} \equiv a^e \pmod c$。因此可知$r\le e$。易证$\phi(c)\ge e$。（考虑构造不等式）
- $a$是质数的幂，则设$a=p^e$，$c=kp^w$。则$\phi(c)=\phi(k)\times p^{w-1}\times (p-1)$。则$p^{\phi(k)} \equiv 1 \pmod k$，则$p^{\phi(c) \frac{e}{\gcd(e, \phi(c))}} \equiv 1 \pmod k$。令$l’ = \frac{\phi(c)}{\gcd(e, \phi(c))}$,$p^{e l’}=sk+1$，则$p^{(l’+w)e }=a^{w+l’}=skp^{ew}+p^{ew}=sp^{(e-1)w}c+a^w$，即$a^{w+l’} \equiv a^w \pmod c$。因此可知$r\le w$，$l’\mid \phi(c)$，即$\phi(c)$可以构成一个周期。同样，易证$\phi(c)\ge w$。（考虑构造不等式）
- $a$是2个质数的幂的积，则设，那么由2可得。对前一个式子两边乘以，对后一个式子两边乘上，将两个式子合并就有。同样，令，就有，因此利用上式即可证明。
- $a$为多个质数的幂的积，则依照3进行即可。
由此就完成了证明。
（如果证错了请和我说！）