maple如何计算欧拉函数数怎么调试

来源：蜘蛛抓取(WebSpider) 时间：2016-12-16 04:19 标签： 如何计算欧拉函数

比赛的时候做了一道欧拉函数的題目所以想在这里整理一下定义。

  1. 定义：在数论对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目此函数以其首名研究者歐拉命名，它又称为Euler's totient function例如φ(8)=4，因为1,3,5,7均和8互质

  2. (注意：每种质因数只一个。比如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→Nn→φ(n)称为欧拉函数。

    欧拉函数是积性函数——若m,n互质φ(mn)=φ(m)φ(n)。特殊性质：当n为奇数时φ(2n)=φ(n), 证明与上述类似。

  3. 3、对于某一合数n可分解为两个素数之积a*b则φ(n)=φ(a)*φ(b)

    在比a*b小的a*b-1个整数中，只有那些既与a互质、又与b互质的数才会满足与a*b互质而显然满足条件的有φ(a)*φ(b)个数，所以φ(a*b)=φ(a)*(b)

我要回帖

更多关于 如何计算欧拉函数 的文章

 

随机推荐