欧拉定理相关性质及证明

欧拉定理：当与互质时，有
通项公式及其证明：
如果，为质数，则

证明：当一个数不包含质因子时就能与互质，小于等于的数中包含质因子p的只有个，即，把他们去除即可

由唯一分解定理可知，

这就是欧拉函数的通项公式
欧拉定理证明：
设是中与互质的数的集合
则他们模两两不相同，且余数与互质
下面我们证明也有这两个性质
模两两不相同：反证法，设且，即
由于与互质，且不可能是的倍数，所以不可能存在这样的和。
余数都与互质：因为与互质，与互质，所以也与互质，模后也与互质。
所以这个集合模后一定是个两两不同且与互质的数，即为