最近在学习数论函数，欧拉函数是其中一个比较重要的一个。
证明了欧拉函数的一些性质，写此文备忘，有不严谨乃至错误处还望指正。
公式预警。
定义：欧拉函数 $\varphi(x)$ 表示 $[1, n]$ 中与 $n$ 互质的数的个数，即：
$$ \varphi(i) = \sum_{i = 1}^n[i \perp n] $$
性质们：
一、若 $p$ 为质数，则 $\varphi(p) = p - 1$
证明：
因为 $p$ 为质数，所以在 $[1, p]$ 中只有 $p$ 本身与其不互质，则由定义得 $\varphi(p) = p - 1$
二、若 $p$ 为质数，则 $\varphi(p^k) = p^k - p^{k - 1}$
证明：
因为 $p$ 为质数，所以只有 $p$ 的倍数与 $p^k$ 不互质，而在 $[1, p^k]$ 中有 $\frac {p^k} {p} = p^{k - 1}$ 个数是 $p$ 的倍数，则由定义得 $\varphi(p^k) = p^k - p^{k - 1}$
三、欧拉函数是积性函数，即对 $a \perp b$，有 $\varphi(a \times b) = \varphi(a) \times \varphi(b)$
证明：
简单来说，根据中国剩余定理，我们可以证明 $Z_a^* \times Z_b^*$ 与 $Z_{a \times b}^*$ 间的一一对应关系。
具体来说，考虑 $Z_a^*$ 中的 $p$，$Z_b^*$ 中的 $q$，$Z_{a \times b}^*$ 中的 $x$ $$ \begin{align*} x &\equiv p \pmod a \\ x &\equiv q \pmod b \end{align*} $$ 由中国剩余定理可得，该方程组有且仅有一个解。
可以构造出解，我们设 $a' \equiv a^{-1} \pmod b$，$b' \equiv b^{-1} \pmod a$，那么 $$x \equiv q \times a \times a' + p \times b \times b' \pmod {a \times b}$$ 这样，$p$ 有 $\varphi(a)$ 种取值， $q$ 有 $\varphi(b)$ 种取值，我们只需证明，对于不同的 $p, q$ ，$x$ 的取值是不同的，那么 $x$ 就有 $\varphi(a) \times \varphi(b)$ 种取值，假设有 $p_1 \not= p_2, q_1 \not= q_2$ 但有
$$ q_1 \times a \times a' + p_1 \times b \times b' \equiv q_2 \times a \times a' + p_2 \times b \times b' \pmod {a \times b} $$
移项可得
$$ (q_1 - q_2) \times a \times a' + (p_1 - p_2) \times b \times b' \equiv 0 \pmod {a \times b} $$
因为我们没有 $q_1 - q_2 = 0$，也没有 $q_1 - q_2 = b$，对于 $p$ 同理，所以上式不成立。
由此我们证明了数对 $(p, q)$ 与 $x$ 有一一对应的关系，也就证明了 欧拉函数是积性函数，即 $$ a \perp b \Rightarrow \varphi(a \times b) = \varphi(a) \times \varphi(b) $$
四、欧拉函数公式： $$ \varphi(n) = n \times \prod (1 - \frac 1 p_i)$$ 其中 $p_i$ 为 $n$ 的质因子。
证明：
这个公式可以简单地由欧拉函数为积性函数这个结论推得。 设 $n = \prod p_i^{k_i}$ $$ \begin{align*} \varphi(n) &= \varphi(\prod p_i^{k_i}) \\ &= \prod \varphi(p_i^{k_i}) \\ &= \prod p_i^{k_i} - p_i^{k_i - 1} \\ &= \prod p_i^{k_i} \times (1 - \frac 1 p_i) \\ &= \prod p_i^{k_i} \times \prod (1 - \frac 1 p_i) \\ &= n \times \prod (1 - \frac 1 p_i) \end{align*} $$
有了这个公式，我们可以在 质因子分解 的复杂度内求欧拉函数。
五、如果质数 $p$ 是 $i$ 的因子，那么 $\varphi(p \times i) = p \times \varphi(i)$，否则 $\varphi(p \times i) = (p - 1) \times \varphi(i)$
证明：
$p \mid i$ 的情况：$i$ 含有 $i \times p$ 的所有质因子，直接由欧拉函数的公式得： $$ \frac {\varphi(i \times p)} {i \times p} = \frac {\varphi(i)} {i} $$ 即 $\varphi(p \times i) = p \times \varphi(i)$
$p\not\mid i$ 的情况：显然有 $p \perp i$ 直接由欧拉函数的积性性质得 $\varphi(i \times p) = \varphi(i) \times \varphi(p) = \varphi(i) \times (p - 1)$
有了此性质，我们可以线性筛 $O(n)$ 求出 $[1, n]$ 的所有欧拉函数。