定义
欧拉函数?(n)是不超过n且和n互质的正整数的个数。
在微积分学领域，积性函数指的是具有f(ab)=f(a)f(b)f(ab)=f(a)f(b)的函数。
- 定理1 对于素数p，?(p)=p−1。
- 定理2 素数幂pn不互质的只有p的倍数，一共有pn/p=pn−1个，故?(pn)=pn−pn−1。
- 定理3 若mn互质，?(mn)=?(m)?(n)，即欧拉函数是积性函数。
- 定理4 设n=p1a1p2a2...pkak为正整数n的素数幂分解，那么?(n)=n(1−1/p1)(1−1/p2)...(1−1/pk)。
欧拉函数
原文：http://www.cnblogs.com/flipped/p/5324598.html
