什么是欧拉函数

欧拉函数就是指:对于一个正整数n,小于或等于n的正整数中与n互质的正整数个数(包括1)的个数,记作 φ ( n ) 。

在数论，对正整数 n，欧拉函数是小于或等于 n 的正整数中与 n 互质的数的数目尺扮（因此φ(1)=1）。

此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为 Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为 1,3,5,7 均和 8 互质。

从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

通式：

(其中 p1, p2……pn 为 x 的所有质因数，x 是不为 0 的整数)

定义 φ(1)=1（和 1 互质的数(小于等于 1)就是 1 本身）。

注意：每种质因数只有仿困唯一个。

比如 12=2*2*3 那么φ（12）=φ（4*3）=φ（2^2*3^1）=（2^2-2^1）*（3^1-3^0）=4

若 n 是质数 p 的 k 次幂，备培

，因为除了 p 的倍数外，其他数都跟 n 互质。

设 n 为正整数，以 φ(n)表示不超过 n 且与 n 互素的正整数的个数，称为 n 的欧拉函数值

φ：N→N，n→φ(n)称为欧拉函数。

欧拉函数是积性函数——若 m,n 互质，

特殊性质：当 n 为奇质数时，

, 证明与上述类似。

标签：欧拉,函数