欧拉函数

设 m 是一个正整数，则 m 个整数 0,1,..., m-1 中与 m 互素的整数的个数，记为 f(m)，通常叫做欧拉函数。

 欧拉函数有很多性质：

1) f(p^k)= p^k- p^k-1 ，p 为素数

证明：1 到 p^k 范围中，除 p 的倍数外，其它数都与 p^k 互素，因为 p 是素数。故 f(p^k)= p^k- p^k-1。

 

2) f(m) 为积性函数，即 f(m* n)= f(m)* f(n)，若 m, n 互质

证明略。

 

3) 设正整数 n 有标准因数分解式为 n= p1^a1 * p2^a2 *... * pk^ak，

    则  f(m)= n*( 1- 1/ p1 )* ( 1- 1/ p2 )* ... * ( 1- 1/ pk ) 。

证明：f(n)= f(p1^a1)* f(p2^a2)* ... * f(pk^ak)  //  // 积性函数性质

= ( p1^a1- p1^{a1- 1} )* (p2^a2- p2^a2-1)* ... * (pk^ak- pk^ak-1)   //  由性质一

= p1^a1 * p2^a2 *... * pk^ak * ( 1- 1/ p1 )* ( 1- 1/ p2 )* ... * ( 1- 1/ pk )   // 除以 pi^ai

= n* ( 1- 1/ p1 )* ( 1- 1/ p2 )* ... * ( 1- 1/ pk )

 

4) 设 n 是一个正整数， å f(d)= n ,  其中 d| n, 且 d> 0

证明: 令函数 F(pⁿ)= f(1)+ f(p)+ f(p²)+ ... + f(pⁿ)， 其中 p 为质数。

则由 性质一 有: F(pⁿ)= 1- 0+ p- 1+ p²- p+ ... + pⁿ- p^n-1 = pⁿ

n= p1^a1 * p2^a2 *... * pk^ak    // 标准因式分解

= F(p1^a1)* F(p2^a2)* ... * F(pk^ak )

=  å f(d)

 

5) 设 p, n 为正整数且 p 为 n 的质因数，有

　　1. 如果 n% p²= 0，则 f(n)= f(n/ p)* p。

　　2. 如果 n% p== 0 && n% p²!= 0，则 f(n)= f(n/ p)* (p- 1)

证明 1：f(n)= f(p1^a1 * p2^a2 *... * pk^ak)    // 标准因式分解

= f(p1^a1)* f(p2^a2)* ... * f(pk^ak)  // 积性函数性质

= ( p1^a1- p1^{a1- 1} )* (p2^a2- p2^a2-1)* ... * (pk^ak- pk^ak-1)   //  由性质一

易知， p 必定与 p1 ... pk 中某一个相等，假设为 p1。

则 f(n/p)= ( p1^{a1- 1}- p1^a1- 2 )* (p2^a2- p2^a2-1)* ... * (pk^ak- pk^ak-1) 

= ( p1^a1- p1^{a1- 1} )* (p2^a2- p2^a2-1)* ... * (pk^ak- pk^ak-1) / p

=  f(n)/ p

所以有  f(n)= f(n/ p)* p

 

证明 2: 易知 p 与 n/ p 互素，所以  f(n)= f(n/ p)* f(p)=  f(n/ p)* (p- 1)

 

由性质 5：我们可以得到计算欧拉函数的算法，代码如下：

int Eular( int n ){
    int ret= 1, i;
    for( i= 2; i* i<= n; ++i )
    if( n% i== 0 ){
        n/= i, ret*= (i- 1);
        while( n% i== 0 ){
            n/= i, ret*= i;
        }
    }
    if( n> 1 ) ret*= (n- 1);
    return ret;
}

另外，欧拉函数与法雷数列关系比较紧密，可以查找相关资料。