### 欧拉函数 #### 欧拉函数 在数论，**对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）**。此函数以其首名研究者欧拉命名(Euler's totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。 欧拉函数的适用范围非常大，许多题目中都会用到欧拉函数的性质。 ##### 欧拉函数表达式1： 欧拉函数的表达为： ~~~[math] \varphi (x)=x\prod_{i=1}^{n}{(1-\frac{1}{p_i})} ~~~ 其中p1,p2,...,pn 表示x的所有质因子，x是不为0的整数。 ##### 欧拉函数表达式2： 假设 ~~~[math] x= {p_1}^{k_1} * {p_2}^{k_2} * ... * {p_n}^{k_n} ~~~ p1,p2,...,pn同上，则其另一种表达为： ~~~[math] \varphi(x)=\prod_{i=1}^{n}{(p_i-1)*p_i^{k_i-1}} ~~~ 特别的， ~~~[math] \varphi(1)=1 ~~~ #### 欧拉函数证明 ##### 容斥定理来证明 对于正整数 x 而言，假设其质因子为p1,p2,p3,...,pn，则小于等于 x 且与 x 不互质的数字的个数为： ~~~[math] g(x)=\frac{x}{p_1}+\frac{x}{p_2}+...+\frac{x}{p_n}-\frac{x}{p_1*p_2}-\frac{x}{p_1*p_3}- ... ~~~ 小于 x 且与 x 互质的数字的个数： ~~~[math] f(x)=x-g(x)=n-\frac{x}{p_1}-\frac{x}{p_2}- ... -\frac{x}{p_n}+\frac{x}{p_1*p_2}+\frac{x}{p_1*p_3}+ ... ~~~ 化简即可得表达式1。（具体化简过程我也不会QAQ） #### 欧拉函数计算 ##### 单值计算 在编程时，习惯上，我们经常用**表达式2**计算欧拉函数的值： ~~~ int eular(int n) {    int ret=1,i;    for(i=2;i*i<=n;i++)   { /* n%i==0时，i为n的质因子，因为如果i不是质因子， 则一i定能分成更小的因子，对应的更小的因子一定在之前出现过了，与之矛盾， 所以i一定不能分割成更小的因子，即i为n的质因子。 */        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; } ~~~ ##### 打表计算 #### 欧拉函数性质 ##### 互质数之和 小于n的正整数中与n互质的数的数字之和为 ~~~[math] f(n)={n}*\frac{\varphi(n)}{2} ~~~ 证明如下： > 对于每个小于 n 的数正整数 a ，如果gcd( n , a )=1,则gcd( n , n-a )=1（ 此处为gcd相关性质，不再证明。）。 > > 所以对于每个与 n 互质的正整数 a ，一定有一个与之对应的与 n 互质数的 n - a ; > > 由此可知，欧拉函数的值总为偶数（1除外），并且总有一对之和为 n， > > 至此，小于n的正整数中与n互质的数的数字之和就可以计算出来了。 ##### 积性函数 欧拉函数是一个积性函数，如果 n , m 互质，则： ~~~[math] \varphi(nm)=\varphi(n)*\varphi(m) ~~~ 可以推出，如果n为质数，则： ~~~[math] \varphi(2n)=\varphi(n) ~~~ ##### 欧拉定理变式 对于任何两个互质的正整数 a , n ，(n>2) ~~~[math] {a}^{\varphi(n)}\equiv 1 mod n ~~~ ##### 费马小定理 当 n = p 且 a 与素数 p 互质时，上式可变为 ~~~[math] {a}^{p-1}\equiv 1 mod p ~~~ ##### n的因数（包括1和它自己）的欧拉函数之和等于n 写成数学表达式的形式即为 ~~~[math] n=\sum_{d|n}\varphi(d) ~~~ 其中 d|n 表示 n 能被 d 整除。 证明如下： > 对于每个 x ( 0 <= x <= n ) 都存在一个gcd( x , n )，可以证得，其值必然为n的因子。 > > 假设gcd( x , n ) = d ,（ d | n ） ，则gcd（ x / d , n / d ）= 1 ，即 x / d 与 n / d 互质。 > > 因此，我们可以求出 gcd( x , n ) 的值为 d 时对应的的数字个数，个数就是 n / d 所对应的欧拉函数值。 > > 由第一行可知，gcd( x , n )的值必然为n的因子，并且只有唯一对应值，因此就可推导出上述公式。