高校问答朴宰范 宋茜:求1到n的欧拉函数的和的公式是什么？
来源：百度文库 编辑：高校问答 时间：2024/04/28 08:39:33
设n是正整数，0，1，2，.......n-1中与n互素的数的个数，称之为n的欧拉函数，记作A（n).
若n的标准分解式为n=p1^q1*p2^q2*........ps^qs,则A(n)计算公式是：
A(n)=p1^(q1-1)*p2^(q2-1)...........ps^(qs-1)*(p1-1)(p2-1)(p3-1)...(ps-1)
那么求1到n的欧拉函数的和的公式是什么？
若n的标准分解式为n=p1^q1*p2^q2*........ps^qs,则A(n)计算公式是：
A(n)=p1^(q1-1)*p2^(q2-1)...........ps^(qs-1)*(p1-1)(p2-1)(p3-1)...(ps-1)
那么求1到n的欧拉函数的和的公式是什么？
φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
设n为正整数，以 φ(n)表示不超过n且与n互
素的正整数的个数，称为n的欧拉函数值，这里函数
φ：N→N，n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。
若n为质数则φ(n)=n-1。
由于数论函数很不规则，所以一般不考虑他们的精确和，而只考虑他们的近似逼近或考虑平均值，故只有近似公式，小于x(x 为实数)的欧拉函数都加起来为3*x^2/(π^2)+O(x*lnx).