请输入您要查询的百科知识:

 

词条 φ函数
释义

φ函数是小于或等于n的正整数中与n互质的数的数目。

定义

ψ函数即欧拉函数。

在数论中,对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数、欧拉商数等。

例如,因为1,3,5,7均和8互质。

欧拉函数实际上是模n的同余类所构成的乘法群(即环的所有单位元组成的乘法群)的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。

欧拉函数的值

(小于等于1的正整数中唯一和1互质的数就是1本身)。

若n是质数p的k次幂,,因为除了p的倍数外,其他数都跟n互质。

欧拉函数是积性函数,即是说若m,n互质,。证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理,和C可建立双射(一一对应)的关系。因此的值使用算术基本定理便知,

性质

n的欧拉函数 也是循环群 Cn 的生成元的个数(也是n阶分圆多项式的次数)。Cn 中每个元素都能生成 Cn 的一个子群,即必然是某个子群的生成元。而且按照定义,不同的子群不可能有相同的生成元。此外, Cn 的所有子群都具有 Cd 的形式,其中d整除n(记作d | n)。因此只要考察n的所有因数d,将 Cd 的生成元个数相加,就将得到 Cn 的元素总个数:n。也就是说:

其中的d为n的正约数。

运用默比乌斯反转公式来“翻转”这个和,就可以得到另一个关于的公式:

其中 μ 是所谓的默比乌斯函数,定义在正整数上。

对任何两个互质的正整数a, m(即 gcd(a,m) = 1),,有

即欧拉定理。

这个定理可以由群论中的拉格朗日定理得出,因为任意与m互质的a都属于环 的单位元组成的乘法群

当m是质数p时,此式则为:

即费马小定理。

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/15 21:16:03