欧拉定理，费马小定理
首先，复习一下欧拉函数(https://www.cnblogs.com/hnoi/p/10992072.html)：
在算术基本定理中，
1~N中与N互质的数的个数成为欧拉函数：
费马小定理：
若p是质数，则对于任意整数a，有。
欧拉定理：
若正整数a,n互质，则 。
证明：
设n的简化剩余系是{}
对任意ai,aj,有。
因为a,n互质，所以。当
时，
代表不同的同余类。
因为简化剩余系关于模n乘法封闭，故也在剩余系集合中。
综上所述，
因此。
证毕。