基础公式
- 莫比乌斯函数
[mu(n)=
left{egin{matrix}
1 & n=1 \
(-1)^k & n=prod_{i=1}^kp_i \
0 & else
end{matrix}
ight.]
- 莫比乌斯反演公式
[F(n)=sum_{d|n}f(d) sim f(n)=sum_{d|n}mu(d)F(frac{n}{d})
]
- 证明
$$sum_{d|n}mu(d)F(frac{n}{d}) = sum_{d|n}[mu(d)sum_{d'|frac{n}{d}}f(d')] = sum_{d'|n}[f(d')sum_{d|frac{n}{d'}}mu(d)]=f(n)$$
- (mu)函数的性质
[sum_{d|n}mu(d)=[n=1]
]
- 欧拉函数的性质1
[sum_{d|n}{varphi(d)}=n
]
- 证明
将前$n$个数按$gcd$分组，则有$$n=sum_{d|n}varphi(frac{n}{d})=sum_{d|n}varphi(d)$$
- 欧拉函数的性质2
(n>1)时$$sum_{gcd(i,n)=1}i=frac{nvarphi(n)}{2}$$- 证明1
若(d|n)那么((n-d)|n),将(n)和(n-d)配成一组，每组的和为(n),一共有(frac{varphi(n)}{2})组,所以(sum_{gcd(i,n)=1}i=frac{nvarphi(n)}{2}). - 证明2
[sum_{gcd(i,n)=1}i=frac{nvarphi(n)}{2}=sum_{i=1}^{n}i[gcd(i,n)=1]=sum_{i=1}^{n}[isum_{d|gcd(i,n)}mu(d)]=sum_{d|n}[mu(d)sum_{d|i}i]=sum_{d|n}[mu(d)frac{n}{2}(1+frac{n}{d})]=frac{n}{2}(sum_{d|n}mu(d)+sum_{d|n}mu(d)frac{n}{d})=frac{n[n=1]}{2}+frac{nvarphi(n)}{2}=frac{nvarphi(n)}{2} ] - 证明1