欧拉函数的证明

欧拉函数的证明

设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，A*B和C可建立一一对应的关系。因此φ(n)的值使用算术基本定理便知，
若
则
例如
与欧拉定理、费马小定理的关系
对任何两个互质的正整数a, m(m>=2)有

即欧拉定理
当m是质数p时，此式则为：
a^(p-1)≡1(mod m)
即费马小定理。