欧拉函数
定义
欧拉函数(Euler's totient function),即
比如说
当 n 是质数的时候,显然有
性质
-
欧拉函数是 积性函数。
即对任意满足
的整数 ,有 。 特别地,当
是奇数时 。 证明参见 剩余系的复合。
-
。 证明
利用 莫比乌斯反演 相关知识可以得出。
也可以这样考虑:如果
,那么 。 如果我们设
表示 的数的个数,那么 。 根据上面的证明,我们发现,
,从而 。注意到约数 和 具有对称性,所以上式化为 。 -
若
,其中 是质数,那么 。 (根据定义可知) -
由唯一分解定理,设
,其中 是质数,有 。 证明
-
引理:设
为任意质数,那么 。 证明:显然对于从 1 到
的所有数中,除了 个 的倍数以外其它数都与 互素,故 ,证毕。 接下来我们证明
。由唯一分解定理与 函数的积性
-
-
对任意不全为
的整数 , 。 可由上一条直接计算得出。
实现
如果只要求一个数的欧拉函数值,那么直接根据定义质因数分解的同时求就好了。这个过程可以用 Pollard Rho 算法优化。
注:如果将上面的程序改成如下形式,会提升一点效率:
如果是多个数的欧拉函数值,可以利用后面会提到的线性筛法来求得。 详见:筛法求欧拉函数
欧拉定理
与欧拉函数紧密相关的一个定理就是欧拉定理。其描述如下:
若
扩展欧拉定理
当然也有扩展欧拉定理
证明和 习题 详见 欧拉定理
最后更新: May 8, 2024
创建日期: July 11, 2018
创建日期: July 11, 2018