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的因子的意思。