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