欧拉函数小结

定义 $\varphi(x)$ 指对于 $\forall i\in [1,x]$ ，满足 $\gcd(i,x)=1$ 的 $i$ 的个数。 也就是小于等于 $x$ 的正整数中与其互质的数的个数。 基本推论 $\varphi(x)=x-1\quad(x\in \mathbb{P})$ $ \begin{aligned} \varphi(p^k)& =p^k-p^{k-1} \quad(p\in \mathbb{P},k\in \Z^*) \\ &= p^k(1-\frac{1}{p})\quad(p\in \mathbb{P},k\in \Z^*)\end{aligned}$ 这是因为只有当一个数不包含质数 $p$ ，才可能与 $x$ 互质。而包含质数 $p$ 的数一共有$ p^{k-1} $个，即 ..