Euler函数
Euler函数
欧拉(Euler)函数通常是指下面这个：
初等数论的欧拉函数
欧拉φ函数：φ(n)是所有小于n的正整数里，和n互素的整数的个数。n是一个正整数。
欧拉证明了下面这个式子：
如果n的标准素因子分解式是p1^a1*p2^a2*……*pm^am，其中众pj(j=1,2,……,m)都是素数，而且两两不等。则有
φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)
利用容斥原理可以证明它。
关于Euler函数的一个著名定理:
a、n都是正整数，并且n>1，(a,n)=1，则有a^φ(n)-1≡0(mod n),这个是同余的表达式。另外还可以写成：n|[a^φ(n)-1]，即n是a^φ(n)-1的因子的意思。