定义
欧拉函数ϕ(n)是不超过n且和n互质的正整数的个数。
下面直观地看看欧拉函数：
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
φ(n) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 | 12 | 6 | 8 |
定理
- 定理0 算术函数f如果满足对于任意两个互质的正整数m和n，均有f(mn)=f(m)f(n)，就称f为积性函数（或乘性函数）。
如果对于任意两个正整数m和n，均有f(mn)=f(m)f(n)，就称为完全积性函数。
- 定理1 对于素数p，ϕ(p)=p−1。
- 定理2 ϕ(pn)=pn−pn−1，因为素数幂pn不互质的只有p的倍数，一共有pn/p=pn−1个。
- 定理3 若m、n互质，ϕ(mn)=ϕ(m)ϕ(n)，所以欧拉函数是积性函数。
因为mn互质，和m互质的数乘上和n互质的数就会和mn互质。
- 定理4 设n=p1a1p2a2...pkak为正整数n的素数幂分解，那么ϕ(n)=n(1−1/p1)(1−1/p2)...(1−1/pk)。
由定理2，ϕ(pn)=pn−pn−1=pn (1-1/p)，又由定理3，ϕ(n)=p1a1p2a2...pkak(1−1/p1)(1−1/p2)...(1−1/pk)=n(1−1/p1)(1−1/p2)...(1−1/pk)
所以可以方便地求欧拉函数：边找质因子边算，res=n，找到一个质因子p，res=res/p*（p-1）。
代码语言：javascript复制int euler(int x){
int res = x;
for(int i=2; i*i<=x; i )
if(x % i == 0){
res = res / i * (i - 1);
while(x % i == 0) x /= i;
}
if(x > 1) res = res / x * (x - 1);
return res;
}也可以方便地求出所有数的欧拉函数。过程就是先让每个phi[i]=i，再对每个质数p，j为它的倍数，phi[j]=phi[j]/p*（p-1）。
代码语言：javascript复制for(int i=1; i<=maxn; i) phi[i] = i;
for(int i=2; i<=maxn; i =2) phi[i] /= 2;
for(int i=3; i<=maxn; i =2)
if(phi[i] == i){
for(int j=i; j<=maxn; j =i)
phi[j] = phi[j] / i * (i - 1);
}- 定理5 设n是一个大于2的正整数，那么ϕ(n)是偶数。
对于素数p，ϕ(p)=p−1，大于2的素数是奇数，那么它的欧拉函数就是偶数。
对于合数n，
由定理2，ϕ(pk)=pk−pk−1，
p=2时，ϕ(2k)=2k−2k−1=2k−1是偶数，
对于大于2的素数p，ϕ(pk)=pk−pk−1,p为奇数，p的次方也为奇数，两个奇数相减为偶数。
所以ϕ(pk)为偶数。
又由定理3，ϕ(n)=ϕ(p1a1)ϕ(p2a2)...ϕ(pkak)，所以ϕ(n)一定是偶数。
- 定理6 ∑d|nϕ(d)=n。
∑d|nϕ(d)表示所有n的约数的欧拉函数值求和，Cd是gcd(n,x)==d的x(1≤x≤n)的集合，d不同的Cd集合不相交。
若m∈Cd，则gcd(n,m)=d，所以gcd(n/d,m/d)=1，由于1≤m≤n，所以1≤m/d≤n/d，所以m/d可以取小于n/d且与n/d互质的所有数，m和m/d个数相同，所以m的个数就是ϕ(n/d)，也就是|Cd|=ϕ(n/d)。1到n每个数和n的最大公约数一定是n的约数，那么所有集合Cd的所有元素个数之和就是n，也就是∑d|n|Cd|=n。所以∑d|nϕ(d)=n。
