ACM-欧拉函数

新浪博客 发表时间 -- 2009-07-26 21:36:12

欧拉函数

　　在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。
　　例如φ(8)=4，因为1,3,5,7均和8互质。
　　从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
　　φ函数的值
　　φ(1)=1（唯一和1互质的数就是1本身）。
　　若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
　　欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
　　证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，A*B和C可建立一一对应的关系。因此φ(n)的值使用算术基本定理便知，
　　若
　　n= ∏p^(α（下标p）)
　　p|n
　　则φ(n)=∏(p-1)p^(α（下标p）-1)=n∏(1-1/p)
　　p|n p|n
　　例如φ(72)=φ(2^3×3^2)=(2-1)2^(3-1)×(3-1)3^(2-1)=24
　　与欧拉定理、费马小定理的关系
　　对任何两个互质的正整数a, m, m>=2有
　　a^φ(m)≡1(mod m)
　　即欧拉定理
　　当m是质数p时，此式则为：
　　a^(p-1)≡1(mod m)
　　即费马小定理。

；例题：

求从1到n-1与n互质的数的个数,代码如下

int eular(int n)
{
<wbr><wbr><wbr> int ret = 1,i;<br><wbr><wbr><wbr> for (i = 2;i * i &lt;= n;i++)<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr> if (n % i == 0)<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr> {<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> n /= i;<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> ret *= (i - 1);<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> while (n % i == 0)<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> {<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> n /= i;<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> ret *= i;<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> }<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr> }<br><wbr><wbr><wbr> if (n &gt; 1)<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr> ret *= (n - 1);<br><wbr><wbr><wbr> return ret;<br> }</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>